A prime number checker that fails

Question

It seems like a normal code and works well, but for whatever reasons when I try entering this number = 18765411123451, computer seems to freeze, any clue?

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")

I've tried many other numbers and the code works as it should except that number. What happened here?

That's a big number if you want to iterate through every single value in `for i in range(2,num):`. That takes time, the program is probably just locked up crunching through the range. Also, is this definitely Python 3? — roganjosh, Oct 09 '18 at 09:07
@roganjosh it is a big number, but I've tried even larger number(twice as long), it works just fine and fast though — moomoochen, Oct 09 '18 at 09:08
You have a misunderstanding here... What if the even bigger number was even? You'd break out of the loop straight away. What this is telling you is that `18765411123451` is being tested by a significant portion of your `range` — roganjosh, Oct 09 '18 at 09:09
@roganjosh, ahh!! Got it, I see what's going on here, thanks :) — moomoochen, Oct 09 '18 at 09:16
@roganjosh, another question, why is it that the first else statement is in the for loop, not in the _if_ statement? — moomoochen, Oct 11 '18 at 02:51
See [here](https://stackoverflow.com/questions/9979970/why-does-python-use-else-after-for-and-while-loops). It's not related to the `if` but rather the `for`. Bit of an odd construct :) — roganjosh, Oct 11 '18 at 08:21

score 3 · Accepted Answer · answered Oct 09 '18 at 09:08

it freezes because your number just too high.

The reason is for i in range(2,num): with num = 18765411123451 with is 100 trillion...

Plus the fact that python 2 will try to allocate that memory just to create the list to iterate on it (in that case use xrange)

Good news: you don't have to check until the number itself, just check until square root (included):

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

that's more reasonable (less that 5 million iterations) and will provide the same result.

Past the square root of a number, if you haven't found divisors, you won't find any afterwards (if q is a divisor of num, then p*q == num so either p or q has to be lower or equal than square root of num

A prime number checker that fails

1 Answers1