Проверка простых чисел, которая не работает

Question

Это похоже на нормальный код и работает хорошо, но по каким-то причинам, когда я пытаюсь ввести это число = 18765411123451, кажется, что компьютер зависает, какая-либо подсказка?

num = 18765411123451

if num > 1:
  for i in range(2,num):
    if num % i == 0:
      print(num,"is not a prime number")
      print("Because", i,"x",num//i, "=" ,num)
      break
  else:
    print(num,"is a prime number")
else:
  print(num,"is not a prime number")

Я пробовал много других чисели код работает как надо, кроме этого числа.Что здесь случилось?

Answer 1

оно зависает, потому что ваше число слишком велико.

Причина for i in range(2,num): с num = 18765411123451 с составляет 100 триллионов ...

Плюс тот факт, что Python 2 попытаетсявыделите эту память только для создания списка для его повторения (в этом случае используйте xrange)

Хорошая новость: вам не нужно проверять до самого числа, просто проверяйте до получения квадратного корня (включено):

for i in range(2,int(num**0.5)+1):

это более разумно (менее 5 миллионов итераций) и даст тот же результат.

Если после квадратного корня из числа делителей вы не нашли делителей, выпотом не найдет (если q является делителем num, то p*q == num, поэтому либо p, либо q должно быть меньше или равно квадратному корню из num