Sieve of Eratosthenes

Introduction

Sieve of Eratosthenes is an algorithm for finding all the prime numbers in a segment [1:n].

The algorithm is simple: at the beginning, we write down all numbers between 2 and n. We mark all multiples of 2 (since 2 is the smallest prime number) as non-prime. Then we find the next number that hasn't been marked as non-prime, in this case, it is 3 which means 3 is prime, and we mark all multiples of 3 as non-prime. The next unmarked number is 5, the next prime number, and we mark all multiples of 5 as non-prime. We continue this procedure until we have processed all numbers in the row.

The idea is that a number is prime if none of the smaller prime numbers divides it. Since we iterate over the prime numbers in order, we already marked all numbers, which are divisible by at least one of the prime numbers, as divisible. Hence if we reach a cell and it is not marked, then it isn't divisible by any smaller prime number and therefore has to be prime.

Code

Java

public class Main {
    public static boolean isPrime(int N) {
        boolean[] isPrime = new boolean[N + 1];
        isPrime[0] = isPrime[1] = false;
        for (int i = 2; i <= N; i++)
            isPrime[i] = true;
        for (int i = 2; i <= N; i++) {
            if (isPrime[i])
                for (int j = 2 * i; j <= N; j += i)
                    isPrime[j] = false;
        }
        return isPrime[N];
    }

    public static void main(String[] args) {
        int N = 23;
        if (isPrime(N))
            System.out.println("Prime Number");
        else
            System.out.println("Non-Prime Number");
    }
}

C++

#include <iostream>
using namespace std;

bool isPrime(int N) {
    bool isPrime[N + 1];
    isPrime[1] = isPrime[0] = false;
    for(int i = 2; i <= N; i++)
        isPrime[i] = true;
    for(int i = 2; i <= N; i++) {
        if(isPrime[i])
            for(int j = 2 * i; j <= N; j += i)
                isPrime[j] = false;
    }
    return (isPrime[N]) ? true : false;
}

int main(){
    int N = 23;
    if(isPrime(N))
        cout << "Prime Number";
    else
        cout << "Non-Prime Number";
}

Python

def is_prime(N):
    is_prime = [True] * (N + 1)
    is_prime[0] = is_prime[1] = True
    for i in range(2, N + 1):
        if is_prime[i]:
            for j in range(2 * i, N + 1, i):
                is_prime[j] = False
    return is_prime[N]

if __name__ == "__main__":
    N = 23
    if is_prime(N):
        print("Prime Number")
    else:
        print("Non-Prime Number")