Browse Groups

• ## Implementing Fermat prime number Sieve

(1)
• NextPrevious
• I ve programmed the Fermat prime number sieve and tested it out on a few different ranges. If the occasion ever arose to factor all numbers in an interval,
Message 1 of 1 , Jul 31, 2007
View Source
I've programmed the Fermat prime number sieve and tested it out on a few
different ranges.

If the occasion ever arose to factor all numbers in an interval, this
algorithm could be extended to find factors for all the numbers in the
interval almost as quickly as Fermat factoring could factor the most
difficult number in the interval.

>>> SieveFermat(10**3,10**3+100)

number of clears is 260
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1009, 0, 0, 0, 1013, 0, 0, 0, 0, 0, 1019, 0,
1021, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1031, 0, 1033, 0, 0, 0, 0, 0, 1039, 0,
0, 0, 0, 0, 0, 0, 0, 0, 1049, 0, 1051, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1061,
0, 1063, 0, 0, 0, 0, 0, 1069, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 1087, 0, 0, 0, 1091, 0, 1093, 0, 0, 0, 1097, 0, 0, 0]

>>> SieveFermat(10**4,10**4+100)

number of clears is 2135
[0, 0, 0, 0, 0, 0, 0, 10007, 0, 10009, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10037, 0, 10039, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10061, 0, 0, 0,
0, 0, 10067, 0, 10069, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10079, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 10091, 0, 10093, 0, 0, 0, 0, 0, 10099, 0]

>>> SieveFermat(10**5,10**5+100)

number of clears is 21255
[0, 0, 0, 100003, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100019,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
100043, 0, 0, 0, 0, 0, 100049, 0, 0, 0, 0, 0, 0, 0, 100057, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 100069, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

>>> SieveFermat(10**6,10**6+100)

number of clears is 213878
[0, 0, 0, 1000003, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1000033, 0, 0, 0, 1000037, 0, 1000039,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1000081, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1000099, 0]

>>> SieveFermat(10**5,10**5+1000)

number of clears is 22491
[0, 0, 0, 100003, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100019,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
100043, 0, 0, 0, 0, 0, 100049, 0, 0, 0, 0, 0, 0, 0, 100057, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 100069, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100103, 0, 0,
0, 0, 0, 100109, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 100129, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 100151, 0, 100153, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
100169, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100183, 0, 0, 0, 0, 0,
100189, 0, 0, 0, 100193, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100207,
0, 0, 0, 0, 0, 100213, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 100237, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100267, 0, 0, 0, 100271, 0,
0, 0, 0, 0, 0, 0, 100279, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100291, 0, 0,
0, 0, 0, 100297, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100313, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100333, 0, 0, 0,
0, 0, 0, 0, 0, 0, 100343, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100357,
0, 0, 0, 100361, 0, 100363, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
100379, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100391, 0, 100393, 0, 0, 0, 0,
0, 0, 0, 0, 0, 100403, 0, 0, 0, 0, 0, 0, 0, 100411, 0, 0, 0, 0, 0,
100417, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 100447, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100459,
0, 0, 0, 0, 0, 0, 0, 0, 0, 100469, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 100483, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100493, 0, 0, 0, 0, 0, 0, 0,
100501, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100511, 0, 0, 0, 0, 0, 100517, 0,
100519, 0, 0, 0, 100523, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100537,
0, 0, 0, 0, 0, 0, 0, 0, 0, 100547, 0, 100549, 0, 0, 0, 0, 0, 0, 0, 0, 0,
100559, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100591, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 100609, 0, 0, 0, 100613, 0, 0, 0, 0, 0, 0, 0, 100621,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 100649, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 100669, 0, 0, 0, 100673, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 100693, 0, 0, 0, 0, 0, 100699, 0, 0, 0, 100703, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 100733, 0, 0, 0, 0, 0, 0, 0, 100741, 0, 0, 0, 0, 0, 100747, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100769, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100787, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 100799, 0, 100801, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100811, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 100823, 0, 0, 0, 0, 0, 100829, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100847, 0, 0, 0, 0, 0, 100853, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 100907, 0, 0, 0, 0, 0, 100913, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 100927, 0, 0, 0, 100931, 0, 0, 0, 0, 0, 100937, 0, 0, 0, 0, 0,
100943, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100957, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100981, 0, 0, 0, 0,
0, 100987, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100999, 0]
>>>

Kermit < kermit@... >

----------

def SieveFermat(start,end):
rstart = ksqrt(start-1)
if start == 0:
rstart = -1
rend = ksqrt(end)
jar = range(start,end+1)

plex = 0

##### zero out 1 if it is present

if start < 2:
jar[1 - start] = 0

#### zero out all even numbers

mds = start + start%2
mde = end + end%2
while mds < mde + 1:
jar[mds - start] = 0
mds = mds + 2

##### outer loop : Set larger square for difference of squares

rs = rstart + 0
if rs < 2:
rs = 2
rsupper = (end + 10)/6
while rs < rsupper:
rs = rs + 1
rs2 = rs * rs
if rs2 < start:
continue

####### set smaller square for difference of squares. Difference must be odd number.

loop2 = 0
sidelow = rs2 - end
if sidelow < 1:
sidelow = 1
sidehigh = rs2 - start + 1
dexlow = ksqrt(sidelow - 1)
dexhigh = ksqrt(sidehigh - 1)
if dexhigh > rs -4:
dexhigh = rs - 4
dex = dexlow - dexlow%2 -rs%2 -1

##### dex remains opposite parity from rs

while dex < dexhigh:
dex = dex + 2

plex = plex + 1

dex2 = dex * dex
d1 = rs - dex
if d1 < 2:
break
d2 = rs2 - dex2
if d2 < start:
break
if d2 > end:
continue
pos = d2 - start
jar[pos] = 0

print "\n number of clears is ",plex
return jar

def ksqrt(start):
if start < 1:
return 0
r = 1
r2 = r * r
while r2 < start:
r = r * 2
r2 = r2 * 4
s = 0
s2 = 0
while r > 0:
s = s + r
s2 = s * s
if s2 > start:
s = s - r
r = r/2
return s

[Non-text portions of this message have been removed]
Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.