Someone once posted a link to a list of the primary numbers but i think its long gone from the board.

I searched the board and googled but can,t find anything.

I only need about the first hundred or so for my purposes so if anyone can help me out ...thanx.

:alright:

I searched the board and googled but can,t find anything.

I only need about the first hundred or so for my purposes so if anyone can help me out ...thanx.

:alright:

Maybe the reason Google can't find it is because you're using the wrong terminology. I've never heard of primary numbers. I've heard prime numbers referred to as primary though.

Describe what you mean... ?

Describe what you mean... ?

Maybe the reason Google can't find it is because you're using the wrong terminology. I've never heard of primary numbers. I've heard prime numbers referred to as primary though.

Describe what you mean... ?

Thanx for the hint iblis.

Got what i was looking for as soon as i changes primary to "prime" on a google.

But i have heard of them referred to as "primary" numbers.

:alright:

if you need a list of primes up to about #1-7568389, i made a program that preforms a calculation on a number to see if its prime. there are currently 481786 primes in the file.

Here's a file I created back in 2001. It has 1 to 999983.

2001!?

my prime project is ongoing. my objective is to compile a complete list of primes #1 to (2~31)-1 and in the future (2~31)-1 to (2~63)-1.

as of now im currently at #7,661,099 and increasing by about 5000 by the time i finish this message. my computer is not dedicated to this, however if you would like to contribute your cpus idle time to this project just email/pm me and i can set you up with the program/source and ill give you a block of primes to do say 10,000,001 to 11,000,001 etc if more people opt to help me!

my prime project is ongoing. my objective is to compile a complete list of primes #1 to (2~31)-1 and in the future (2~31)-1 to (2~63)-1.

as of now im currently at #7,661,099 and increasing by about 5000 by the time i finish this message. my computer is not dedicated to this, however if you would like to contribute your cpus idle time to this project just email/pm me and i can set you up with the program/source and ill give you a block of primes to do say 10,000,001 to 11,000,001 etc if more people opt to help me!

Our ECE 'DSP' lab is, uh, willing to lend some computer time on the P3's we're using... ;)

'Course when our research project is finished, say bye-bye....!

Maybe you should make it into a screen saver too (:tongue: :tongue: :grin: ).

'Course when our research project is finished, say bye-bye....!

Maybe you should make it into a screen saver too (:tongue: :tongue: :grin: ).

you would be willing to help me!!????, pm me about it for confirmation.

7666999 is Prime heh

7666999 is Prime heh

And umm, what will you do with all those prime numbers when you're done?

**Qages**, with a sieve you should be able to finish numbers up to 16 times availible memory in a single day. :) I have 512 megs and could easily compute all numbers up to billion+. How would you like the output?

how is this possible?, right now one takes just over a second to compute one and uses no memory, well about 20 bytes,maby. do you have any code examples of this sieve i could use in my program?

8000009 is prime!

8000009 is prime!

alright.i have the first 4 bytes after the routine is finished. and the biniary. here are some calculations. i have had to add 3, then one then 3 then 1 etc. there must be some error!

B7 6D 5A B2

B7=10110111 6D=1101101

1*2+3=5

3*2+1=7

4*2+3=11

6*2+1=13

7*2+3=17

8*2+3=19

9*2+5=23

10*2+8=31

12*2+3=

13*2+3=

15*2+3=

------------------------

0*2+3=3

2*2+1=5

3*2+1=7

5*2+1=11

6*2+1=13

7*2+3=17

8*2+3=19

9*2+5=23

11*2+9=31

12*2+13=37

14*2+13=41

8053931 is prime btw

B7 6D 5A B2

B7=10110111 6D=1101101

1*2+3=5

3*2+1=7

4*2+3=11

6*2+1=13

7*2+3=17

8*2+3=19

9*2+5=23

10*2+8=31

12*2+3=

13*2+3=

15*2+3=

------------------------

0*2+3=3

2*2+1=5

3*2+1=7

5*2+1=11

6*2+1=13

7*2+3=17

8*2+3=19

9*2+5=23

11*2+9=31

12*2+13=37

14*2+13=41

8053931 is prime btw

```
; set all bits in buffer
```

; assume all numbers are prime

mov ecx, MAX_BITS/32

or eax, -1

push edi

rep stosd

pop edi

xor ecx, ecx

; 0 1 2 3 4 5 6 7 8 9 10 11 ... | bit index

;-----------------------------------------|

; 3 5 7 9 11 13 15 17 19 21 23 25 ... | (N)

; 9 15 21 27 33 39 45 51 57 63 69 75 ... | 3(N)

; 15 25 35 45 55 65 75 85 95 ... | 5(N)

; find first set bit

__0: bt [edi], ecx

inc ecx

jnc __0

; ECX*2 + 1 is prime number (P)

; 2(P) is even - skip even numbers

; number 3(P) is represented by bit 3: ECX*3

; number 5(P) is represented by bit 6: ECX*5 + 1

; number 7(P) is represented by bit 9: ECX*7 + 2

; number x(P) = bit y: ECX * x + [(x-3)/2]

; start with (P)^2 as first odd multiple to mark

; as non-prime: all others have been marked

lea eax, [ecx*2]

mul ecx

lea eax, [eax + ecx*2 - 1]

; exit it out of range

cmp eax, MAX_BITS

jnc __x

; clear bits representing odd multiples of (P)

__2: btr [edi], eax

lea eax, [eax + ecx*2 + 1]

cmp eax, MAX_BITS

jc __2

; inc ecx

jns __0

__x:

; Output Primes:

; count number of primes

xor ebx, ebx

xor esi, esi

__8: cmp ebx, MAX_BITS

jnc __y

bt [edi], ebx

inc ebx

jnc __8

inc esi

jmp __8

__y:

shl esi, 2 ; DWORD per prime

invoke GetProcessHeap

invoke HeapAlloc, eax,

HEAP_ZERO_MEMORY or HEAP_GENERATE_EXCEPTIONS,

esi ; bytes needed

mov esi, eax

push eax

xor ebx, ebx

; find first set bit

__9: cmp ebx, MAX_BITS

jnc __z

bt [edi], ebx

inc ebx

jnc __9

lea eax, [ebx*2 + 1] ; prime number

mov [esi], eax

add esi, 4

jmp __9

__z:

pop esi

invoke GetProcessHeap

invoke HeapFree, eax, NULL, esi

All the prime up to 2^24 in 783ms!
1,077,870 primes (16,777,213 is prime) :)

All primes up to 2^30 (over one billion!) in 86 seconds!!!

(Only 32 seconds on an XP2800+, Dual DDR.)

54,400,027 primes (

**1,073,741,789**is prime) :)

:grin: :grin:

*Verified the code. Not counting the number 2.*

*Algorithm only good to 2^31 until I get my Opteron.*

what would i need to change to be able to do say 2^33? and beyond, alot of disk paging will be probly needed, but where eaxtly would it be needed.? or can it be done in sections? say, i have about 256mb of ram free if I dont have much open, or does it need all numbers below it to be there??? of cource id have to look at the algo and improve apon it, i have a habit of askin someting before i go out to find it myself. but prior feedback would be helpfull. and thanks for your effort!

**Qages**, this algorithm takes advantage of the x86 bit array instructions - they only work between -2^31 and 2^31 - 1. With some work I think you could adapt the algorithm to be effective for the full range = 2^32 -1 bits; since each bit represents two numbers (ignore even numbers), you could reach 2^33 - 1.

Another option that I explored before was to not include multiples of three (similar to not including multiples of two), but this gets harder and doesn't have as great a return (1/3 less bits needed, 1/5 less bits needed, etc.) Memory is not as much a concern as it used to be.

What is nice about having all this primes, and having them fast to calculate -- you can quickly test bigger numbers against 54 million primes to increase the changes that it is prime - better than testing 1 billion numbers! Use many methods together.

Also, note that 54 million primes takes 4*54 million bytes to store as DWORDs, but the bit array used above to calculate the 54 million primes is only 64MB - do not convert them to numbers - keep them in the bit array if used in another program.

I have does this algorithm over a dozen times in many languages. :)

you mean x86-32, what about x86-64? i assume the bt etc will be increased to b4 bits too?

you mean x86-32, what about x86-64? i assume the bt etc will be increased to b4 bits too?

Memory is the limit there, or pagefile for the crazy people. :)

http://www.utm.edu/research/primes/largest.html

__Lists of primes__:

http://www.utm.edu/research/primes/lists/small/

Here is a cool page to confirm primes:

http://www.rsok.com/~jrm/printprimes.html

Also, read the begining of the page to learn how to pack primes. We could make a program in ASM that operates on the packed data (similar to what I stated above).

Why do you want all the primes? There are other methods that work for very large numbers - I don't have any experiece with them, but I know they are out there. Good Luck! :)

i don't want nessasarly the single largest, but i want a list of all primes (1 to whatever the largest is possible, i have about 300 gigz of freespace now heh.) i have a whole lot of reasons(and uses) for this, one for encription, and well many more i havent really thought of heh.

There is a cool algorithm on the page I posted above. I might do an ASM version for fun. Stores 38.5 integers per byte! Mine only does 16. :( 256MB would be good for 10,334,765,056 numbers. :) 128GB would be good for 5,291,399,708,672 numbers (less than 2^43). I think you could do it in under a year.

So, you could be known as the prime repository for the world. I think it is fairly easy to test a number under 2^64 for primeness, but there are surely people that would need a list of primes for an interval. As technology increases, you would just increase your list. And the growth of the list could be a measure of the security of algorithms based on primes.

So, you could be known as the prime repository for the world. I think it is fairly easy to test a number under 2^64 for primeness, but there are surely people that would need a list of primes for an interval. As technology increases, you would just increase your list. And the growth of the list could be a measure of the security of algorithms based on primes.

Please excuse my posting an inferior algorithm...

Create a table of primes...

A(x,0)=x+1 th prime

A(x,1)=next odd number divisible by A(x,0)

start

2 (x=0)

3 (x=1)

m=# primes

n=# being checked

counting n in twos beginning at 5,

x=1 to m-1

if n<=A(x,1), then A(x,1)=A(x,1)+2*A(x,0); flag=1

next x

if flag=0 then A(m,0)=n; A(m,1)=n*3; m=m+1;

next n

The programs check and store primes up to the size of array (mx) or memory allocated (memtoalloc). They could do with some optimization... 16384 primes found in 4 seconds on a Pentium III. But it's a non-optimal algorithm anyway...

Please contact me with changes...

BASIC and HLA (Assembly) source code and executable included.

Create a table of primes...

A(x,0)=x+1 th prime

A(x,1)=next odd number divisible by A(x,0)

start

2 (x=0)

3 (x=1)

m=# primes

n=# being checked

counting n in twos beginning at 5,

x=1 to m-1

if n<=A(x,1), then A(x,1)=A(x,1)+2*A(x,0); flag=1

next x

if flag=0 then A(m,0)=n; A(m,1)=n*3; m=m+1;

next n

The programs check and store primes up to the size of array (mx) or memory allocated (memtoalloc). They could do with some optimization... 16384 primes found in 4 seconds on a Pentium III. But it's a non-optimal algorithm anyway...

Please contact me with changes...

BASIC and HLA (Assembly) source code and executable included.

```
```

mx=1000

dim a(mx,1)

cls

Print"Searching for primes..."

print"2":a(0,0)=2

print"3":a(1,0)=3:a(1,1)=3*3

m=2:n=5

n1:

f=0

for j=m-1 to 1 step -1

if n>=a(j,1) then a(j,1)=a(j,1)+2*a(j,0):f=1

next j

if f=0 then A(m,0)=n:A(m,1)=n*3:m=m+1:'print m"th prime is"n

if m<1000 then n=n+2:goto n1

print m"primes found"

```
```

// **********************************

// Prime Numbers Search Program

// Coded using HLA

//

// **********************************

program primes;

#include( "stdlib.hhf" );

const

memtoalloc :=$2000;

static (4)

memaddr: pointer to byte;

numprimes: int32:=2 * 8; // 2 primes found so far

number: int32:=3;

flag: int32;

t:time.timerec;

begin primes;

console.cls();

console.gotoxy(4, 15);

stdout.put ( "Primes Search Program.", nl);

console.gotoxy(5, 15);

stdout.put ( " Coded using HLA", nl, nl);

stdout.put ( "Initializing memory. Initial Time: ");

time.curTime(t);

stdout.puti16Size(t.hours, 2, '0'); stdout.put(':');

stdout.puti8Size(t.mins, 2, '0'); stdout.put(':');

stdout.puti8Size(t.secs, 2, '0');

// Allocate RAM; On return EAX contains address;

malloc (memtoalloc);

// Store memory address

mov (eax, memaddr);

// Clear memory

mov (memaddr, esi);

xor (eax, eax); // Fill mem with 0

mov (memtoalloc, ecx);

sub (4, ecx);

clm1:

mov (edx, [esi+ecx]);

sub (4, ecx);

jns clm1;

// Commencing Message

stdout.put ( nl, nl,"Commencing Search. Time: ");

time.curTime(t);

stdout.puti16Size(t.hours, 2, '0'); stdout.put(':');

stdout.puti8Size(t.mins, 2, '0'); stdout.put(':');

stdout.puti8Size(t.secs, 2, '0'); stdout.put(nl);

// Check clocks

rdtsc; // First measure of time

// rdtsc takes 13 cycles on Pentium MMX,

push (edx); // I store the 64 bit cycle count on the stack.

push (eax);

mov (memaddr, esi);

mov (2, eax);

mov (eax, [esi+4]);

mov (3, eax);

mov (eax, [esi+12]);

lea (edx, [eax+eax*2]);

mov (edx, [esi+8]);

mov (number, eax);

nx:

mov (numprimes, ecx);

nx_:

sub (8, ecx);

xor (ebx, ebx); // flag

add (2, eax);

nxj:

cmp (eax, [esi+ecx]);

jb nxk;

mov ([esi+ecx+4], edx);

lea (edx, [edx*2]);

add (edx, [esi+ecx]);

mov (1, ebx);

nxk:

sub (8, ecx);

jne nxj;

or (ebx, ebx);

jne nx;

mov (numprimes, ecx);

mov (eax, [esi+ecx+4]);

lea (edx, [eax*2]);

mov (edx, [esi+ecx]);

// stdout.put((type uns32 eax), nl);

add (8, ecx);

mov (ecx, numprimes);

cmp (ecx, memtoalloc);

jne nx_;

mov (eax, number);

// Check clocks

rdtsc; // Second measure of time

push (edx);

push (eax);

// Completion Message

stdout.put ( nl, nl,"Search Stopped at Time: ");

time.curTime(t);

stdout.puti16Size(t.hours, 2, '0'); stdout.put(':');

stdout.puti8Size(t.mins, 2, '0'); stdout.put(':');

stdout.puti8Size(t.secs, 2, '0');

// Report

mov (ecx, numprimes);

shr (3, ecx);

stdout.put (nl, (type uns32 ecx), " Primes found in ");

// Retrieve 2nd rdtsc

pop (eax);

pop (edx);

sub ([esp], eax); // subtract first from second

sbb ([esp+4],edx); // result in EDX:EAX

add (8, esp); // remove first edx, eax from stack

if (edx=0) then

stdout.putu32(eax);

stdout.put(" clock cycles = ", nl);

else

stdout.put ("$",edx," ",eax, " clock cycles = ", nl);

endif;

end primes;