力扣日常 #204计算质数

 1 class Solution {
 2     public int countPrimes(int n) {
 3         int count = 0;
 4         for(int i = 2; i < n; i++){
 5             if(isPrime(i)) count++;
 6         }
 7         return count;
 8     }
 9 
10     public boolean isPrime(int n){
11         for(int i = 2; i < n; i++){
12             if(n % i == 0) return false;
13         }
14         return true;
15     }
16 }

 1 class Solution {
 2     public int countPrimes(int n) {
 3         int count = 0;
 4         for(int i = 2; i < n; i++){
 5             count += isPrime(i)?1:0;
 6         }
 7         return count;
 8     }
 9 
10     public boolean isPrime(int n){
11         for(int i = 2; i * i <= n; i++){
12             if(n % i == 0) return false;
13         }
14         return true;
15     }
16 }

 1 public int countPrimes(int n) {
 2     boolean[] notPrime = new boolean[n];
 3     int count = 0;
 4     for (int i = 2; i < n; i++) {
 5         if (!notPrime[i]) {
 6             count++;
 7             //将当前素数的倍数依次标记为非素数
 8             for (int j = 2; j * i < n; j++) {
 9                 notPrime[j * i] = true;
10             }
11         }
12     }
13     return count;
14 }