Блог

Я написал простой код для вывода наибольшего простого множителя заданного числа из Project Euler. Это отлично работает для чисел, таких как 24, но для больших чисел нет ответа от оболочки python!

 a=600851475143
b=[]
for i in range(2,600851475143):
    if a%i==0:
         if i==2:
            b.append(i)
            continue
         for j in range(2,i 1):
             if j==i:
                b.append(i)
             if i%j==0:
                break
 print(max(b))
 print(b)
  

Вы можете использовать подобный алгоритм для получения больших множителей простых чисел:

 import math

def LLL(N):
   p = 1<<N.bit_length()-1
   if N == 2:
     return 2
   if N == 3:
     return 3
   s = 4
   M = pow(p, 2) - 1
   for x in range (1, 100000):
     s = (((s * N ) - 2 )) % M
     xx = [math.gcd(s, N)]   [math.gcd(s*p x,N) for x in range(7)]   [math.gcd(s*p-x,N) for x in range(1,7)]
     try:
        prime = min(list(filter(lambda x: x not in set([1]),xx)))
     except:
        prime = 1
     if prime == 1:
        continue
     else:
        break
   return N/prime