Primzahl Test

[oOLolo]

oOLolo schrieb:

unsigned isPrime(unsigned num){
...
}

[Big Brother]

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

[noobLolo]

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

[Big Brother]

noobLolo schrieb:

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

[o_O]

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.

[Big Brother]

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.

[noobLolo]

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

[noobLolo]

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

[noobLolo]

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

[Big Brother]

noobLolo schrieb:

macht es sinn das switch so zu ändern

Nö.

[whynot]

Big Brother schrieb:

noobLolo schrieb:

macht es sinn das switch so zu ändern

Nö.

wiesonichit, funzt doch

[Big Brother]

Ist das jetz ne Fangfrage?
Tjaaa, weil sich für eine handvoll Primzahlen, hier bis 100, solch ein Aufwand wohl kaum lohnt und weil der Algorithmus für Zahlen > 100 seltsame noobLolo-primes wie z.B. 121 ermittelt. :p

[volkard]

noobLolo schrieb:

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

Oh Herr, schenke ihm ein Array. Und sei es auch nur ein kleines Stringliteral.

[noobLolo]

langsam wirds peinlich

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

unsigned isPrime(unsigned num){
	if(num > 0xFF){
		if(num % 2 == 0
		|| num % 3 == 0
		|| num % 5 == 0
		|| num % 7 == 0
		|| num % 11 == 0
		|| num % 13 == 0
		|| num % 17 == 0
		|| num % 19 == 0
		|| num % 23 == 0
		|| num % 29 == 0
		|| num % 31 == 0
		|| num % 37 == 0
		|| num % 41 == 0
		|| num % 47 == 0
		|| num % 53 == 0
		|| num % 59 == 0
		|| num % 61 == 0
		|| num % 67 == 0
		|| num % 71 == 0
		|| num % 73 == 0
		|| num % 79 == 0
		|| num % 83 == 0
		|| num % 89 == 0
		|| num % 97 == 0)
			return 0;

		unsigned l = 102, ll = sqrt(num)+1;
	    for(;l <= ll;l+=6){
		    if(num % (l+1) == 0
		    || num % (l-1) == 0)
		    	return 0;
	    }
		return 1;
	}
	return "\x00"
	"\x00\x01\x01\x00\x01\x00\x01\x00\x00\x00"
	"\x01\x00\x01\x00\x00\x00\x01\x00\x01\x00"
	"\x00\x00\x01\x00\x00\x00\x00\x00\x01\x00"
	"\x01\x00\x00\x00\x00\x00\x01\x00\x00\x00"
	"\x01\x00\x01\x00\x00\x00\x01\x00\x00\x00"
	"\x00\x00\x01\x00\x00\x00\x00\x00\x01\x00"
	"\x01\x00\x00\x00\x00\x00\x01\x00\x00\x00"
	"\x01\x00\x01\x00\x00\x00\x00\x00\x01\x00"
	"\x00\x00\x01\x00\x00\x00\x00\x00\x01\x00"
	"\x00\x00\x00\x00\x00\x00\x01\x00\x00\x00"
	"\x01\x00\x01\x00\x00\x00\x01\x00\x01\x00"
	"\x00\x00\x01\x00\x00\x00\x00\x00\x00\x00"
	"\x00\x00\x00\x00\x00\x00\x01\x00\x00\x00"
	"\x01\x00\x00\x00\x00\x00\x01\x00\x01\x00"
	"\x00\x00\x00\x00\x00\x00\x00\x00\x01\x00"
	"\x01\x00\x00\x00\x00\x00\x01\x00\x00\x00"
	"\x00\x00\x01\x00\x00\x00\x01\x00\x00\x00"
	"\x00\x00\x01\x00\x00\x00\x00\x00\x01\x00"
	"\x01\x00\x00\x00\x00\x00\x00\x00\x00\x00"
	"\x01\x00\x01\x00\x00\x00\x01\x00\x01\x00"
	"\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
	"\x01\x00\x00\x00\x00\x00\x00\x00\x00\x00"
	"\x00\x00\x01\x00\x00\x00\x01\x00\x01\x00"
	"\x00\x00\x01\x00\x00\x00\x00\x00\x01\x00"
	"\x01\x00\x00\x00\x00\x00\x00\x00\x00\x00"
	"\x01\x00\x00\x00\x00"[num];
}

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

lg lolo

[volkard]

unsigned isPrime(unsigned num){
	if(num > 97*97){//oder 101*101-1?
//...
		|| num % 97 == 0)
			return 0;

[noobLolo]

volkard schrieb:

unsigned isPrime(unsigned num){
	if(num > 97*97){//oder 101*101-1?
//...
		|| num % 97 == 0)
			return 0;

stimmt das wär natürlich schon sinnvoll. dann sollte man aber evtl. lieber ein bitfield nehmen, sonst wird das ein bischen zu wuchtig, da ja die lookuptable bis 97*97 gehen müßte oder

lg lolo

[volkard]

noobLolo schrieb:

volkard schrieb:

unsigned isPrime(unsigned num){
	if(num > 97*97){//oder 101*101-1?
//...
		|| num % 97 == 0)
			return 0;

stimmt das wär natürlich schon sinnvoll. dann sollte man aber evtl. lieber ein bitfield nehmen, sonst wird das ein bischen zu wuchtig, da ja die lookuptable bis 97*97 gehen müßte oder
lg lolo

Nein. Die Tabelle darf doch klein bleiben. Denn die Schleife tut ja bei kleinen Werten nicht falsch sein sollen.
Vielleicht auch was:

if(num<32) return getBit(UInt32(/*HabDieZahlNicht*/),p);
if(num%2==0) return false;
if(num%3==0) return false;
if(num%5==0) return false;

if(num<7*7) return true;
if(num%7==0) return false;
if(num<11*11) return true;
if(num%11==0) return false;
...
if(num<31*31) return true;
if(num%31==0) return false;

//hier die Schleife

[SalmoGairdnerii]

bool isPrime(unsigned number){
 unsigned i = 2;
 unsigned max = number << 1;
 if(number < 2)
  return false;
 if(max == 1)
  return true;
 do{
  if(!(number % i))
   return false;
 }while(++i < max);
 return true;
}

[SalmoGairdnerii]

SalmoGairdnerii schrieb:

[cpp]
bool isPrime(unsigned number){
unsigned i = 2;
unsigned max = number >> 1; /* Andere Richtung schieben */
if(number < 2)
return false;
if(max == 1)
return true;
do{
if(!(number % i))
return false;
}while(++i < max);
return true;
}
[/cpp]

Kleine Korrektur