Determining whether a number is prime or not

Question

I know it's been discussed many times; I've read it, but somehow I can't get it. I want to write a program that determines if the entered number is prime or not.

One of the implementations I found somewhere on the Internet:

from math import *

def main():
    n = abs(input("Enter a number: "))
    i = 2
    msg = 'is a prime number.'
    while i <= sqrt(n):
        if n % i == 0:
            msg = 'is not a prime number.'
        i = i + 1
    print n, msg


main()

A couple of questions here:

• In the above, what is i, and why does it have a starting value of 2?
• What does i = i + 1 do in this program?
• How does the interpreter know when to print 'is a prime number.' even though it is out of the body loop?

Answer 1

A prime number is a number that's only divisible by 1 and itself. The method it's using is to try dividing your candidate number n by every other number from 2 up to itself; however if any number i is a divisor of your number n then so is n / i and at least one of them is less than or equal to sqrt(n) therefore we need only test up to sqrt(n) inclusive. In practice we need only test the divisors that are actually prime themselves but since we don't have a list of primes to hand we'll test every one.

what in the above i is? and why it got a 2 starting value?

i is the potential factor of n we're testing. It starts with 2 because we don't care if 1 divides n (and trivially it will) because the prime definition allows / expects that.

what is the i = i + 1 statement, in this concrete example for? Can't see its use in the program.

It's incrementing the i value at the end of the loop defined by the while i <= sqrt(n); it means we advance i to test the next candidate divisor of n.

and finally, how python knows when to print 'is a prime number.' although it is out of the body loop?

We initialise msg to "is a prime number" and if we find any divisor then we change it to "is not a prime number" inside the loop. If the loop doesn't find a divisor, or if the loop never runs, we'll use the initial value we set which is "is a prime number". Incidentally you could break out of the loop when you find a divisor; there's no point carrying on the test after that.

As another aside you probably want to compute sqrt(n) outside the while and store than in a variable to use in the while - you may be recalculating the square root for every iteration, which is relatively expensive.

Answer 2

I've added comments on the sides to explain what each line does:

from math import * # imports everything from the math module

def main():
    n = abs(input("Enter a number: ")) # gets input from the user
    i = 2 # starts off at 2 because all input is divisble by 1
    msg = 'is a prime number.' # the message is initially set
    while i <= sqrt(n):
        if n % i == 0: # if 'i' divides evenly into n
            msg = 'is not a prime number.' # only set if it isn't a prime
        i = i + 1 # increases 'i' by 1 so it can check every value up to the square-root of 'n' (to see if it divides evenly)
    print n, msg


main()

The program has to go through every value of i (up to the square-root of n) so that every possible factor is checked.

This is sort of a rough-prime checker, and inefficient for large numbers that aren't prime: If the input was a number like 1234567890, it will iterate through every number up to the square root of that number, which is 35147 (rounded up). Using return statements break the loop, so the first number you check, 2, it is declared not prime since it is evenly divisible by 2. By using return, it will stop the function, and save you 35,146 calculations. That isn't a massive number (for computers, at least) but it's still more memory-efficient and takes less time.

def isPrime(n):
    '''Checks if 'n' is prime.'''
    from math import sqrt
    if n == 0 or n == 1:
        return False
    else:
        for check in range(2, int(sqrt(n))+1):
            if n % check == 0: return False
    return True