is prime in python

To check if a number is prime in Python, we can use the following algorithm:

  1. Check if the number is less than 2. If it is, the number is not prime.
  2. Check if the number is divisible by any integer from 2 to the square root of the number (rounded up). If it is, the number is not prime. Otherwise, the number is prime.

Here's a Python function that implements this algorithm:

main.py
import math

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, math.ceil(math.sqrt(n))+1):
        if n % i == 0:
            return False
    return True
179 chars
10 lines

The function takes an integer n as input and returns True if n is prime, and False otherwise. We start by checking if n is less than 2, since 0 and 1 are not prime. Then we loop over all the integers from 2 to the square root of n (rounded up), checking if n is divisible by each one. If we find a divisor, we return False since the number is not prime. If we have looped over all the possible divisors without finding one, we know that the number is prime and we return True.

We can test the function like this:

main.py
>>> is_prime(17)
True
>>> is_prime(21)
False
>>> is_prime(1000000007)  # a large prime number
True
>>> is_prime(1000000009)  # another large prime number
True
>>> is_prime(1000000021)  # not prime
False
203 chars
11 lines

gistlibby LogSnag