Eratosthenes sieve method

Prime numbers are also called prime numbers. The number of a natural number greater than 1 that is not divisible by any natural number except 1 and the integer itself. How do you determine which numbers within n are prime?

Eratosthenes sieve method

Eradosse, an ancient Greek mathematician, took a different approach to finding prime numbers: he put the numbers 2-n in a table, then drew a circle above 2 and crossed off other multiples of 2. The first number that’s not circled and not crossed out is 3, circled and crossed out other multiples of 3; Now the first number that is neither circled nor crossed out is 5, circled and crossed out other multiples of 5… And so on, until all numbers less than or equal to N are circled or crossed out. In this case, the circled and uncrossed numbers in the table are prime numbers less than N.

As shown below:



In fact, the iteration coefficient I does not need to traverse up to n-1, but only up to √(n-1). Reduction to absurdity:

  • If n-1 is not prime, then n-1 can be solved by multiplying two integer factors, n-1=d1×d2.
  • If d1 and d2 are greater than √(n-1), n-1 = d1 x d2 > √(n-1) x √(n-1) = n-1
  • Then n-1 must have a factor d1 or d2 less than or equal to square root of n-1, so that n-1 can be traversed by an integer less than or equal to square root of n-1.
  • Integers less than n minus 1 that are prime must be iterated.

If N is composite, there must be integers d1 and d2 greater than 1 and less than N such that N=d1×d2. If d1 and d2 are greater than √N, N = d1 x d2>√N x √N = N. And that’s not going to happen, so d1 and d2 must be less than or equal to square root of N. The code is as follows:

1 public class Solution { 2 public int countPrimes(int n) { 3 if(n <= 2) 4 return 0; 5 boolean[] prime = new boolean[n]; 6 for(int i =2; i < n; ++i) { 7 prime[i] = true; 8 } 9 for(int i = 2; i <= Math.sqrt(n-1); + + I) {/ / I can be 10 (n - 1) < =) if (prime) [I] {11 for (int j = I + I; j < n; j += i) { 12 prime[j] = false; 13 } 14 } 15 } 16 int count = 0; 17 for(int i = 2; i < n; ++i) { 18 if(prime[i]) 19 count++; 20 } 21 return count; 23 22}}Copy the code

Other methods

Any natural number can always be expressed as one of the following: 6N, 6N+1, 6N+2, 6N+3, 6N+4, 6N+5 (N= 0,1,2…) If N is greater than 1, 6N, 6N+2, 6N+3, 6N+4 are not prime numbers. They can only be 6N+1 or 6N+5, that is, 6N+1. Therefore, non-prime numbers can be greatly reduced through a 6N±1 sieve.