Sorry, an error occurred while loading the content.

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

Expand Messages
• ... Oh good, a question that doesn t involve elliptical curves. :) I hope I can adequately answer it. The sequence of odd numbers does not contain all primes.
Message 1 of 5 , Mar 10, 2004
At 06:06 AM 3/10/04 -0800, H.BARGHOUT wrote:
>Hi all
>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

Oh good, a question that doesn't involve elliptical curves. :) I hope I

The sequence of odd numbers does not contain all primes. There's one
prime not included, the even number 2. I know that's just a detail, but
mathematics people are sticklers for detail. :)

There's the 'wheel' which is a method for efficiently storing
consecutive primes, that I think might be what you're looking for. Here's
an earlier message about it (I've posted this link before, I think it's
really neat):

This misses the earliest primes in the first 'rotation' of the wheel,
but as that message says, you already 'know' that they are prime. Rotating
this 'wheel' may or may not be faster than incrementing an odd number by 2
(going through all the odd numbers), depending on implementation. Actually,
going through the odd numbers is effectively using a wheel of length 2. A
wheel of any size appears to be linear processes (increasing the range of
numbers they go over increases the time it takes in direct proportion), so
in the realm of algorithms, these both take the same amount of time.

>thank you in advance

---
• ... From: H.BARGHOUT [mailto:hamedbar@yahoo.com] Sent: Wednesday, March 10, 2004 8:07 AM To: primenumbers@yahoogroups.com Subject: [PrimeNumbers] SEARCHING FOR
Message 2 of 5 , Mar 10, 2004
-----Original Message-----
From: H.BARGHOUT [mailto:hamedbar@...]
Sent: Wednesday, March 10, 2004 8:07 AM
Subject: [PrimeNumbers] SEARCHING FOR A GOOD ALTERNATIVE

Hi all
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
thank you in advance

-----End Original Message-----
Here are two algorithms to generate a sequence of numbers
that contains all the primes. (both are wheel generators)

print 2
print 3
n=5
for( ever )
print n
n = n+2
print n
n = n+4
end for

Or with a bigger wheel:
print 2
print 3
print 5
n=7
for( ever )
print n
n = n+4
print n
n = n+2
print n
n = n+4
print n
n = n+2
print n
n = n+4
print n
n = n+6
print n
n = n+2
print n
n = n+6
end for
• I suppose it s worth asking whether the original poster wanted a sequence that contained all the prime numbers, or a sequence that consisted entirely of prime
Message 3 of 5 , Mar 10, 2004
I suppose it's worth asking whether the original poster wanted a sequence that
contained all the prime numbers, or a sequence that consisted entirely of prime
numbers but doesn't necessarily contain all of them.

"Hadley, Thomas H (Tom), ALABS" wrote:
>
> -----Original Message-----
> From: H.BARGHOUT [mailto:hamedbar@...]
> Sent: Wednesday, March 10, 2004 8:07 AM
> Subject: [PrimeNumbers] SEARCHING FOR A GOOD ALTERNATIVE
>
> Hi all
> 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
> thank you in advance
>
> -----End Original Message-----
> Here are two algorithms to generate a sequence of numbers
> that contains all the primes. (both are wheel generators)
>
> print 2
> print 3
> n=5
> for( ever )
> print n
> n = n+2
> print n
> n = n+4
> end for
>
> Or with a bigger wheel:
> print 2
> print 3
> print 5
> n=7
> for( ever )
> print n
> n = n+4
> print n
> n = n+2
> print n
> n = n+4
> print n
> n = n+2
> print n
> n = n+4
> print n
> n = n+6
> print n
> n = n+2
> print n
> n = n+6
> end for
>
> Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
> The Prime Pages : http://www.primepages.org/
>
>
> Yahoo! Groups Links
>
>
>
>

-- Dan Morenus (dmorenus@...)

-- This parachute is not warranted to be suitable --
-- for any purpose, including descending safely --
-- from an airplane to the ground. --
• ... [snipped] (Just having fun) Below is a slightly obfuscated C wheel generator generator (no stuttering) . Set m = largest prime used in the wheel. The
Message 4 of 5 , Mar 10, 2004
Thomas H Hadley wrote:
> 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
> thank you in advance
>
> -----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
Your message has been successfully submitted and would be delivered to recipients shortly.