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

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

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

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

bitRAKE, nice code.

Can we get away from the Sieve based algos and head more toward the N^2 based ones?

Can we get away from the Sieve based algos and head more toward the N^2 based ones?

**EvilHomer2k**, sure, like what?

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

I think someone on this board is able to write a very efficient version of this algorithm.

JC

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.

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

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

**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.

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.

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.

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.

@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

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

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)

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

```
```

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

```
```

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

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.

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 (

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

**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.