## Problem define

We want to find all the primes between 2~N, then how to find all the primes efficiently?

### Sieve of Eratosthenes

Sieve of Eratosthenes method, is very efficient, the algorithm is:

- Create a list of consecutive integers from 2 through n: (2, 3, 4, ..., n).
- Initially, let p equal 2, the first prime number.
- Starting from p, enumerate its multiples by counting to n in increments of p, and mark them in the list (these will be 2p, 3p, 4p, ... ; the p itself should not be marked).
- Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this new number (which is the next prime), and repeat from step 3.

And, there are some small tricks that could refine the algorithm.
As a refinement, it is sufficient to mark the numbers in step 3 starting from p^{2}, as all the smaller multiples of p will have already been marked at that point. This means that the algorithm is allowed to terminate in step 4 when p^{2} is greater than n.

## Java code

The jave implement of Sieve of Eratosthenes is as:

```
public static List<Integer> getPrimebyErichsenSieve(int range) {
if (range < 2) {
throw new IllegalArgumentException("range should >= 2");
}
boolean[] isPrime = new boolean[range + 1];
// init
for (int i = 0; i <= range; i++) {
isPrime[i] = true;
}
isPrime[0] = false;
isPrime[1] = false;
// sieve
for (int i = 2; i * i <= range; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= range; j += i) {
isPrime[j] = false;
}
}
}
// collect results
List<Integer> primeList = new ArrayList<Integer>();
for (int i = 0; i <= range; i++) {
if (isPrime[i]) {
primeList.add(i);
}
}
return primeList;
}
```

## Complexity

Time complexity for Sieve of Eratosthenes is **O(nloglogn)**, and Space complexity is **O(n)**. **O(nloglogn)** is nearly a linear algorithm, and is much faster than the other function I wrote in the java code.

In the above java code, I also implemented another brute-force algorithm `getPrimebySimpleMethod()`

to find primes, by running the algorithm to generate all primes between 0~1000000,

```
// time for Erichsen Sieve, range: 1000000
long startMili=System.currentTimeMillis();
List<Integer> list3 = Primer.getPrimebyErichsenSieve(1000000);
long endMili=System.currentTimeMillis();
System.out.println("time："+(endMili - startMili) + "ms");
System.out.flush();
// time for simple method, range: 1000000
startMili=System.currentTimeMillis();
List<Integer> list4 = Primer.getPrimebySimpleMethod(1000000);
endMili=System.currentTimeMillis();
System.out.println("time："+(endMili - startMili) + "ms");
System.out.flush();
```

we could see the running time differnece is:

```
time：28ms
time：319ms
```

Sieve of Eratosthenes is much better than `getPrimebySimpleMethod()`

brute-force method.

For the above brute-force algorithm, the time complexity is: **O(n ^{3/2})**.

### Complexity Analysis

For the **O(nloglogn)** analysis for Sieve of Eratosthenes, please refer to this and this.

I found it's a little hard to write equation in YAML Markdown, so sorry for no equation in this post.

Because Sieve of Eratosthenes need **O(n)** Space complexity, so if you want to get a very very large range primes, you need to segment the range and process each segment separately, if not, you will run into out of memory.

## Find the largest prime that less than given x

Sometimes maybe we need to find the largest prime less than a given number, such as **x**, then how to do this? Actually I have made some search and did not found perfect solution.

### by using Sieve of Eratosthenes

By this method, we still find the primes from 2 to **x**, and until we found the largest prime that less than **x**. But remember that the space requirement is **O(n)**, be careful for large **x**.

```
public static int findLPTGbyES(int n) {
if (n < 2) {
throw new IllegalArgumentException("range should >= 2");
}
boolean[] isPrime = new boolean[n + 1];
// init
for (int i = 0; i <= n; i++) {
isPrime[i] = true;
}
isPrime[0] = false;
isPrime[1] = false;
int largestPrime = 2;
// sieve
for (int i = 2; i <= n; i++) {
if (isPrime[i]) {
if (i >= n) {
break;
}
largestPrime = i;
for (int j = 2 * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
return largestPrime;
}
```

Time complexity for this is **O(nloglogn)**.

### find largest prime from back-end

Begin from x - 1, check if x - 1 is a prime, if not, check x - 2, until find a prime.
Time complexity for this method is **O(n ^{3/2})**.

```
public static boolean isPrime(int num) {
if (num < 2) {
throw new IllegalArgumentException("num should >=2");
}
if (num == 2) {
return true;
}
for (int i = 2; i * i <= num; i++) {
if (num % i == 0) {
return false;
}
}
return true;
}
```

```
public static int findLargestPrimeLessThanGivenNum(int n) {
if (n < 2) {
throw new IllegalArgumentException("range should >= 2");
}
for (int i = n - 1; i >= 2; i--) {
if (isPrime(i)) {
return i;
}
}
return 2;
}
```

### Compare

Theoretically **O(nloglogn)** is much better than **O(n ^{3/2})**.

**but**for small x, such as

`Integer.MAX_VALUE`

, in my experiment It seems find largest prime from back-end is faster, maybe this is because the x is relatively small for prime. Another point you need to pay attention is for using Sieve of Eratosthenes, the space complexity is **O(n)**, be careful about your memory.

```
// find largest prime by brute-force from back end
startMili=System.currentTimeMillis();
int prime = Primer.findLargestPrimeLessThanGivenNum(1000000);
System.out.println("largest prime: " + prime);
endMili=System.currentTimeMillis();
System.out.println("time："+(endMili - startMili) + "ms");
System.out.flush();
// find largest prime by Erichsen Sieve
startMili=System.currentTimeMillis();
int prime2 = Primer.findLPTGbyES(1000000);
System.out.println("largest prime: " + prime2);
endMili=System.currentTimeMillis();
System.out.println("time："+(endMili - startMili) + "ms");
System.out.flush();
```

The test results:

```
largest prime: 999983
time：0ms
largest prime: 999983
time：15ms
```

## Source Code

Source code `Primer.java`

is here.