Sieve of Eratosthenes

The Sieve of Eratosthenes is a very ancient method for finding prime numbers. As the name suggests, it was proposed by the ancient Greek mathematician Eratosthenes.

Description

The Sieve of Eratosthenes (hereafter called the Eratosthenes sieve) is an algorithm for getting all the prime numbers up to a natural number n by gradually eliminating multiples of primes no greater than √n. An implementation in Python is shown below.

x = int(input())
y = [True] * (x + 1)
y[0], y[1] = False, False
for i in range(2, x + 1):
    if y[i]:
        for j in range(i, x + 1, i):
            y[j] = False
if y[x]:
    print(f"{x} is a prime number.")
else:
    print(f"{x} is not a prime number.")

The program does the following:

1. First, the program takes an integer x.
2. Then, it lists a sequence from 0 to x, and crosses out 0 and 1 first (since they're neither prime nor composite).
3. Repeatedly, it finds an uncrossed number p in the sequence, and crosses out numbers in the sequence that are multiples of p like 2p, 3p, 4p, etc.
4. If the last number, x, hasn’t been crossed out, then it’s a prime number.

Examples

Brain-Flak

{(({})[()])}{}{}([]){{}{(({}<>{})(<()>)<>)([][()]){{}(({}[()])<{({}[()]<({}<>)(())<>>)}({}<>)(())<>{}>())([][()])}{}{}<>{{}({}<>)<>}(<>)}{}([])}{}<>{}{({}<>)<>}<>

See also

• wikipedia:Sieve of Eratosthenes
• Prime numbers generator
• Prime Detector