Вопрос. Подсчитайте количество простых чисел, меньших неотрицательного числа, n.

Пример:

Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

Полностью вопрос можно посмотреть здесь.

Подход 1. Начнем с самого очевидного —

//Approach 1:
//Runtime: 465ms
//Memory usage: 32.8MB
class Solution {
    public int countPrimes(int n) {
        int count = 0;
        for(int i = 2; i<n; i++){
            if(isPrime(i)){
                count++;
            }
        }
        return count;
    }
    
    private boolean isPrime(int n) {
        int d = 2;
        int root = (int) Math.sqrt(n);
        while(d<=root){
            if(n%d==0){
                return false;
            }
            d++;
        }
        return true;
    }
}

Подход 2. В подходе 1 логика определения того, является ли число простым или нет, включала проверку делимости числа на делители, начинающиеся с 2 и заканчивая квадратным корнем из этого числа.

Проверка делимости в основном требует, чтобы мы проверяли только простые делители. Для этого мы можем использовать список для хранения всех простых чисел.

//Approach 2:
//Runtime: 151ms
//Memory usage: 38MB
class Solution {
    List<Integer> primes = new ArrayList();
    int count = 0;
    
    public int countPrimes(int n) {
        primes = new ArrayList();
        count = 0;
        for(int i = 2; i<n; i++){
            isPrime(i);
        }
        return count;
    }
    
    private boolean isPrime(int n) {
        int root = (int) Math.sqrt(n);
        if(count==0){
            int d = 2;
            while(d<=root){
                if(n%d==0){
                    return false;
                }
                d++;
            }
        } else {
            
            for(int i = 0; i<count && primes.get(i)<=root; i++){
                if(n%primes.get(i)==0){
                    return false;
                }
            }
        }
        count++;
        primes.add(n);
        return true;
    }
}

Подход 3. Давайте позаимствуем некоторые идеи у некоторых великих умов. Этот подход использует — Решето Эратосфена. (Проверьте страницу вики!)

Этот алгоритм удаляет все составные числа, так что в итоге остаются только простые. Начинаем с числа, если оно простое, то отмечаем все его кратные. Мы делаем это итеративно.

Небольшая оптимизация будет состоять в том, чтобы проверять только квадратный корень из «n», так как числа, превышающие это, будут иметь кратность, большую, чем «n».

//Approach 3:
//Runtime: 9ms
//Memory usage: 34.5MB
class Solution {
    public int countPrimes(int n) {
        if (n <= 2)
  return 0;
 
 // init an array to track prime numbers
 boolean[] composite = new boolean[n];
 
    //We can stop the loop at the square root of 'n'
    //This is because the numbers greater than this square root
    //will only have multiples that are greater than 'n'
 for (int i = 2; i <= Math.sqrt(n - 1); i++) {
        //Check if the current number is a prime
  if (!composite[i]) {
            //Account for all the multiples of this prime
   for (int j = i + i; j < n; j += i)
    composite[j] = true;
  }
 }
 
 int count = 0;
 for (int i = 2; i < n; i++) {
  if (!composite[i])
   count++;
 }
 
 return count;
    }
}

Больше постов ищите здесь.

Удачи и Чао!