Primzahl Test

Jochen S.

Die Schleife sieht bei dir so aus:

for(i=2; i<Prim; i++)
{
//...
}

Hier würde es reichen, wenn man die bis Prim/2 laufen lässt.
Außerdem ist 77 keine Primzahl...

Edit: Wenn du nicht willst, dass so viele Ausgaben gemacht werden, könntest du ja in einer Variablen sie Anzahl der gefundenen Teiler speichern. Wenn 0 herauskommen sollte, ist die Zahl eine Primzahl.

mngbd

Haki schrieb:

du hast recht. die Variable ist jetzt richtig, die primzahlerkennung läuft wirklich nicht wie sie laufen soll. wenn ich eine höhere Zahl eingebe, wie z.B. 77 kommt dann diese Ausgabe raus:

Und da heisst es immer, dass imperatives Programmieren einsteigerfreundlich ist... ich glaub nicht so recht dran.

Bei jedem Schleifendurchlauf trifft entweder der then-Teil oder der else-Teil zu (klar, oder?). Wenn kein Rest bleibt, kann's keine Primzahl sein, dass stimmt. Aber wenn beim n-ten i ein Rest bleibt, heisst das noch nicht, dass es eine Primzahl ist. Es ist erst dann sicher eine Primzahl, wenn für alle i ein Rest bleibt.

mngbd

Jochen S. schrieb:

Hier würde es reichen, wenn man die bis Prim/2 laufen lässt.

Oder gleich nur bis sqrt(Prim).

Jochen S. schrieb:

Wenn du nicht willst, dass so viele Ausgaben gemacht werden, könntest du ja in einer Variablen sie Anzahl der gefundenen Teiler speichern.

Das wäre nicht nur Primzahltesten sondern Teilerzählen. Wenn man nur testen will, muss man nur im richtigen Moment rausspringen.

Haki

ok hab das gemacht mit dem sqrt. Habe jetzt immernoch zwei Probleme und zwar....
wenn 1,2 oder 3 eingebe wird nichts ausgegeben.habe versucht i kleiner zu machen aber es ging trotzdem nicht. das zweite Problem ist das jede zahl, die mit 7 endet, wie z.B. 77, 187 oder 987, ist immer eine Primzahl. ansonsten funktionert dir funktion einwandfrei

for(i=2; i<=sqrt(Prim); i++)
{
    if ( Prim % i == 0 )
    {
        printf("%d ist keine Primzahl!\n", Prim);
        break;
    }
    else
    {
        printf("%d ist eine Primzahl!\n", Prim);
        break;
    }
}

BasicMan01

schau dir mal an, was sqrt zurueckliefert.

fuer den Fall von 77 kommt bei sqrt(77) der wert 8.xxx heraus. Deine Schleife
geht also nur bis zur 8. 77 ist aber auch durch 11 teilbar. sqrt ist also nicht der richtige Weg. X/2 wie von Jochen erwaehnt ist da etwas besser.

die Werte fuer 1,2 und 3 kannst gleich abfangen. (Prim <= 3)

Genmutant

Aaaaaber 77 ist durch 7 teilbar. und 7 is kleiner als 8.xx.
Bis zur Wurzel reicht vollkommen.

BasicMan01

stimmt *LOL* ... hab heut nen schlechten Tag.

Allerdings wuerde ich dann mit einer Status-Variablen (bool) arbeiten, die auf false gesetz wird, wenn eine Bedingung x%x == 0 liefert.
Das Break fuehrt dazu, dass 77%2 > 0 liefert und dann die Schleife schon abbricht

Jochen S.

So könnte man es machen:

int IsPrim(int Prim)
{
    int iPrim = 1;
    int i;

        for(i=2; i<=sqrt(Prim); i++)
        {
            if ( Prim % i == 0 )
            {
            iPrim = 0;
            break;
            }
        } 

    return iPrim;
}

Finde das mit der Funktion irgendwie schöner...

MfG, Jochen

mngbd

BasicMan01 schrieb:

Allerdings wuerde ich dann mit einer Status-Variablen (bool) arbeiten, die auf false gesetz wird, wenn eine Bedingung x%x == 0 liefert.

Jochen S. schrieb:

So könnte man es machen:
...

Nicht vergessen: C ist C, da darf man sich's einfach machen:

#include <stdbool.h>

bool isprime(int number)
{
    int limit = sqrt(number);

    for (int i = 2; i <= limit; i++)
        if (number % i == 0)
            return false;

    return true;
}

Sicherheitshalber das sqrt(number) aus der for-Bedingung rausnehmen, es muss schon ein ausgefeilter Compiler sein, damit er sowas optimiert.

Jochen S. schrieb:

Finde das mit der Funktion irgendwie schöner...

Das war noch mal...?
Edit: Schon klar...

Jochen S.

Gut, das würde auch in C++ funktionieren. (Auch ohne das Einbinden von stdbool.h)
Finde meine Funktion aber schöner.

Jochen S. schrieb:

Gut, das würde auch in C++ funktionieren. (Auch ohne das Einbinden von stdbool.h)
Finde meine Funktion aber schöner.

F1) Sind negative Zahlen und die Zahlen 0,1 Primzahlen?
F2) Muss man gerade Zahlen > 2 nach dem ersten Test auch weiterhin als Teiler berücksichtigen? :p
A1) Nöööööö!
A2) Siehe A1

Big Brother schrieb:

F1) Sind negative Zahlen...

7 /-7=-1
7 / 7= 1
-7/-7= 1

wenns mal wieder länger dauert
http://de.wikipedia.org/wiki/Miller-Rabin-Test

lg lolo

noobLolo schrieb:

7 /-7=-1
7 / 7= 1
-7/-7= 1

Äh ... na und?
Ich wollte auf den unpassend gewählten Datentypen int hinaus.
Das hätte ich wohl dazu schreiben sollen

Eigentlich reicht es zuerst auf %2 zu prüfen und dann die zählvariable um 2 zu erhöhen (da alle geraden zahlen eh durch 2 teilbar sind).
dadurch spart man sich unnötige schleifendurchläufe.

bool isprime(int number)
{
    int limit = sqrt(number);

    if ( number % 2 == 0)
    {
        return false;
    }

    for (int i = 3; i <= limit; i=i+2)
    {
        if (number % i == 0)
        {
            return false;
        }
    }
    return true;
}

mngbd

o_O schrieb:

Eigentlich reicht es zuerst auf %2 zu prüfen und dann die zählvariable um 2 zu erhöhen (da alle geraden zahlen eh durch 2 teilbar sind).
dadurch spart man sich unnötige schleifendurchläufe.

Und was ist mit unnötigen Vielfachen von 3? Oder 5?

volkard

mngbd schrieb:

o_O schrieb:

Eigentlich reicht es zuerst auf %2 zu prüfen und dann die zählvariable um 2 zu erhöhen (da alle geraden zahlen eh durch 2 teilbar sind).
dadurch spart man sich unnötige schleifendurchläufe.

Und was ist mit unnötigen Vielfachen von 3? Oder 5?

Die 3 geht noch relativ leicht, zum Beispiel for(s=2,i=5;...;i+=s,s=6-s)
Mit der 5 muß man wohl schon ein Array benutzen. Es ist schwierig, abzuschätzen, wie weit man es treiben kann, ohne durcvh die Komplexität wieder langsamer zu werden.
Ist eigentlich for (int i = 3; i <= limit; i=i+2) besser als for (int i = 3; i*i <= number; i=i+2)? Sind es ausreichend viele Ausstiege bei kleinen i, so daß die teure Wurzel oft genug gespart wird?

so hätt ichs mal versucht

int isPrime(int num){
  if(num % 2 == 0
  || num % 3 == 0
  || num % 5 == 0)
    return 0;

  unsigned l = sqrt(num);
  l += 6 - l % 6;
  while(l-=6){
    if(num % (l+1) == 0
    || num % (l-1) == 0){
      return 0;
    }
  }
  return 1;
}

lg lolo

oOLolo schrieb:

unsigned isPrime(unsigned num){
...
}

o_O schrieb:

Eigentlich reicht es zuerst auf %2 zu prüfen und dann die zählvariable um 2 zu erhöhen (da alle geraden zahlen eh durch 2 teilbar sind).
dadurch spart man sich unnötige schleifendurchläufe.

Das wollte ich mit F2 ausgedrückt haben.
Und es muss number > 2 sein, weil 2 eine Primzahl ist.
und negative Zahlen, 0, 1 sind laut Definition keine Primdinger

Big Brother schrieb:

und negative Zahlen, 0, 1 sind laut Definition keine Primdinger

unsigned isPrime(unsigned num){
  if(num == 1
  || num % 2 == 0
  || num % 3 == 0
  || num % 5 == 0)
    return 0;
  {
    unsigned l = sqrt(num);
    l += 6 - l % 6;
    while(l-=6){
      if(num % (l+1) == 0
      || num % (l-1) == 0){
        return 0;
      }
    }
    return 1;
  }
}

lg lolo