## Assembly pgm for the decomposition of primes

Expand Messages
• oups, sorry... Dear primenumbers group, My friend Fabien Sibenaler realized an Assembly program implementing the new algorithm that gives the decomposition of
Message 1 of 2 , Apr 21 10:31 AM
oups, sorry...

My friend Fabien Sibenaler realized an Assembly program implementing the new
algorithm that gives the decomposition of a prime number (prime = weight * level
+ gap, or A000040(n) = A117078(n) * A117563(n) + A001223(n)).

This pgm is faster than the previous pgm said "naïf" for prime numbers
classified by level.
Ex (PIV 3 GHz, 512 Mo RAM) :
Old pgm :
Number : 979872743
Gap : 204
Weight : 979872539
Level : 1
Time in ms : 116656

New pgm :
Number : 979872743
Gap : 204
Weight : 979872539
Level : 1
Time in ms : 16

The principle of the new algo :
We look for the odd weights until sqrt(p) (1 red) and if we did not find the
decomposition, we look for it by levels until (ln p)^2 by beginning with the
highest level (2 red).
This limit (ln p)^2 is arbitrary and can be improved.
Whith the "naïf" algo, we looked for the odd weights until p-g (1 black) :
http://reismann.free.fr/primeSieve.html
The decomposition of primes in weight * level + gap is a generalisation of the
Eratosthenes sieve :
http://reismann.free.fr/sieveEra.html

Assembly pgm :
source code).
http://reismann.free.fr/telechargements.php

With this pgm I found a prime of level(1,24) :
p(28106444831) - p(28106444830) = p(28106444830) - p(28106444830 - 24)
738832928467 - 738832927927 = 738832927927 - 738832927387 = 540 = 6 * 90
p(28106444830) is of level 1 in in A117563,
p(28106444830) = 738832927927 is of level(1,24).

With the Java pgm, I obtained a table of 25 million lines in 2h49min (PIV 3
GHz, 512 Mo RAM).

Best,

Rémi Eismann
Your message has been successfully submitted and would be delivered to recipients shortly.