Primzahl Test
-
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.
-
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
-
unsigned isPrime(unsigned num){ if(num > 97*97){//oder 101*101-1? //... || num % 97 == 0) return 0;
-
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
-
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 loloNein. 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
-
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 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
-
noobLolo schrieb:
... || num % 41 == 0 <--- 'Insertion mark' || num % 47 == 0 ...Insert
|| num % 43 == 0for(;l <= ll;l+=6){ if(num % (l+1) == 0 || num % (l-1) == 0) return 0; }Wie kommst du eigentlich darauf? Kann ich z.Zt. nicht nachvollziehen.
Wird das Sieb bei großen Zahlen nicht irgendwann mal zu grobmaschig?Gruß,
B.B.
-
Dieser Beitrag wurde gelöscht!
-
Dieser Beitrag wurde gelöscht!