Rate my first python prime checker

Question

I'm new to programming; I started about a week ago and started learning python. Currently, I only know some basic arithmetic operations in addition to some basic knowledge about lists, dictionaries, strings, etc.

I tried testing what I learnt so far. I made this prime number checker, which works except when the numbers are really big. Please rate it and suggest improvements that I can understand at my current level.

Here is the code:

'''
pr means the number we'll be working on
dl is a dictionary that contains our the dividend and the reaminder
x is the dividend
e is a list that contains all remainders
and what the program does as you might have guessed already
it makes a list of all remainders of the division of our number by every integer before it
and checks for the number 0
if it finds it then the number is not prime
and if it doesn't then it's prime
'''

pr = int(input("Enter your number "))

print("\n")

dl = {}

x = pr - 1
while x < pr and x > 1 :
    r = pr % x
    dl[x]= r
    x -= 1

e = list(dl.values())

if any( z == 0 for z in e ) :
    print(pr," is not a prime number")
else :
    print(pr," is a prime number")

print("\n")

input("Press Enter to close the program")

Answer 1

Code showing some of the points AJNeufeld mentioned.

Further points:

• You can check most false states in one condition
• Because of this, you only need to check factors from a minimum of 3
• Working through the possible factors in ascending order will produce a quicker result. E.g. 1200 is not divisible by 1199, but is by 3.
• You only need to check factors up to the square root of the passed number, since any numbers after that will start repeating previously checked calculations. E.g. 3 * 400 == 400 * 3
• Any even factor will produce an even number, so we can skip checking even factors in the for loop using a step size of 2

import math

num = int(input("Enter your number: "))

# check all negative numbers, 0, 1 and even numbers
if num <= 1 or (num % 2 == 0 and num > 2):
    print(num, "is not a prime number")
else:
    # calculate square root as maximum factor to check
    # any numbers past this point will start repeating
    # previously checked values since a * b == b * a
    sqrt = math.sqrt(num)
    # start from 3, checking odd numbers only
    # even factors will result in an even num
    # + 1 on end ensures loop runs for x == 3
    for x in range(3, int(math.floor(sqrt)) + 1, 2):
        if num % x == 0:
            print(num, "is not a prime number")
            break
    # no factor found, loop falls through
    else:
        print(num, "is a prime number")

Answer 2

I'd have to rate your program a "D-Minus".

• incorrectly labels 1, 0, and all negative numbers as prime!
• runs in \$O(n)\$ time, instead of \$O(\sqrt n)\$ time
• runs in \$O(n)\$ space, instead of \$O(1)\$ space

Other deficiencies:

• '''docstrings''' should be used for describing "how" to use the module/class/method; comments should be used to explain how the code works
• variable names are cryptic; too short to be descriptive
• PEP8 guidelines are not consistently followed. Operators like = should have 1 space on each side. No space should be used after (, or before ), as well as not before :
• a dictionary is being used to store a list of values; a simple list would suffice
• dl.values() is an iterable; there is no need to convert it into a list in order to use in the for z in ...

As suggested by aaaaa says reinstate Monica, please work on your solution and then submit it as a new question.

Answer 3

First, thank you for including a docstring that explained how the script works; it saved me a good couple of minutes in puzzling it out. :) It turned out to be a lot simpler than I initially thought it was, which suggests an easy path to optimizing it for space.

The error that your program hits with large numbers is a MemoryError, which is a result of the dictionary that you build which includes every number prior to your number (or, potentially, the roughly-equally-massive list that you then unnecessarily convert that dictionary into).

Since you're only interested in one piece of data (is any of these numbers zero?), and since the computation of the numbers doesn't depend on any of the numbers before them, there's no need to store them all in memory. As soon as one of the values of r (aka pr % x; there's not really any reason to name or store it since you only look at it once) is 0, you know that the number isn't prime; that's all there is to it.

The core of your program stays the same. Just skip the part where you build the giant dictionary and the giant list, and have the program finish immediately once it knows what the answer is:

pr = int(input("Enter your number: "))

x = pr - 1
while x > 1 :
    if pr % x == 0:
        print(pr, "is not a prime number")
        exit()
    x -= 1
print(pr, "is a prime number")

Answer 4

pr means the number we'll be working on
dl is a dictionary that contains our the dividend and the reaminder
x is the dividend
e is a list that contains all remainders

These variable names are very short and don't have a lot of meaning. You can save a lot of comments by naming your variables: number_to_check, remainders, dividend, remainder_list.

Not all variable names need to be that explicit, but if you feel the need to explain them in a comment, there is probably room for improvement.

and what the program does as you might have guessed already it makes a list of all remainders of the division of our number by every integer before it and checks for the number 0 if it finds it then the number is not prime and if it doesn't then it's prime

This part of the comment you can also make redundant by using method names:

def isPrime(our_number):
    remainders = make_list_of_all_remainders(our_number)
    if any( item == 0 for item in remainders ):
        return False
    else:
        return True

If you read the method names, it basically narrates the same as your description of the algorithm does.

Answer 5

In addition, I'd recommend using a for loop instead of a while loop here just so that it's more clear what's going on. And I'd put the entire for loop in a function so you could do something like

if isPrime(pr):
    print(pr, " is a prime number.")
else:
    print(pr, " is not a prime number.")

This will also make it so you can use return() instead of exit() as specified in the other answer:

def isPrime(pr):
    for i in range(2, pr):
        if pr % i == 0:
            return(True)
    return(False)

Also as already stated name your variables properly.

Answer 6

functions

Separate your program into functions

• getting the input number
• calculate the result
• present the result (print)

get the number

When you do int(input("<message>")), and the user types in text that is not convertable to an integer, your program will fail with a strange error message. Better is to validate the user input

def get_number() -> int:
    """
    Asks the user for a number

    Asks again if the user input is no valid integer
    Returns None when the user returns 'q'
    """
    while True:
        input_str = input("Enter your number")
        try:
            return int(input_str)
        except ValueError:
            if input_str.lower() == "q":
                return None
            print(
                f"{input_str} is not a valid integer. "
                "Try again or enter `q` to quit"
            )

If you want, you can add more tests to this function, like testing that the result is larger than 1,...

calculate

Your algorithm works like this: - iterate from the number itself down - store the remainder of the division in a dict - make a list of the values - check whether any of the values of the dict is 0

This can be simplified in a number of steps: - why the list. You can immediately iterate over the values - why the dict? You only use the values, so you can use another container like a list or set to only store the values - why iterate over all the values, if you use a set, you can check if 0 in remainders - why iterate over all the values. You can stop once a remainder is 0 - why start at the number with the iteration. You will not find any divisors between number and number//2. You can even stop at the square root of the number, because either the divisor or the quotient will be smaller if there is any. - why iterate descending. Odds are, you'll find a remainder in the lower numbers sooner - why iterate over all numbers. If 2 is no divisor, 4, 6, 8, ... will not be a divisor either

So this would be a lot more efficient:

def is_prime(number: int) -> bool:
    """Checks whether `number` is prime"""
    if number < 2:
        return False
    if number == 2: 
        return True
    i = 3
    while i**2 <= number:
        if number % i == 0: # or of `not number % i:`
            return False
        i += 2
    return True

There are more efficient prime checkers out there, but this will already be a lot more performant than your version

present the result

Now you have nice, clear functions to get a number from the user, and calculate whether the number is prime, you can make a function to present this to the user:

def main() -> None:
    number = get_number()
    if number is None:
        return
    result = is_prime(number)
    if result:
        message = f"{number} is prime"
    else:
        message = f"{number} is not prime"

    print(message)
    print("Press Enter to close the program")
    input()

if __name__ == "__main__"

The code you really want executed when you call this as a script, but not when you import it in a different program should go behind an if __name__ == "__main__": guard. Here you can do the presentation:

if __name__ == "__main__":
    main()

type hints

I've added type hints, so users of the function (other programmers, not the end users) know what kind of type the function expects and returns

Answer 7

Input validation: the term "prime" is often used to refer to integers greater than 1. You might want to check whether it qualifies. It's up to you whether to reject negative integers outright or multiply them by negative 1.

Reverse order doesn't make sense: you're starting from the largest numbers, but if something isn't prime, then you'll see that earlier if you start will small numbers. For instance, for 26, you'll have to go down 12 numbers if you're starting at 25 to get to 13, but you'll immediately get to 2 if you're starting with small numbers.

Smaller range: you only have to check numbers less than the square root.

Reduced possible factors: Once you check whether a prime number is a factor, you don't have to check any multiples of the prime factor. So if you have a list of prime factors up to the square root of the number you're checking, you only have to use those. Otherwise, you can check only numbers relatively prime to the product of the primes you do have. For instance, for primes [2, 3, 5], you only have to check numbers that are, modulus 30, in [1, 7, 11, 13, 17, 19, 23, 29].

import math
def prime_checker(pr, modulus = 30):
    residues = [residue for residue in range(modulus) 
        if math.gcd(residue, modulus) == 1]
    try:
        our_int = int(pr)
    except:
        print("Not a valid number")
        return
    if our_int != float(pr):
        print("Not an integer")
        return
    if our_int < 2:
        print("Number greater than 1 expected.")
        return
    if our_int in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]:
        return True
    for candidate in range(2, modulus):
        if candidate * candidate > our_int:
            return True
        if (our_int % candidate) == 0:
            print(str(candidate)+ " is a factor")
            return False            
    multiple =  1
    while True:
        product = multiple*modulus
        if product*product > our_int:
            return True
        for residue in residues:             
            if ((our_int % (residue + product)) == 0):
                print(str(residue + product)+ " is a factor")
                return False 
        multiple += 1

Answer 8

Great start! People have already given good advice in terms of improving the solution, but I'd like to comment on some things that could be improved on even though they aren't relevant in the "cleaned up" versions people have posted.

• you can iterate over a dictionary, so there's no need to turn it into a list first. Iterating over like this: for i in dl: will give you the keys, and like this: for i in dl.values(): will of course give you the values. dl.items() gives both as a tuple (which can be unpacked if you'd like: for (key, value) in dl.items():.
• With that in mind, the any check could be written as if any( z == 0 for z in dl.values() This is fine, but we can invert the logic (something that takes a bit of experience to recognize). if any values equal 0 is the same as if all values are not 0. Realizing that python treats 0 as false and all other integers as true gives the slightly cleaner final form: if all(dl.values()): # the number is prime
• All that being said, since you aren't using the 'divisor list' dl except for checking if it contains a 0, you can instead just break the loop when you find a 0 without storing the result and checking it later. Other answers cover that in better detail. That will be much more memory efficient and also more efficient in terms of runtime, since you can stop as soon as you find a divisor.
• Your first while condition is unnecessary. Since you've set x = pr - 1, x < pr will always be true (provided you don't increment or set x to a value higher than pr, which of course you aren't doing)

Happy Coding!