## 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:

## 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**.

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})**.

### 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.