This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

1. Title Description

Count prime Numbers

Count the number of primes less than the non-negative integer n.

Example 1:

Input: n = 10 Output: 4 Explanation: There are four prime numbers less than 10, they are 2, 3, 5, 7. Example 2:

Input: n = 0 Output: 0 Example 3:

Input: n = 1 Output: 0

Tip:

0 <= n <= 5 * 106

Second, train of thought analysis

  • Obtain the number of nonnegative primes less than n. First we need to know what a prime number is.
  • The first is exposure cracking. At first glance, it seems like there’s nothing else to do but brute force. And the way violence works is very simple with a two-level cycle.
public int countPrimes(int n) {
    int total = 0;
    for (int i = 2; i < n; i++) {
        int j=2;
        for (j = 2; j < i; j++) {
            if (i % j == 0) {
                break; }}if(j == i) { total++; }}return total;
}
Copy the code
  • As I mentioned before, algorithms are not about solving problems. This is the result of the above violent method posted to Leetcode

  • Even if Leetcode passes, this solution is not optimal.

Iii. Upgrade path +AC code

Reduce violence

  • I don’t know if you’ve noticed what numbers you get when you multiply 6. If you look closely at the figure above, you’ll see that after 2 there is repetition.

6 = 6 ∗ 6 6=\sqrt{6} * \sqrt{6}
  • In fact, the final threshold is 6 development. After the square root of 6, you get duplicate numbers. So all we need to do to figure out whether something is prime is loop up to the square root
public int countPrimes(int n) {
    int total = 0;
    for (int i = 2; i < n; i++) {
        boolean flag = false;
        for (int j = 2; j*j <= i; j++) {
            if (i % j == 0) {
                flag=true;
                break; }}if (!flag) {
            total++;
        }
    }
    return total;
}
Copy the code
  • We’ll change that to the square root, but running leetcode will still result in a timeout. The upgrade ended in failure.

Mr Sieve method

  • To be honest, the problem is simple, but for a novice like me, it really didn’t work out at the beginning. When I read the official solution to the problem after the escher method.
  • The Escher method takes into account the correlation between data. Let’s say we detect that 3 is prime, then1 * 3; 2 * 3; 3 * 3... ; n*3These data are composite numbers, so there is no need to judge whether they are prime or not in the loop detection. That would greatly reduce the number of searches we’d have to make

  • When we detect that 2 is prime, theta corresponds4，6,8,10,12,14Will be marked composite. Because they’re looking at numbers below n, we don’t have to worry about 16 here

  • And then we continue to find composite numbers based on 3.

  • When we get to node 4, node 4 defaults to false but is marked true, indicating that node 4 has been evaluated as composite by the primes above, so we skip it here. We definitely know that we’re going to extend it by 5

  • I’m going to extend 7,11,13, but I’m not going to do that
public int countPrimes2(int n) {
    int total = 0;
    // Construct an array of state bits of the same length. The default is false for prime numbers
    boolean[] primes = new boolean[n];
    for (int i = 2; i < n; i++) {
        if(! primes[i]) { total++;for (int j = 2 * i; j < n; j += i) {
                primes[j] = true; }}}return total;
}
Copy the code

Mr Sieve method 2

  • Although the Escher method has been tested by Leetcode. But there is still room for improvement in execution. Moreover, it is not difficult to find that a lot of data are repeated when we analyze the implementation process of Escher method.
  • In the illustration above I also used different colors to distinguish the extensions of different prime numbers. Let’s say 10 is the first time2 * 5The 2 prime numbers are rendered composite. But 10 will be again5 * 2Render composite. This truth is the same problem with the escalation of violence law above. In order to avoid similar10 = 2 * 5In the multiplier position swap problem, we can start with the square of the prime number when extending, because the prime number before will definitely be rendered by the previous prime number

public int countPrimes3(int n) {
    int total = 0;
    // Construct an array of state bits of the same length. The default is false for prime numbers
    boolean[] primes = new boolean[n];
    for (int i = 2; i < n; i++) {
        if(! primes[i]) { total++;if ((long)i * i >= n) {
                continue;
            }
            for (int j = i * i; j < n; j += i) {
                //System.out.println("index="+j+"i="+i);
                primes[j] = true; }}}return total;
}
Copy the code
  • There is a slight improvement in both time and space. However, after the upgrade, we need to deal with arrays that are out of bounds. Because we squared it.

Four,

  • Why did you choose this one? Because when I saw this problem at the beginning, I didn’t think of any other method except violent method (after all, my own algorithm is not good).
  • Secondly, the algorithm takes into account the correlation between data. Association prevents us from going through the number. It’s actually the brute force method but it’s just a refinement of the brute force method