Algorithm
Problem Name: 204. Count Primes
Given an integer n, return the number of prime numbers that are strictly less than n.
Example 1:
Input: n = 10 Output: 4 Explanation: There are 4 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
Constraints:
0 <= n <= 5 * 106
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
int countPrimes(int n) {
bool *flag = (bool *)calloc(n + 1, sizeof(bool));
int *prime = (int *)calloc(n / 2, sizeof(int));
flag[0] = 1;
flag[1] = 1;
int i, j;
int count = 0;
for (i = 2; i < n; i++) {
if (flag[i] == 0) { /* i is prime */
prime[count ++] = i;
}
for (j = 0; j < count && i * prime[j] < n; j++) {
flag[i * prime[j]] = 1;
if (i % prime[j] == 0) { /* important */
break;
}
}
}
return count;
}
int main() {
printf("%d\n", countPrimes(5000000));
return 0;
}
Input
n = 10
Output
4
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const countPrimes = function (n) {
const memo = Array(n).fill(false)
let res = 0
for (let i = 2; i < n; i++) {
if (memo[i] === false) {
res++
for (let j = 2; i * j < n; j++) {
memo[i * j] = true
}
}
}
return res
}
Input
n = 10
Output
4
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def countPrimes(self, n):
primes = [i for i in range(2, n)]
for i in range(2, n):
for prime in primes:
if i ** (prime - 1) % prime != 1 and prime > i:
primes.remove(prime)
return len(primes)
Input
n = 0
#4 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _0204_CountPrimes
{
public int CountPrimes(int n)
{
var notPrime = new bool[n];
var count = 0;
for (int i = 2; i < n; i++)
{
if (!notPrime[i])
{
count++;
for (int j = 2; j * i < n; j++)
notPrime[i * j] = true;
}
}
return count;
}
}
}
Input
n = 0