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:
Posted on 2003-05-15 18:40:09 by IwasTitan
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... ?
Posted on 2003-05-15 18:49:47 by iblis

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:
Posted on 2003-05-15 22:58:00 by IwasTitan
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.
Posted on 2003-05-15 23:57:55 by Qages
Here's a file I created back in 2001. It has 1 to 999983.
Posted on 2003-05-18 03:47:12 by eet_1024
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!
Posted on 2003-05-18 22:08:12 by Qages
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: ).
Posted on 2003-05-18 22:11:00 by AmkG
you would be willing to help me!!????, pm me about it for confirmation.

7666999 is Prime heh
Posted on 2003-05-18 22:16:33 by Qages
And umm, what will you do with all those prime numbers when you're done?
Posted on 2003-05-18 22:58:37 by iblis
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?
Posted on 2003-05-19 01:00:53 by bitRAKE
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!
Posted on 2003-05-19 14:55:17 by Qages
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
Posted on 2003-05-19 20:51:14 by Qages
	; 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.*
Posted on 2003-05-19 22:12:17 by bitRAKE
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!
Posted on 2003-05-19 22:31:12 by Qages
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. :)
Posted on 2003-05-19 22:47:09 by bitRAKE
you mean x86-32, what about x86-64? i assume the bt etc will be increased to b4 bits too?
Posted on 2003-05-19 22:58:34 by Qages

you mean x86-32, what about x86-64? i assume the bt etc will be increased to b4 bits too?
Yes, AMD extended them for 64-bit mode!
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! :)
Posted on 2003-05-19 23:04:50 by bitRAKE
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.
Posted on 2003-05-19 23:17:26 by Qages
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.
Posted on 2003-05-19 23:31:38 by bitRAKE
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.



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;
Posted on 2003-05-20 01:12:21 by V Coder