Az euklideszi algoritmus hatékonysága
Euklideszi algoritmus
a = 44
b = 32
while b!=0: a,b = b,a%b
print(a)
Euklideszi algoritmus nagy számokkal
a = ZZ.random_element(10^1000,10^1001)
b = ZZ.random_element(10^1000,10^1001)
print(a)
print(b)
while b!=0: a,b = b,a%b
print(a)
Euklideszi algoritmus nagy számokkal, sokszor
for i in range(10):
a = ZZ.random_element(10^1000,10^1001)
b = ZZ.random_element(10^1000,10^1001)
while b!=0: a,b = b,a%b
print(a)
Prímfaktorizáció
a = ZZ.random_element(10^100,10^101)
print(a)
print(factor(a))
Hány lépésig tart az euklideszi algoritmus?
def eukl(a,b):
n = 0
while b!=0:
a, b = b, a%b
n += 1
return n
print(" ",end="")
for b in range(2,10): print(b,end=" ")
print()
print(" ",end="")
for b in range(2,10): print("-",end=" ")
print()
for a in range(2,10):
print(a,end=" | ")
for b in range(2,10):
n = eukl(a,b)
if a>=b:
print(n,end=" ")
else:
print(n,end=" ")
print("")
Az euklideszi algoritmus legrosszabb esetei
legrosszabb = 0
for a in range(100):
for b in range(a,100):
n = eukl(a,b)
if n>legrosszabb:
print("a=",a,"\t b=",b,"\t lépésszám=",n)
legrosszabb = n
Üres cellák