typestar

Primality test in Python

Trial division: the simplest primality test worth writing.

def is_prime(n):
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2
    i = 3
    while i * i <= n:
        if n % i == 0:
            return False
        i += 2
    return True

How it works

  1. Rules out numbers under 2, and even numbers except 2, early.
  2. Tries odd divisors up to the square root.
  3. Any divisor means composite; none means prime.

Keywords and builtins used here

The run, in numbers

Lines
11
Characters to type
139
Tokens
50
Three-star pace
90 tpm

At the three-star pace of 90 tokens a minute, this run takes about 33 seconds.

Type this snippet

Step 7 of 7 in Flow control, step 22 of 72 in Language basics.

← Previous Next →

Primality test in other languages