Primzahl Test

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

noobLolo schrieb:

Dein Code funzt leider nicht für gewisse Testkandidaten wie z.B. 11*11, 17*17, etc.

volkard schrieb:

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?

Du hast natürlich recht. Da ist dann halt die frage, ab wann es sich nichtmehr lohnt speziel drauf zu testen.
Aber: Jede 2. Zahl, die durch 3 Teilbar ist, ist auch durch 2 Teilbar. Dadurch wäre der nutzen der weiteren ausschliessung wohl geringer als bei der 2.
Müsste man mal durchrechnen...

Mal überlegen.. Nehmen wir als Beispiel mal eine Maximale größe von 1000.
Mit %2 schliesst man 50% aus. Bleiben 500.
Mit %3 schliesst man 3% aus. Davon sind die hälfte schon weg. Man schliesst also noch 16,7% aus. Bleiben 334 über (aufgerundet).
Pratisch. Man hat also trotz, das schon etliche weggefallen sind dem Aufwand um 1/3 Reduziert.
Ok, im Nachhinein betrachtet macht das auch Sinn. Das ist definitiv nicht meine Stärke ^^

Da muss man sich halt fragen, wie lange sich das trozdem noch lohnt..

Haki

erstmal danke ich jedem, der versucht mir zu helfen.
**1.)**aber das problem mit dem 7, d.h. die Zahl die mit 7 endet immer eine primzahl ist, habe ich immernoch, trotz "sqrt(Prim)" oder "Prim/2". die zahlen die mit 3 oder 9 enden geben auch dieselbe ausgabe aus. die funktion funzt irgendwie nicht richtig
**2.)**da die Bedingung 2 < (Prim/2) ist, verstehe ich nicht wie die Funktion die zahl 3 und die 4 überprüfen soll, ob es um eine Primzahl handelt oder nicht.

Haki schrieb:

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;
    }
}

Also, das ist durchaus ausbaufähig. Die Abbruchbedingungen müssten noch angepasst werden ( überleg doch mal warum ) und wenn du noch den einen oder anderen Tipp berücksichtigst, der hier genannt wurde, dann wird das schon ganz brauchbar.

neuer versuch neues glück

#include <stdio.h>
#include <math.h>

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

int main(void) {
	int l = 99992,ret;
	while(l--){
		if((ret = isPrime(l)))
			printf("%d\n",l);
	}
	return 0;
}

lg lolo

macht es sinn das switch so zu ändern

switch(num){
  default:
  case 1:
    return 0;
  case 2:
  case 3:
  case 5:
  case 7:
    return 1;
}

lg lolo

okay okay ich hör ja schon auf

#include <stdio.h>
#include <math.h>

unsigned isPrime(unsigned num){
	if(num > 10){
		if(num % 2 == 0
		|| num % 3 == 0
		|| num % 5 == 0
		|| num % 7 == 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;
	}

	switch(num){
		case 2:
		case 3:
		case 5:
		case 7:
			return 1;
		default:
			return 0;
	}
}

int main(void) {
	int l = 100,ret;
	while(l--){
		if((ret = isPrime(l)))
			printf("%d\n",l);
	}
	return 0;
}

lg lolo

noobLolo schrieb:

macht es sinn das switch so zu ändern

Nö.