Comment on page
Count Prime
Given an integer
n, return the number of prime numbers that are strictly less than n.
https://leetcode.com/problems/count-primes/#include <stdio.h>
#include <math.h>
#include <stdbool.h>
bool isPrime(int n){
int sq = sqrt(n);
for(int j = 2; j <= sq; j++){
if( n % j == 0){
return false;
}
}
return true;
}
int countPrime(int N){
int count = 0;
for(int i = 2; i < N + 1; i++){
if(isPrime(i)){
count++;
}
}
return count;
}
int countPrime2(int n){
if( n <= 2 ) return 0;
int primes[n + 1];
for (int i = 0; i < n + 1 ; i++){
primes[i] = 1;
}
int ret = 0;
for(int i = 2; i*i <= n; i++){
if(primes[i] == 1){
for(int j = i*i; j <= n; j+=i){
primes[j] = 0;
}
}
}
for(int i = 2; i < n; i++){
if( primes[i] == 1){
ret++;
}
}
return ret;
}
int main(){
int N = 25;
printf("There are %d prime numbers whthin %d\n", countPrime(N), N);
return 0;
}
Last modified 1yr ago