|
1 | 1 | packagecom.fishercoder.solutions; |
2 | 2 |
|
3 | | -/** |
4 | | - * 204. Count Primes |
5 | | - * |
6 | | - * Description: |
7 | | -
|
8 | | - Count the number of prime numbers less than a non-negative number, n. |
9 | | -
|
10 | | - Hint: |
11 | | -
|
12 | | - Let's start with a isPrime function. To determine if a number is prime, we need to check if it is not divisible by any number less than n. |
13 | | - The runtime complexity of isPrime function would be O(n) and hence counting the total prime numbers up to n would be O(n2). Could we do better? |
14 | | -
|
15 | | - As we know the number must not be divisible by any number > n / 2, |
16 | | - we can immediately cut the total iterations half by dividing only up to n / 2. Could we still do better? |
17 | | -
|
18 | | - Let's write down all of 12's factors: |
19 | | -
|
20 | | - 2 × 6 = 12 |
21 | | - 3 × 4 = 12 |
22 | | - 4 × 3 = 12 |
23 | | - 6 × 2 = 12 |
24 | | - As you can see, calculations of 4 × 3 and 6 × 2 are not necessary. Therefore, we only need to consider factors up to √n because, |
25 | | - if n is divisible by some number p, then n = p × q and since p ≤ q, we could derive that p ≤ √n. |
26 | | -
|
27 | | - Our total runtime has now improved to O(n1.5), which is slightly better. Is there a faster approach? |
28 | | -
|
29 | | - public int countPrimes(int n) { |
30 | | - int count = 0; |
31 | | - for (int i = 1; i < n; i++) { |
32 | | - if (isPrime(i)) count++; |
33 | | - } |
34 | | - return count; |
35 | | - } |
36 | | -
|
37 | | - private boolean isPrime(int num) { |
38 | | - if (num <= 1) return false; |
39 | | - // Loop's ending condition is i * i <= num instead of i <= sqrt(num) |
40 | | - // to avoid repeatedly calling an expensive function sqrt(). |
41 | | - for (int i = 2; i * i <= num; i++) { |
42 | | - if (num % i == 0) return false; |
43 | | - } |
44 | | - return true; |
45 | | - } |
46 | | -
|
47 | | - The Sieve of Eratosthenes is one of the most efficient ways to find all prime numbers up to n. |
48 | | - But don't let that name scare you, I promise that the concept is surprisingly simple. |
49 | | -
|
50 | | - Sieve of Eratosthenes: algorithm steps for primes below 121. "Sieve of Eratosthenes Animation" by SKopp is licensed under CC BY 2.0. |
51 | | - We start off with a table of n numbers. Let's look at the first number, 2. We know all multiples of 2 must not be primes, so we mark |
52 | | - them off as non-primes. Then we look at the next number, 3. Similarly, all multiples of 3 such as 3 × 2 = 6, 3 × 3 = 9, ... must not |
53 | | - be primes, so we mark them off as well. Now we look at the next number, 4, which was already marked off. |
54 | | - What does this tell you? Should you mark off all multiples of 4 as well? |
55 | | - 4 is not a prime because it is divisible by 2, which means all multiples of 4 must also be divisible by 2 and were already marked off. |
56 | | - So we can skip 4 immediately and go to the next number, 5. |
57 | | - Now, all multiples of 5 such as 5 × 2 = 10, 5 × 3 = 15, 5 × 4 = 20, 5 × 5 = 25, ... can be marked off. |
58 | | - There is a slight optimization here, we do not need to start from 5 × 2 = 10. Where should we start marking off? |
59 | | -
|
60 | | - In fact, we can mark off multiples of 5 starting at 5 × 5 = 25, because 5 × 2 = 10 was already marked off by multiple of 2, |
61 | | - similarly 5 × 3 = 15 was already marked off by multiple of 3. |
62 | | - Therefore, if the current number is p, we can always mark off multiples of p starting at p2, then in increments of p: p2 + p, p2 + 2p, ... |
63 | | - Now what should be the terminating loop condition? |
64 | | -
|
65 | | - It is easy to say that the terminating loop condition is p < n, which is certainly correct but not efficient. Do you still remember Hint #3? |
66 | | - Yes, the terminating loop condition can be p < √n, as all non-primes ≥ √n must have already been marked off. When the loop terminates, |
67 | | - all the numbers in the table that are non-marked are prime. |
68 | | -
|
69 | | - The Sieve of Eratosthenes uses an extra O(n) memory and its runtime complexity is O(n log log n). |
70 | | - For the more mathematically inclined readers, you can read more about its algorithm complexity on Wikipedia. |
71 | | -
|
72 | | - public int countPrimes(int n) { |
73 | | - boolean[] isPrime = new boolean[n]; |
74 | | - for (int i = 2; i < n; i++) { |
75 | | - isPrime[i] = true; |
76 | | - } |
77 | | -
|
78 | | - // Loop's ending condition is i * i < n instead of i < sqrt(n) |
79 | | - // to avoid repeatedly calling an expensive function sqrt(). |
80 | | -
|
81 | | - for (int i = 2; i * i < n; i++) { |
82 | | - if (!isPrime[i]) continue; |
83 | | - for (int j = i * i; j < n; j += i) { |
84 | | - isPrime[j] = false; |
85 | | - } |
86 | | - } |
87 | | - int count = 0; |
88 | | - for (int i = 2; i < n; i++) { |
89 | | - if (isPrime[i]) count++; |
90 | | - } |
91 | | -
|
92 | | - return count; |
93 | | - } |
94 | | - */ |
95 | 3 | publicclass_204 { |
96 | 4 |
|
97 | 5 | publicstaticclassSolution1 { |
|