## 14660Re: [PrimeNumbers] SEARCHING FOR A GOOD ALTERNATIVE

Expand Messages
• Mar 10, 2004
> From: H.BARGHOUT [mailto:hamedbar@...]
> i would like to ask if any body has a way to generate
> a sequence of numbers that containes all prime, faster
> than generating all odd number
>
> -----End Original Message-----
> Here are two algorithms to generate a sequence of numbers
> that contains all the primes. (both are wheel generators)
[snipped]

(Just having fun)
Below is a slightly obfuscated C wheel generator generator (no stuttering) .
Set m = largest prime used in the wheel.
The output is a C wheel generator.
m=3 and m=5 gives Hadley's two algorithms.

#include <stdio.h>
unsigned m=7,p,oldp=1,d,n,primor=1;
unsigned pn[1000];
main(void) {
printf("#include <stdio.h>\nunsigned n=1;\nmain(void){\n");
for (p=2;p<=m;p++) { /*print primes<=m*/
for (d=2;p%d;d++) ;
if (d==p) {
printf("printf(\"%u\\n\");\n",p);
pn[n++]=p;
primor*=p;
}
}
printf("for(;;) {\n");
for(p=m;p<=primor+m;p++) {
for(d=0;(d<n)&&(p%pn[d]);d++) ;
if (d==n) {
printf("n+=%2u; ",p-oldp);
printf("printf(\"%%u\\n\",n);\n",p);
oldp=p;
}
}
printf("}\nreturn 0;\n}\n");
return 0;
}

Here is the output for m=7, skipping numbers divisible by 2,3,5,7:

#include <stdio.h>
unsigned n=1;
main(void){
printf("2\n");
printf("3\n");
printf("5\n");
printf("7\n");
for(;;) {
n+=10; printf("%u\n",n);
n+= 2; printf("%u\n",n);
n+= 4; printf("%u\n",n);
n+= 2; printf("%u\n",n);
n+= 4; printf("%u\n",n);
n+= 6; printf("%u\n",n);
n+= 2; printf("%u\n",n);
n+= 6; printf("%u\n",n);
n+= 4; printf("%u\n",n);
n+= 2; printf("%u\n",n);
n+= 4; printf("%u\n",n);
n+= 6; printf("%u\n",n);
n+= 6; printf("%u\n",n);
n+= 2; printf("%u\n",n);
n+= 6; printf("%u\n",n);
n+= 4; printf("%u\n",n);
n+= 2; printf("%u\n",n);
n+= 6; printf("%u\n",n);
n+= 4; printf("%u\n",n);
n+= 6; printf("%u\n",n);
n+= 8; printf("%u\n",n);
n+= 4; printf("%u\n",n);
n+= 2; printf("%u\n",n);
n+= 4; printf("%u\n",n);
n+= 2; printf("%u\n",n);
n+= 4; printf("%u\n",n);
n+= 8; printf("%u\n",n);
n+= 6; printf("%u\n",n);
n+= 4; printf("%u\n",n);
n+= 6; printf("%u\n",n);
n+= 2; printf("%u\n",n);
n+= 4; printf("%u\n",n);
n+= 6; printf("%u\n",n);
n+= 2; printf("%u\n",n);
n+= 6; printf("%u\n",n);
n+= 6; printf("%u\n",n);
n+= 4; printf("%u\n",n);
n+= 2; printf("%u\n",n);
n+= 4; printf("%u\n",n);
n+= 6; printf("%u\n",n);
n+= 2; printf("%u\n",n);
n+= 6; printf("%u\n",n);
n+= 4; printf("%u\n",n);
n+= 2; printf("%u\n",n);
n+= 4; printf("%u\n",n);
n+= 2; printf("%u\n",n);
n+=10; printf("%u\n",n);
n+= 2; printf("%u\n",n);
}
return 0;
}

It has been tested and works.
The optimal m is machine and application dependent.
Printing takes far longer than adding in practice.
Besides, I suspect the original poster did not know what he really needed.
If the generated numbers are used for something where only primes were really
necessary, then only generating the primes with the sieve of Eratosthenes would
probably be much faster.

--
Jens Kruse Andersen
• Show all 5 messages in this topic