[LeetCode]--204. Count Primes

xiaoxiao2026-05-27 10

Description:

Count the number of prime numbers less than a non-negative number, n.

Credits: Special thanks to @mithmatt for adding this problem and creating all test cases.

public int countPrimes(int n) { int count = 0; for (int i = 2; i < n; i++) if (isPrime(i)) count++; return count; } public boolean isPrime(int n) { if (n <= 1) return false; for (int i = 2; i * i <= n; i++) if (n % i == 0) return false; return true; }

基本复杂度都是由isPrime()这个弄出来，这个算法是正确的，但是不能Accept。超时了，那么就想着把isPrime()提高效率，对算法进行改进，将判断能否被小于sqrt（n）的数整除，改为能否被小于sqrt(n)的素数整除，可以节省很多计算量，大大减少计算的次数。这样就需要将以前计算的素数都记下来，所以使用一个全局的List来记录计算过的素数。

public class _204CountPrimes { public List<Integer> list = new ArrayList<Integer>(); public int countPrimes(int n) { int count = 0; for (int i = 2; i < n; i++) if (isPrime1(i)) { list.add(i); count++; } return count; } public boolean isPrime1(int n) { if (n < 2) return false; if (n == 2) return true; int sqetN = (int) Math.sqrt(n); int temp = 0; for (int i = 0; i < list.size(); i++) { temp = list.get(i); if (temp > sqetN) break; if (n % temp == 0) return false; } return true; } }

这个就可以Accept。