blob: cf4d139e3e1de6ae1328558f453b279750c80fe2 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
#!/usr/bin/env python
import sys
def gcd(x,y):
if x <= 0 or y <= 0:
raise ValueError, "Arguments must be positive integers"
g = y
while x > 0:
g = x
x = y % x
y = g
return g
def gen_primes():
primes = [2,3,5,7,11]
# Primes < 11351 fit into less than 256x64 bits
for i in xrange(1+primes[-1], 11351+1):
for prime in primes:
if gcd(i, prime) != 1:
break
else:
primes.append(i)
return primes
def extract_product(primes):
product = 1
used = set()
for prime in sorted(primes, reverse=True):
if product * prime < 2**64:
product *= prime
used.add(prime)
primes -= used
return product
def main():
primes = gen_primes()
primes.sort()
primes.reverse()
primes = set(primes)
while len(primes):
print "0x%016X, " % extract_product(primes)
#product = 1
#for prime in primes:
# product *= prime
# if product >= 2**64:
# print "%016X" % (product/prime)
# product = prime
if __name__ == '__main__':
sys.exit(main())
|
