문제
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
에라토스테네스의 체를 활용해서 작성했다.
int countPrimes(int n) {
int *arr;
int count = 0;
arr = (int*) malloc((n+1) * sizeof(int));
for(int i=1; i<n+1; i++){
arr[i] = i;
}
for(int i=2; i<n+1; i++){
if(arr[i] == 0) continue;
else{
int j=2;
while(i*j <= n){
arr[i*j] = 0;
j++;
}
}
}
for(int i=2; i<n; i++){
if(arr[i]==0) continue;
else{
count++;
}
}
free(arr);
return count;
}