Primzahl Test

[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

[Big Brother]

noobLolo schrieb:

...		|| num % 41 == 0
        <--- 'Insertion mark'
		|| num % 47 == 0
...

Insert

|| num % 43 == 0

for(;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.

[kevinf]

Dieser Beitrag wurde gelöscht!

[kevinf]

Dieser Beitrag wurde gelöscht!