Count Prime
Given an integer n, return the number of prime numbers that are strictly less than n. https://leetcode.com/problems/count-primes/

Algorithm:

1
#include <stdio.h>
2
#include <math.h>
3
#include <stdbool.h>
4
5
bool isPrime(int n){
6
int sq = sqrt(n);
7
for(int j = 2; j <= sq; j++){
8
if( n % j == 0){
9
return false;
10
}
11
}
12
return true;
13
}
14
15
int countPrime(int N){
16
int count = 0;
17
for(int i = 2; i < N + 1; i++){
18
if(isPrime(i)){
19
count++;
20
}
21
}
22
return count;
23
}
24
Copied!

Version 2:

1
int countPrime2(int n){
2
if( n <= 2 ) return 0;
3
4
int primes[n + 1];
5
for (int i = 0; i < n + 1 ; i++){
6
primes[i] = 1;
7
}
8
9
int ret = 0;
10
for(int i = 2; i*i <= n; i++){
11
if(primes[i] == 1){
12
for(int j = i*i; j <= n; j+=i){
13
primes[j] = 0;
14
}
15
}
16
}
17
18
for(int i = 2; i < n; i++){
19
if( primes[i] == 1){
20
ret++;
21
}
22
}
23
return ret;
24
}
Copied!

Test:

1
int main(){
2
3
int N = 25;
4
printf("There are %d prime numbers whthin %d\n", countPrime(N), N);
5
return 0;
6
}
Copied!
Copy link