Ja. Har endret isprime til å bruke at hvis et tall n er samensatt, så har det en faktor som er lavere enn sqrt(n). Bytter også ut range(..) med en while-løkke som bare sammenligner to heltall. Tror det er billigere, men er ikke sikker... Det tar dog fortsatt skrekkelig lang tid, så vet ikke om jeg ender opp med en løsning uansett.
Code: Select all
def gcd(a,b):
# returnerer sfd(a,b)
d = 1
i = 1
while i <= min(a,b)+1:
if not a%i and not b%i:
d = i
i+=1
return d
def reduser(a):
#input: touple a tolket som broek
#output: touple (b,c) lik reduserte broek a
d = gcd(a[0],a[1])
b = a[0]/d
c = a[1]/d
return (b,c)
def isprime(n):
# input: heltall n
# output: 1 hvis n er primsk, 0 hvis n er sammensatt
i = 2
while i <= int(n**.5)+1:
if not n%i:
return 0
i+=1
return 1
# H[k] er H_k som definert i oppgaveteksten
H = [(1, 1), (1, 1)]
#[(1, 1), (1, 1), (5, 4), (49, 36), (205, 144), (5269, 3600), (5369, 3600), (266681, 176400), (1077749, 705600), (9778141, 6350400), (1968329, 1270080), (239437889, 153679680)]
# Antall primtall W_k funnet.
primtall = 0
# Finn 4 av dem
while primtall <= 4:
# Legg til neste ledd i foelgen H ved aa benytte seg
# av siste utregnede H-verdi
l = len(H)-1
Hl = H[l]
Hl1 = (Hl[0]*(l+1)**2 + Hl[1], Hl[1]*(l+1)**2)
Hl1 = reduser(Hl1)
H.append(Hl1)
# Sjekk om telleren er et primtall
if isprime(Hl1[0]):
print "Leddet %s har primtalls-teller: %s" % (l+1,Hl1)
primtall += 1
else:
print "Leddet %s har ikke primtalls-teller: %s" % (l+1,Hl1)
