- 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

__________________________________

Do you Yahoo!?

Yahoo! Search - Find what you�re looking for faster

http://search.yahoo.com - At 06:06 AM 3/10/04 -0800, H.BARGHOUT wrote:
>Hi all

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

>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

can adequately answer it.

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):

http://groups.yahoo.com/group/primenumbers/message/10491

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

---

http://mindspring.com/~benbradley - -----Original Message-----

From: H.BARGHOUT [mailto:hamedbar@...]

Sent: Wednesday, March 10, 2004 8:07 AM

To: primenumbers@yahoogroups.com

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

numbers but doesn't necessarily contain all of them.

"Hadley, Thomas H (Tom), ALABS" wrote:>

-- Dan Morenus (dmorenus@...)

> -----Original Message-----

> From: H.BARGHOUT [mailto:hamedbar@...]

> Sent: Wednesday, March 10, 2004 8:07 AM

> To: primenumbers@yahoogroups.com

> 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

>

>

>

>

-- This parachute is not warranted to be suitable --

-- for any purpose, including descending safely --

-- from an airplane to the ground. -- - Thomas H Hadley wrote:
> From: H.BARGHOUT [mailto:hamedbar@...]

[snipped]

> 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)

(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