Counting primes has already been done upto 4.10^22=2^75 !
http://numbers.computation.free.fr/Constants/Primes/Pix/pixproject.html

Also, a very fast Eratosthenes algorithm has been designed by Achim Flammenkamp.
http://wwwhomes.uni-bielefeld.de/achim/prime_sieve.html
His C code is able to count all primes upto 2^32 in 3.5 minutes on a P133 !

If you really want to search for something new, try:
http://www.primepuzzles.net
which proposes interesting weekly challenges to code about prime numbers.

JC
Posted on 2003-05-20 14:50:18 by MCoder
hahaha, ha hahaha. took me 30 seconds to compute 3 to 8128129, took me combined(estimated) 3 weeks with modulo compare.

btw 4,399,999,991 is prime
with this

ftp://ftp.rsok.com/pub/source/sieve2310_64bit.c

looks like that algo in the .c can be approved apon. 1 to 4,399,999,991 is about 299mb, winzip compressed to 243mb
Posted on 2003-05-20 18:51:31 by Qages
bitRAKE, nice code.

Can we get away from the Sieve based algos and head more toward the N^2 based ones?
Posted on 2003-05-22 07:55:49 by Homer
EvilHomer2k, sure, like what?
Posted on 2003-05-22 08:40:09 by bitRAKE
EvilHomer2k: if you need to check for primeness, try the chinese remainder algorithm to quickly detect if a number is composite (non-prime), instead of doing dumb divisions.
I think someone on this board is able to write a very efficient version of this algorithm.

JC
Posted on 2003-05-22 08:44:49 by MCoder
I was able to quickly write an algo to test for possible Mersenne primes below N < 2^31 using the algo above for primes. I have tested all prime N, (2^N - 1) for factoring by all prime numbers < N. Now I just need to reduce the list further.
Posted on 2003-05-22 19:54:26 by bitRAKE
Mersenne primes have already been exhaustively explored upto 2^7000000 !
http://www.mersenne.org
Prime95 is a wonderful tool for factoring and finding such primes.
I spent some YEARS of factoring on this project before starting my own, but I'm still impressed by its ASM implementation (FFT, P-1, ECM, etc...).
I strongly encourage you to try to devote your time to other prime problems, since this subject has been already explored A LOT.
This is why I suggested the www.primepuzzles.net page, which contains new problems, or records to break.

Other interesting projects are ECMNET or NFSNET which try to factor numbers with more than 300 digits (!).

About primality proving, chinese remainder theorem is a fast technique to determine if a number is composite. If the test finds 1, you have to use other techniques to check if the number is prime, and testing small divisors is the slowest of all possible techniques (even in ASM). If you don't believe me, try to factor a 50 digits number !

JC
Posted on 2003-05-23 02:42:16 by MCoder
MCoder, thanks for the help. I'm aware of Prime95 and I'm just exploring some of the research that has been done. I have begun to explore up to 2^(2^31) -- just simple pruning of the possible primes. I have no plans on trying to factor large numbers by simple division.
Posted on 2003-05-23 08:34:35 by bitRAKE
bitRake, I referred to the sieve of arosthenes (?) variant you posted in this thread - the 2^N stuff...
I was wondering if anyone had a go at the algo proposed by the Indian guy (no idea about the name) who proposed an effiecient probability-based way of calulating all the primes in a given RANGE, and provided a way of estimating the Time it would take.
There's some really neat ranged variants of the Sieve out there but I was hoping to get away from that line of thought entirely.
Posted on 2003-05-25 11:20:44 by Homer
I thought that the "Indian guy" found a way to test a number for primality with 100% accuracy. As I understand it, there is a method that is faster but sometimes (rarly) reports the wrong result.
Posted on 2003-05-25 15:38:42 by gliptic
@Gliptic,

yes they algo is faster in theory but very very slow in practice, or in other words: today inpracticable. The problem with it is the fact that today nobody known how to work with large modular polynomials in a very fast manner. To remeber they method need an modular Polynom exponetation with polynoms as base. For larger numbers the count of the needed coefficients of these polynoms are very big.
A good ECM, elliptic curve method, is magnitudes faster.

The two question with finding primes are:
Want we to check only some numbers for primality, or
want we to compute and count all succesive primes.

For the first case i have some stuff that checks number upto 2^32-1 in only about 1200 cylces.
The trick is we dont need to factorize such numbers or to use chineese remainders, because other nice peoples have counted all Strong Provable Primes upto certain bounds. So we have to check such numbers upto 2^32-1 only with a Strong Pseudo Prime Test (most called Rabin Miller Test) with fixed bases 2,7,61 if the Number is smaller as 4759123141. If these three combined test don't fail then it is fact that the tested number must be prime, because all numbers upto this bound have been tried today.

For the second case upto 2^32-1 my 8/30 comp sieve implementation compute all 203.280.221 primes upto 2^32-1 in about 28 seconds on a P4 1.5GHz. On this computation we produce a binary file of 138Mb on disk that holds all these primes. This file can be used for random access to all these primes, in average 1-2 ms are needed for each number to test.

Hagen
Posted on 2003-06-08 18:38:21 by Hagen
hm, i have written this for a contest, this program checks for a prime number and
prints out, if it is prime. If not, it shows you the divisor and the time needed for the calculation...

this algo is not very good, but on my 500Mhz K62 i need about 1 ms to check every number up to 2^32 (tested with a prime 2147483647)
``````TestIt proc hWnd:DWORD

invoke timeGetTime

mov Time1,eax
xor eax,eax
xor ebx,ebx
xor edx,edx
xor ecx,ecx
mov falsch,0

;ALGO
mov eax,DWORD ptr[Zahl]
mov ecx,eax
mov ebx,2
div ebx
test edx,1
je KEINE_PRIMZAHL

fninit
fild Zahl
fsqrt
fistp Zahl ;fist akzeptiert nur 16,32 bit
mov esi,DWORD ptr[Zahl]
inc esi
dec ebx
_LOOP:
mov eax,ecx
xor edx,edx
add ebx,2	;immer die ungeraden Zahlen nehmen
cmp ebx,esi ;sind wir schon bei der Wurzel?
jge WEITER ;wenn ja, dann ist schl?ss
div ebx ;ansonsten teilen
cmp edx,0 ;wenn kein Rest da ist != Primzahl
je KEINE_PRIMZAHL
jmp _LOOP

KEINE_PRIMZAHL:

mov falsch,1
jmp WEITER

;ALGOENDE

WEITER:
invoke timeGetTime

sub eax,Time1
invoke wsprintf,offset Ausgabe_buffer,offset Ausgabe_template,eax
invoke wsprintf,offset Ausgabe_buffer2,offset Teilbar_template,ebx

ret
TestIt endp
``````
Posted on 2003-06-29 13:56:48 by CDW
``````
mov eax,DWORD ptr[Zahl]
mov ecx,eax
mov ebx,2
div ebx
test edx,1
je KEINE_PRIMZAHL
``````

Should be faster if you use
``````
mov eax, dword ptr [Zahl]
mov ecx, eax
shr eax, 1
jnc KEINE_PRIMZAHL
sub ebx, ebx
inc ebx
``````

Anyway no need to clear eax, ecx, edx and ebx at the start of the algo.

Just my thoughts. ;)
Posted on 2003-06-30 03:45:18 by roticv
``````

function IsPrime(N: Cardinal): Boolean; register;
// test if N is prime, do some small Strong Pseudo Prime test in certain bounds
// not PIC safe !!
asm
TEST  EAX,1	      // Odd(N) ??
JNZ   @@1
CMP   EAX,2	      // N == 2 ??
SETE  AL
RET
@@1:   CMP   EAX,73	      // N  < 73 ??
JB    @@C
JE    @@E	      // N == 73 ??
PUSH  ESI
PUSH  EDI
PUSH  EBX
PUSH  EBP
PUSH  EAX	      // save N as Param for @@5
LEA   EBP,[EAX - 1]    // M == N -1, Exponent
MOV   ECX,32	      // calc remaining Bits of M and shift M'
MOV   ESI,EBP
@@2:   DEC   ECX
SHL   ESI,1
JNC   @@2
PUSH  ECX	      // save Bits as Param for @@5
PUSH  ESI	      // save M' as Param for @@5
CMP   EAX,08A8D7Fh     // N >= 9080191 ??
JAE   @@3
// now if (N < 9080191) and SPP(31, N) and SPP(73, N) then N is prime
MOV   EAX,31
CALL  @@5	      // 31^((N-1)(2^s)) mod N
JC    @@4
MOV   EAX,73	      // 73^((N-1)(2^s)) mod N
PUSH  OFFSET @@4
JMP   @@5
// now if (N < 4759123141) and SPP(2, N) and SPP(7, N) and SPP(61, N) then N is prime
@@3:   MOV   EAX,2
CALL  @@5
JC    @@4
MOV   EAX,7
CALL  @@5
JC    @@4
MOV   EAX,61
CALL  @@5
@@4:   SETNC AL
ADD   ESP,4 * 3
POP   EBP
POP   EBX
POP   EDI
POP   ESI
RET
// do a Strong Pseudo Prime Test
@@5:   MOV   EBX,[ESP + 12]   // N on stack
MOV   ECX,[ESP +  8]   // remaining Bits
MOV   ESI,[ESP +  4]   // M'
MOV   EDI,EAX	      // T = b, temp. Base
@@6:   DEC   ECX
MUL   EAX
DIV   EBX
MOV   EAX,EDX
SHL   ESI,1
JNC   @@7
MUL   EDI
DIV   EBX
AND   ESI,ESI
MOV   EAX,EDX
@@7:   JNZ   @@6
CMP   EAX,1	      // b^((N -1)(2^s)) mod N ==  1 mod N ??
JE    @@A
@@8:   CMP   EAX,EBP	      // b^((N -1)(2^s)) mod N == -1 mod N ?? , EBP = N -1
JE    @@A
DEC   ECX	      // second part to 2^s
JNG   @@9
MUL   EAX
DIV   EBX
CMP   EDX,1
MOV   EAX,EDX
JNE   @@8
@@9:   STC
@@A:   RET
@@B:   DB    3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71
@@C:   MOV   EDX,OFFSET @@B
MOV   ECX,18
@@D:   CMP   AL,[EDX + ECX]
JE    @@E
DEC   ECX
JNL   @@D
@@E:   SETE  AL
end;

``````

Ok, is Delphi inlined assembler, but very fast. (extracted from my Delphi Encryption Compendium)

Hagen
Posted on 2003-07-01 12:22:52 by Hagen

I was able to quickly write an algo to test for possible Mersenne primes below N < 2^31 using the algo above for primes. I have tested all prime N, (2^N - 1) for factoring by all prime numbers < N. Now I just need to reduce the list further.

Tell me more bitRAKE...

I'm looking into the Mersenne thing now briefly myself.
Posted on 2004-08-05 00:15:19 by V Coder
bitRAKE, I've finally got back to this a year later. Now understanding the sieve routine...

If you insert a checkpoint at __x, you will find that checking primes up to sqrroot of maxbits (perhaps the bulk of the work) is done in about 90% of the time. At that point you can save the table and close. The rest is just counting the number of set bits. No multiplications etc. needed again...

PS... I guess an advanced bit counting routine, eg mmx will be faster, but since the counting is sooo much faster than the multiplies, etc... it is pointless to optimize the fastest part of the code...

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) :)
Posted on 2004-08-05 00:39:43 by V Coder
V Coder, you are correct a population count would be faster - I was just coding in a hurry to confirm the results of the sieve. With regard to Mersenne primes, I was just using the sieve along with other algorithms from http://www.mersenne.org/ to quickly reduce the number of test cases - although I haven't tested any very large numbers for primeness.
Posted on 2004-08-09 11:16:41 by bitRAKE