forked from fivemack/factorisation-tools
-
Notifications
You must be signed in to change notification settings - Fork 0
/
for_christophe.py
86 lines (78 loc) · 1.41 KB
/
for_christophe.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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
from math import log
import sys
def ModExp (Base, Exp, Mod):
Hash = 1
X = Exp
Factor = Base
while X > 0 :
Remainder = X % 2
X = X / 2
if Remainder == 1:
Hash = Hash * Factor % Mod
Factor = Factor * Factor % Mod
return Hash
def IsPrime(r):
if (r in [2,3,5,7,11,13,31]):
return True
if (ModExp(3,r,r)==3 and ModExp(5,r,r)==5):
return True
return False
def product(l):
if (len(l) == 1):
return l[0];
else:
return l[0] * product(l[1:])
def usum(p,e):
# usum(p,1)=p+1
# usum(p,2)=p**2+p+1
return (p**(e+1)-1)/(p-1)
def sigma(e):
if (len(e) == 1):
return usum(e[0][0],e[0][1])
else:
return usum(e[0][0],e[0][1])*sigma(e[1:])
FN = sys.argv[1]
A=open(FN)
C=open(FN+".cc","w")
line=1
H=A.readline().split(' ')
if (len(H)>1):
line=int(H[1])
u=int(H[0])
smallp = []
for v in A:
pp = int(v)
if (IsPrime(pp)):
smallp = smallp + [int(v)]
else:
print "AARGH composite ",pp
die
smallp.sort()
while (2 != 3):
f = []
uu=u
for p in smallp:
if (u%p==0):
ex=0
while (u%p==0):
ex=1+ex
u=u/p
f=f+[[p,ex]]
if (IsPrime(u)):
f=f+[[u,1]]
u=1
if (u==1):
uf=""
for v in f:
if (v[1]==1):
uf = uf + str(v[0]) + " * "
else:
uf = uf + str(v[0]) + "^" + str(v[1]) + " * "
uf = uf[:-3]
C.write("%04d"%line + " : ")
C.write(str(uu)+" = "+uf+"\n")
# print line,uu,log(uu)/log(10),f
line=1+line
u=sigma(f)-uu
else:
break