How to properly check if a number is a prime number-CodePudding

Hey so i have this function to check if a number is a prime number

def is_prime(n):
    flag = True
    for i in range(2, n ):
        if (n % i) == 0:
            flag = False
    return flag


print(is_prime(1))

However when i test the number 1, it skips the for loop and returns True which isn't correct because 1 is not a prime number. How could i fix this?

CodePudding user response：

You can first start by checking if n is greater than 1 the code should proceed, else it should return False. If n passes the first condition, only then the code can proceed to verify if n is indeed prime or not.

def is_prime(n):
    flag = True
    if n > 1:
        for i in range(2, n ):
            if (n % i) == 0:
                flag = False

        return flag # Returns this flag after check whether n is prime or not
        
    # Returns False if n <= 1
    return False


print(is_prime(1))

output:

False

CodePudding user response：

2 is also skipped by the loop, but the function returns true thanks to the flag, and we know that's right.

Also you can exit early the loop if the condition is met:

def is_prime(n: int) -> bool:
    if n > 1:
        for i in range(2, n): # if n == 2, there is no loop, is never checked
            if (n % i) == 0:
                return False # can return early once we meet the condition, don't need to finish the loop

    return True

print(is_prime(7534322224))
print(is_prime(5))

An alternative approach (though much slower on bigger numbers):

def is_prime(n: int) -> bool:
    if n < 2: return False    
    return n == 2 or True not in [True for i in range(2, n) if (n % i) == 0]

print(is_prime(75343224))
print(is_prime(5))