首页 > 代码库 > 算法题解之math类题

算法题解之math类题

2024-08-20 15:12:10   213人阅读

Count Primes

质数计数

思路1：暴力法。其中判断每一个数n是不是质数需要验证是否任何小于n的数都不能整除n，这一步是O（n）。因此整体复杂度是O(n^2)。

思路2：思路1的优化版。如果一个数n不是质数，则n = p * q。令 p <= q，则可以推出 p * p <= n，即 p <= √n。因此思路一中只需要判断是否任何小于等于√n都不能整除n。整体时间复杂度变为O(n^1.5)。

技术分享 
 1 public int countPrimes(int n) {
 2    int count = 0;
 3    for (int i = 1; i < n; i++) {
 4       if (isPrime(i)) count++;
 5    }
 6    return count;
 7 }
 8 
 9 private boolean isPrime(int num) {
10    if (num <= 1) return false;
11    // Loop‘s ending condition is i * i <= num instead of i <= sqrt(num)
12    // to avoid repeatedly calling an expensive function sqrt().
13    for (int i = 2; i * i <= num; i++) {
14       if (num % i == 0) return false;
15    }
16    return true;
17 }
View Code

思路3：埃拉托色尼筛选法：对于当前数i（i要从2开始），把它的倍数2i，3i，4i......都标记为不是质数，然后 i 的下一个没有被标记过的数一定是质数。

优化：（1）如果一个数已经被标记为不是质数了，直接跳过，因为它的倍数之前一定已经标记过了；（2）对于数i，不用从2i开始标记，直接从i * i开始标记（之前的也一定被标记过）。

算法空间复杂度为O(n)，时间复杂度为O(n log log n)。（证明见wiki）

技术分享 
 1 public class Solution {
 2     public int countPrimes(int n) {
 3         boolean[] notPrime = new boolean[n];
 4         int count = 0;
 5         for (int i = 2; i < n; i++) {
 6             if (notPrime[i] == false) {
 7                 count++;
 8                 for (long j = i; i * j < n; j++) {
 9                     notPrime[(int)(i * j)] = true;
10                 }
11             }
12         }
13         
14         return count;
15     }
16 }
View Code

 

算法题解之math类题


联系
我们