Preface explains

Algorithm learning, daily brush record.

Subject to connect

Count prime Numbers

The subject content

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

Example 1:

Enter n = 10

Output: 4

Explanation: There are four prime numbers less than 10:2, 3, 5, and 7.

Example 2:

Enter n = 0

Output: 0

Example 3:

Enter n = 1

Output: 0

Tip:

0 <= n <= 5 * 10^6

The analysis process

According to the traditional method, by traversing from 2 to n-1, judge whether they are prime numbers one by one and count the number.

Since starting at 3, primes are always odd, the traversal increases by 2 each time, reducing the number of traversals.

And to determine whether each number is prime, you only need to traverse the square root of the number, because a number can never have a factor greater than its square root.

So the code looks like this:

Class Solution {public int countPrimes(int n) {if (n < 3) {// countPrimes less than 2. } else {// The number of primes starts with 1, because 2 is a prime number. For (int I = 3; for (int I = 3; i < n; I += 2) {// Whether prime Boolean isPrime = true; For (int j = 3; j * j <= i; J += 2) {if (I % j == 0) {if (I % j == 0) { break; }} if (isPrime) {// The number of primes plus 1 ++num; } } return num; }}}Copy the code

But the commit results show that the run timed out.

If x is prime, then 2x, 3x… It’s definitely not prime.

So we can go the other way, we can go composite, and what’s left is prime.

We can use a Boolean array to hold the numbers up to n, marking each number as prime or composite.

If a prime number is found, then the prime number is iterated from 2 to n until it is less than n. Since x is prime, multiples of x must not be prime, so all iterated are composite numbers, marked as true.

Is it possible for a composite number to be marked as prime, false?

We can assume that if a composite number is marked false, it must be a multiple of some previous prime number, but we have checked the multiple of all primes before, so if it is a composite number, it must be marked true.

Therefore, no composite number will be marked as prime.

To solve the code

So we need to exchange space for time, using The Escherichia algorithm, the solution code is as follows:

Class Solution {public int countPrimes(int n) {count = 0; Boolean [] flag = new Boolean [n]; Boolean [] flag = new Boolean [n]; For (int I = 2; i < n; i++) { if (! Flag [I]) {// If I is 0, find the prime number, the number of primes plus 1 ++count; // If x is prime, then 2x, 3x... // If x is prime, then 2x, 3x... Int j = I + I; int j = I + I; j < n; j += i) { flag[j] = true; Return count; return count; return count; return count; }}Copy the code

Submit the results

The execution time was 51ms, the time beat 59.83% of users, the memory consumption was 41.7MB, and the space beat 65.44% of users.

The original link

Counting primes