# Sieve of Eratosthenes

Learn about the Sieve of Eratosthenes approach to check whether the given number is prime or not.

## 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")
```