The title information

Subject address: leetcode-cn.com/problems/co…

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

Example 1:

Enter n =10Output:4Explanation: less than10The primes of phi have a total of4Student: Yes, they are2.3.5.7 。
Copy the code

Example 2:

Enter n =0Output:0
Copy the code

Example 3:

Enter n =1Output:0
Copy the code

Solution one: enumeration of violence

Count the number of primes from 0 to n, and then judge whether each number is prime. If it is, count plus one, if it is not, it will not change, and finally return the counting result.

To determine whether a number is prime, we all know that a number that is divisible only by itself and 1 is prime (1 does not count). So to determine whether 7 is prime, we need to determine whether it is divisible by any number from 2 to 6. We don’t need to know because a number cannot be divisible by more than half of itself. So if the number “number” is prime, see if the integers between “number” and “number/2” are divisible

After understanding, we first define a judge method to judge whether it is prime:

public boolean judge(int number){
	// Check whether the number between 2 and number/2 is divisible by number
	for(int i = 2; i<=number/2; i++){
		if(number%i==0) return false;
	}
	return true;
}
Copy the code

After having the judge method, the result is obtained with the traversal count:

public int countPrimes(int n) {
	// The counter is initialized to 0
	int result = 0;
	for (int i = 2; i < n; i++){
		// count incremented by 1 if judge is prime, otherwise unchanged
		result = judge(i) ? ++result : result;
	}
	return result;
}
Copy the code

Space: a counter variable, hence complexity O(1),

Time: each number from 0 to n needs to be traversed, and each number needs to be traversed to determine whether it is prime. The complexity is O(n^2).

Submission Results:

You can see that most of the test cases passed, proving that the solution results are no problem. However, in the face of large numbers such as 499979, too many calculations result in timeouts, so we need to see how to optimize the time complexity.

In fact, it can be found that if a number is divisible by the number from 2 to number-1, I subconsciously thought that I could reduce the size by half by just judging from 2 to number/2.

But you can actually scale it down

12 = 2 * 6
12 = 3 * 4
Copy the code

Like this 12, you don’t have to divide it into 6,6 is the same thing as 2. If you divide a number by a number, you get an integer number/x = y, so the two factors x * y are one and the other, and we just divide the smaller side by the smaller side to see if it’s divisible. So we take the square root.


n u m b e r \sqrt{number}

Like determining whether 23 is prime, determine 2 to 4.79….


23 \sqrt{23}

So you just need to see if 2, 3, 4 are divisible, instead of going from 2 to 11.

public Boolean judge(int number){
	// Boundary conditions 0 and 1 return directly
	if(number == 0 || number == 1) return false;
	// Iterate over the number between 2 and the square root of number to see if it is divisible by number
	for (int i = 2; i*i<=number; i++){
		if(number%i==0) return false;
	}
	return true;
}
Copy the code

Change I <=number /2 to I * I <=number /2, reduce the time complexity by one square root: O (nlogn), still not enough, still timeout.

Solution two: Eradosse sieve method

Solution when we are through the two traverse to solve the problem: one is the traverse every number to judge, the second is the process of the current digital judging whether it is a prime number within the scope of the need to traverse the digital divide, time complexity is very high, but we from 2 to judge whether it is a prime number 1 digital narrowing the scope of half (square).

But that’s not enough. The process for determining prime numbers is optimized. So the only thing that can be optimized is the first step which is to go through each number and make a judgment.

{% note info no-icon %}

  1. Is it possible to judge without going through every one of them?
  2. Do primes appear regularly in consecutive numbers?
  3. If this number is prime then everybody is prime? You don’t have to judge them all.

{% endnote %}

I was drawing a little bit on paper, and I didn’t really find any patterns that would help me solve this, and I looked at this online and it was really nice to use the Eradosite sieving with arrays.

So a multiple of a prime number that’s not prime, so x is prime but 2x, 3x, 4x is not prime, 2x is divisible at least 2, 3x is divisible at least 3.

But I really didn’t think to solve the problem. The main point is that when we iterate from prime number 2 one by one, we can’t iterate faster than we can exclude, so we can assume that the current number we iterate over is prime if it’s not excluded. The following manual enumeration can be seen:

2 3 4 5 6 7 8 9Like right now2-9Prime numbers: from prime numbers2At first, the prime count is incremented and excluded4,6,8It's not prime. To traverse the3Prime numbers, prime numbers count plus one and exclude6,9It's not prime. To traverse the4Find has been excluded from traversal5Prime number, prime number count plus to6Find has been excluded from traversal7Prime number, prime number count plus to8Find has been excluded from traversal9The final prime number count is4
Copy the code

You can also see that there is one point that needs to be optimized, and each number is excluded from being twice as large as it is: twice, three times, four times, and so on. You can see that 2 excludes, 3 excludes. That is, there are some numbers that have already been excluded, so you don’t have to do any extra steps when you’re doing the exclusion, and that’s the point of optimization. If you think about it, 3 starts at a multiple of 2. It must have been 3 times 2 before. The only way to avoid repetition is to start at multiples larger than yourself, because the first number has been ruled out by other smaller numbers. 2 x 5 and 3 x 5 should not be excluded because they have been excluded by the previous number. We should start with our own square.

Here’s another GIF:

The implementation is essentially two loops, one to iterate over each number, and the other to double each number and eliminate the resulting number. Data structures are marked with byte arrays, which are prime numbers marked 0 and changed to 1 when excluded

public int countPrimes(int n) {
	// The counter is initialized to 0
	int result = 0;
	/** * define array, mark whether the number is excluded * < n then exclude 0 and 1, there are n-1 need to determine ** initialize array default is 0, wait for each mark starting from 2 */
	int[] arr = new int[n];
	// iterate over each number
	for (int i = 2; i < n; i++){
		// is a prime number, do multiple exclusion, starting with square
		if(arr[i] == 0){
			result++;
			for(int j = i * i; j < n; j+=i){
				arr[j] = 1; }}}return result;
}
Copy the code

Int n=499979; int n=499979;

After all, arr can only be selected if j < n [j]. Then I noticed that the index out of bounds is -2146737495. It’s the product of two ints that exceeds the range of int, which is j, and j gets a negative value and goes into the loop. So when you get j, give it a long, make sure it’s less than n, and then give it a strong int

I’m going to do a space optimization here, which is that the array only holds zeros or ones, so I’m going to use a small byte array

The code is as follows:

public int countPrimes(int n) {
    int result = 0;
    byte[] arr = new byte[n];
	for (int i = 2; i < n; i++){
        if(arr[i] == 0){
            result++;
        	for(long j = (long)i * i; j < n; j+=i){
                arr[(int)j] = 1; }}}return result;
}
Copy the code

So even though it’s going through twice, the number that’s actually going through the inner loop is not going through the outer loop, how many times n should it be in terms of time complexity

It uses byte arrays for space, which take up n bytes. The complexity of O (n)

The test results

Solution three: linear screening method

In the case of erado, the Ehrenheit screening, there was a question mark, right? We avoid repeated culling by filtering composite numbers by multiples of prime numbers squared

Exclude the composite of prime x x * x (x +)1 )
x * ( x + 2 )
x * ( x + 3)...Copy the code

Although it avoids the case where 2 excludes 6 and 3 excludes 6. Because 3 goes straight from 9,12,15. But 12 is still excluded by both 2 and 3.

We solved the problem of eliminating duplicate numbers before the square number, but there are still conflicting numbers after the square number and there are duplicate eliminations.

Now we want each composite number to be excluded by the smallest of its many pairs of factors, and not by any other factors

Sum Numbers factor
4 2
6 2, 3,
8 2, 4
9 3
10 2, 5
12 Two, three, four, six

Linear screening is used to exclude each number, and each exclusion is current and does not conflict with the future. The point is that any composite number that has one of its smallest factors must be a prime number, so take the prime number and multiply each number to exclude it. So how do you avoid double culling?

Here are a few:

2To rule out4
3To rule out6,9
4To rule out8 （4by2Exclude, therefore its3times5Times should be2Solve)5To rule out10,15,25
6To rule out12(6Can be2Exclude, do not need to remove other times)7To rule out14,21,35,49
8To rule out16(8Is made up of2Can be ruled out9To rule out18,27(9Is be3Can be ruled out)10To rule out20(10Is be2Excluded)Copy the code

It’s like four excludes eight, why not twelve. Because 4 has a minimum factor of 2. So 3 times or 5 times it has a factor of 2, which means it’s followed by a number that’s twice as big as 12 to be excluded by that number. Only the most recent one is excluded at a time, so that the first one is left behind, and the last one is left behind. Like 9, which has a minimum factor of 3, he should exclude 2×9 and 3×9. The 18 that comes out of the smallest factor of 2 is the closest thing to 9, and 2 is not the least factor of 9 it’s the least factor of 3, which makes 3 excluded and the closest thing to 9 is 3 times 9, and then there’s no more numbers to pick it out.

Pass the number of minimum factor screening backwards, each time the nearest layer is screened, you can complete the non-repeat and always go ahead of the screening

The code is as follows:

public int countPrimes(int n) {
    // Tag filter
    byte[] arr = new byte[n];
    // Minimum factor (prime)
    List<Integer> numbers = new ArrayList<>();
	for (int i = 2; i < n; i++){
        if(arr[i] == 0) numbers.add(i);
        for(int j = 0; j < numbers.size() && numbers.get(j) * i < n; j++){
            arr[numbers.get(j) * i] = 1;
            if(i % numbers.get(j) == 0) break; }}return numbers.size();
}
Copy the code

In this case, time and space are order n

It actually looks a little bit less efficient than The Eichler filter, but this thing is mostly a matter of operators.

conclusion

Subject to find a number of less than the number of prime Numbers, which method a is probably the first reaction is according to the solution of the question, though it is realized that the solution to go detour but did not figure out screening method, on the Internet to see the erichsen screening method is indeed a can be used for problem solving, although this thing should be everyone know the truth, but has not realized that the strict reasoning. And then you can think of linear screening, which is sort of a vertical versus a horizontal deduction. So in addition to the realization of the idea, the optimization of the code in space and time is also the optimization point after the final realization of the idea. Things like filter tags that only store 0/1 so they only take up one bit, if we only store 8 ints it would take up 8×32 bits. There is no bit array in Java, the smallest is 8 bits in bytes, 8×8 bits. We don’t have an array of bits so can we have eight zeroes and one zeroes and only eight bits of space to store them? Well, instead of an array we can just use one byte which has eight bits and each one holds a zero or a one, so that’s a point to think about. The second is the time for linear filtering method contrast erichsen screening method on time complexity is just said in the Java implementation of ascension this linear filter USES some like take over the operator and so on can affect the execution efficiency, this time we are dealing with some arithmetic can think on the bit operations, some can be replaced by a computing some can’t. Is mainly for the first three ideas on the development of learning and work may be a lot of ideas are bound, may change the state of the high school a lot of things can be reasoning, the second is about space for tag types need to be considered in place, the third is the operation can achieve the same result through bit operations to improve the practical efficiency.