LeetCode – Count Primes (Java)
Count the number of prime numbers less than a non-negative number, n
This solution is the implementation of Sieve of Eratosthenes.
X. Using BitSet
https://leetcode.com/discuss/33528/accepted-java-code-with-bitset
java.util.BitSet.nextClearBit(int)
https://gist.github.com/gcrfelix/4c11d5107f73ff1e33d5
// new method: 10/28
public int countPrimes(int n) {
if(n <= 2) return 0;
boolean[] notPrime = new boolean[n];
int count = 0;
for(int i=2; i<n; i++) {
if(notPrime[i] == false) {
count ++;
for(int j=2; i*j<n; j++) {
notPrime[i*j] = true;
}
}
}
return count;
}
public int countPrimes(int n) {
if(n <= 2) {
return 0;
}
int count = 1; // count = 1 because 2 is prime, add it to total first
for(int i=3; i<n; i++) {
if(isPrime(i)) {
count ++;
}
}
return count;
}
private boolean isPrime(int n) {
if(n%2 == 0) { // even numbers can't be prime except 2.
return false;
}
for(int i=3; i*i<=n; i+=2) { // We start from 3 and add 2 to avoid even numbers(we should get 3, 5, 7 etc.).
if(n%i == 0) {
return false;
}
}
return true;
}
http://algobox.org/count-primes/
https://leetcode.com/discuss/35195/my-simple-java-solution
public int countPrimes(int n) { boolean[] notPrime = new boolean[n]; int count = 0; for (int i = 2; i < n; i++) { if (notPrime[i] == false) { count++; for (int j = 2; i*j < n; j++) { notPrime[i*j] = true; } } } return count; }
http://bookshadow.com/weblog/2015/04/27/leetcode-count-primes/
http://www.zhuangjingyang.com/leetcode-count-primes/
public int countPrimes(int n) { boolean notPrime[] = new boolean[n + 2]; notPrime[0] = notPrime[1] = true; for (int i = 2; i * i < n; i++) { if (!notPrime[i]) { int c = i * i; while (c < n) { notPrime[c] = true; c += i; } } } int ans = 0; for (int i = 0; i < n; i++) { if (!notPrime[i]) ans ++; } return ans; }
http://blog.csdn.net/myself9711/article/details/45437229
http://www.programcreek.com/2014/04/leetcode-count-primes-java/
Count the number of prime numbers less than a non-negative number, n
This solution is the implementation of Sieve of Eratosthenes.
X. Using BitSet
https://leetcode.com/discuss/33528/accepted-java-code-with-bitset
java.util.BitSet.nextClearBit(int)
* Returns the index of the first bit that is set to {@code false}
* that occurs on or after the specified starting index.
java.util.BitSet.nextSetBit(int)
* Returns the index of the first bit that is set to {@code true}
* that occurs on or after the specified starting index. If no such
* bit exists then {@code -1} is returned.
java.util.BitSet.set(int, int)
* Sets the bits from the specified {@code fromIndex} (inclusive) to the
* specified {@code toIndex} (exclusive) to {@code true}.
java.util.BitSet.clear(int, int)
* Sets the bits from the specified {@code fromIndex} (inclusive) to the
* specified {@code toIndex} (exclusive) to {@code false}.
java.util.BitSet.cardinality()
* Returns the number of bits set to {@code true} in this {@code BitSet}.
public int countPrimes(int n) {
BitSet bs = new BitSet(n);
bs.set(0); bs.set(1);
int ind = 0, count = 0;
while(ind < n){
ind = bs.nextClearBit(ind + 1);
if(ind >= n)
return count;
count++;
for(int i = 2 * ind; i < n; i += ind)
bs.set(i);
}
return count;
}public int countPrimes(int n) { if (n <= 1) { return 0; } BitSet set = new BitSet(n); set.set(0, 2); for (int i = 2; i < n; i++) { if (!set.get(i)) { for (int j = i*2; j < n; j+=i) { set.set(j); } } } return n-set.cardinality(); }
// new method: 10/28
public int countPrimes(int n) {
if(n <= 2) return 0;
boolean[] notPrime = new boolean[n];
int count = 0;
for(int i=2; i<n; i++) {
if(notPrime[i] == false) {
count ++;
for(int j=2; i*j<n; j++) {
notPrime[i*j] = true;
}
}
}
return count;
}
public int countPrimes(int n) {
if(n <= 2) {
return 0;
}
int count = 1; // count = 1 because 2 is prime, add it to total first
for(int i=3; i<n; i++) {
if(isPrime(i)) {
count ++;
}
}
return count;
}
private boolean isPrime(int n) {
if(n%2 == 0) { // even numbers can't be prime except 2.
return false;
}
for(int i=3; i*i<=n; i+=2) { // We start from 3 and add 2 to avoid even numbers(we should get 3, 5, 7 etc.).
if(n%i == 0) {
return false;
}
}
return true;
}
http://algobox.org/count-primes/
The accurate time complexity is which is not trivial to show. But, it is easy to show a complexity of .
The complexity of the algorithm isO(n(logn)(loglogn))
bit operations.
How do you arrive at that?
That the complexity includes the
loglogn
term tells me that there is a sqrt(n)
somewhere.
Suppose I am running the sieve on the first 100 numbers (
n = 100
), assuming that marking the numbers as composite takes constant time (array implementation), the number of times we use mark_composite()
would be something liken/2 + n/3 + n/5 + n/7 + ... + n/97 = O(n^2)
And to find the next prime number (for example to jump to
7
after crossing out all the numbers that are multiples of 5
), the number of operations would be O(n)
.- Your n/2 + n/3 + n/5 + … n/97 is not O(n^2), because the number of terms is not constant. [Edit after your edit: O(n2) is too loose an upper bound.] A loose upper-bound is n(1+1/2+1/3+1/4+1/5+1/6+…1/n) (sum of reciprocals of all numbers up to n), which is O(n log n): see Harmonic number. A more proper upper-bound is n(1/2 + 1/3 + 1/5 + 1/7 + …), that is sum of reciprocals of primes up to n, which is O(n log log n). (See here or here.)
- The "find the next prime number" bit is only O(n) overall, amortized — you will move ahead to find the next number only n times in total, not per step. So this whole part of the algorithm takes only O(n).
So using these two you get an upper bound of O(n log log n) + O(n) = O(n log log n) arithmetic operations. If you count bit operations, since you're dealing with numbers up to n, they have about log n bits, which is where the factor of log n comes in, giving O(n log n log log n) bit operations.
public int countPrimes(int n) { if (n <= 2) return 0; // init an array to track prime numbers boolean[] primes = new boolean[n]; // we can use notPrimes for (int i = 2; i < n; i++) primes[i] = true; for (int i = 2; i <= Math.sqrt(n - 1); i++) { // or for (int i = 2; i <= n-1; i++) { if (primes[i]) { for (int j = i + i; j < n; j += i) primes[j] = false; } } int count = 0; for (int i = 2; i < n; i++) { if (primes[i]) count++; } return count; } |
public int countPrimes(int n) { boolean[] notPrime = new boolean[n]; int count = 0; for (int i = 2; i < n; i++) { if (notPrime[i] == false) { count++; for (int j = 2; i*j < n; j++) { notPrime[i*j] = true; } } } return count; }
http://bookshadow.com/weblog/2015/04/27/leetcode-count-primes/
http://www.zhuangjingyang.com/leetcode-count-primes/
public int countPrimes(int n) { boolean notPrime[] = new boolean[n + 2]; notPrime[0] = notPrime[1] = true; for (int i = 2; i * i < n; i++) { if (!notPrime[i]) { int c = i * i; while (c < n) { notPrime[c] = true; c += i; } } } int ans = 0; for (int i = 0; i < n; i++) { if (!notPrime[i]) ans ++; } return ans; }
This solution exceeds time limit.
public int countPrimes(int n) { n = n-1; ArrayList<Integer> primes = new ArrayList<Integer>(); if(n<=1) return 0; if(n==2) return 1; if(n==3) return 2; primes.add(2); primes.add(3); for(int i=4; i<=n; i++){ boolean isPrime = true; for(int p: primes){ int m = i%p; if(m==0){ isPrime = false; break; } } if(isPrime){ primes.add(i); } } return primes.size(); }
http://blog.csdn.net/myself9711/article/details/45437229
Time Complexity: O(n*n)
class Solution: # @param {integer} n # @return {integer} def countPrimes(self, n): result_dict = {0: 0, 1: 1, 2: 2} for key in range(3, n+1): if self.isPrime(key): result_dict[key] = result_dict[key-1] + 1 else: result_dict[key] = result_dict[key-1] return result_dict[n] def isPrime(self, n): if n == 0: return False if n == 1 or n == 2: return True for divide in range(2, n): if n % divide == 0: return False return True
http://www.programcreek.com/2014/04/leetcode-count-primes-java/
public int countPrimes(int n) { n = n-1; ArrayList<Integer> primes = new ArrayList<Integer>(); if(n<=1) return 0; if(n==2) return 1; if(n==3) return 2; primes.add(2); primes.add(3); for(int i=4; i<=n; i++){ boolean isPrime = true; for(int p: primes){ int m = i%p; if(m==0){ isPrime = false; break; } } if(isPrime){ primes.add(i); } } return primes.size(); }Read full article from LeetCode – Count Primes (Java)