Вопрос. Подсчитайте количество простых чисел, меньших неотрицательного числа, 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; } }
Больше постов ищите здесь.
Удачи и Чао!