1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| public class CountPrimes {
public int countPrimes(int n) {
if (n < 2) {
return 0;
}
boolean[] noPri = new boolean[n];
noPri[0] = true;
noPri[1] = true;
for (int i = 2; i * i < n; i++) {
if (!noPri[i]) {
int c = i * i;
while (c < n) {
noPri[c] = true;
c += i;
}
}
}
int result = 0;
for (int i = 0; i < n; i++) {
if (!noPri[i]) {
result++;
}
}
return result;
}
}
|