Я пытаюсь решить это упражнение: https://projecteuler.net/problem=69. Это прекрасно работает с примером, приведенным в упражнении, но вылетает, когда я пытаюсь вычислить максимум для n <= 1.000.000, и это ужедовольно медленно, когда я пытаюсь вычислить его для n <= 5.000.Как я могу оптимизировать мой код?Я использую PyScripter. </p>
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
def coprime(b):
x = 0 # define a counter for the number of co-primes of b
for a in range(1, b):
if gcd(a, b) == 1: # check if a and b are co-prime
x += 1
return x
def main():
maximum = 1
for n in range(1, 1000001):
m = coprime(n)
x = n / m # calculate n/phi(n)
if x > maximum: # check if you have a new maximum
maximum = n
print(maximum)
if __name__ == '__main__':
main()