-
Notifications
You must be signed in to change notification settings - Fork 0
/
euler69.py
67 lines (54 loc) · 1.2 KB
/
euler69.py
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
64
65
66
67
import pickle
f=open('primes.txt')
primes=pickle.loads(f.read())
def filter(ls):
ls2=[]
for x in ls:
if x<1000001:
ls2.append(x)
else: return ls2
primes=filter(primes)
primeset=set(primes)
f.close()
def factorout(n,x):
if n%x!=0:
return n
else:
return factorout(n/x,x)
def prime_fact(n):
facts=[]
if True:
for x in primes:
if n%x==0:
facts.append(x)
n=factorout(n,x)
if n in primeset:
facts.append(n)
return facts
elif n==1:
return facts
def diction():
d=dict()
for x in range(2,1000001):
if x in primeset:
d[x]=set([x])
else:
d[x]=set(prime_fact(x))
return d
d=diction()
def rprime(n,d):
# rp=[1]
rp=1
ls=d[n]
for i in range(2,n):
if len(ls.intersection(d[i]))==0:
# rp.append(i)
rp+=1
return float(n)/rp
top=[4.8125,2310]
def test(top,n=20071):
for x in range(n,1000001,2):
if rprime(x,d)>top[0]:
top[0]=rprime(x,d)
top[1]=x
print x