质数判定O(sqrt(n))

  • 试除法判断质数，从2到sqrt(n)，是否可以整除，如果可以整除，则不是质数

    1. bool is_prime(int n)
    2. {
    3.   if (n < 2) {
    4.       return false;
    5.   }
    6.   // 约数是成对出现的，由于效率问题，我们希望只枚举最小的约数
    7.   // 假设比较小的约数为i, 则比较大的约数为n / i
    8.   // 由于i <= (n / i)，则i <= sqrt(n)
    9.   for (int i = 2; i <= n / i; i ++) {
    10.       if (n % i == 0) {
    11.           return false;
    12.       }
    13.   }
    14.   return true;
    15. }

    质因子分解O(sqrt(n))

  • 试除法对整数进行质因子分解

  • 由于每个数只可能有一个大于sqrt(n)的质因子，因此可以单独处理
  • 先找到小于sqrt(n)的质因子和个数，最后如果n > 1，则还有一个质因子
    1. void divide(int n)
    2. {
    3.   // 对于每个数，只可能有一个大于sqrt(n)的质因子
    4.   for (int i = 2; i <= n / i; i ++) {
    5.       int cnt = 0;
    6.       while(n % i == 0) {
    7.           cnt ++;
    8.           n /= i;
    9.       }
    10.       if (cnt > 0) {
    11.           cout << i << " " << cnt << endl;
    12.       }
    13.   }
    14.   if (n > 1) {
    15.       cout << n << " " << 1 << endl;
    16.   }
    17. }

    筛质数

    朴素筛法O(nlogn)

    ```cpp

    define N 1000010

    int primes[N], cnt; bool st[N];

int get_prime(int n) { for (int i = 2; i <= n; i ++) { // 如果该数之前没有被筛过，则是质数 if (!st[i]) { primes[cnt ++] = i; } // 利用当前数删除对应的倍数 for (int j = 2; j <= n / i; j ++) { st[j * i] = true; } } return cnt; }

  1. <a name="6sHzU"></a>
  2. #### 埃式筛法O(n log logn)
  3. ```cpp
  4. #define N 1000010
  5. int primes[N], cnt;
  6. bool st[N];
  8. int get_prime(int n)
  9. {
  10.     for (int i = 2; i <= n; i ++) {
  11.         // 如果该数之前被筛过了，跳过
  12.         if (st[i]) {
  13.             continue;
  14.         }
  15.         primes[cnt ++] = i;
  16.         // 利用当前质数删除对应的倍数
  17.         for (int j = 2; j <= n / i; j ++) {
  18.             st[j * i] = true;
  19.         }
  20.     }
  21.     return cnt;
  22. }

线性筛法O(n)

#define N 1000010
int primes[N], cnt;
bool st[N];

int get_prime(int n)
{
    for (int i = 2; i <= n; i ++) {
        // 筛出新的质数
        if (!st[i]) {
            primes[cnt ++] = i;
        }
        // 通过最小质因子标记所有primes[j] * i
        for (int j = 0; primes[j] <= n / i; j ++) {
            st[primes[j] * i] = true;
            // 如果条件成立，primes[j]是i的最小质因子
            // primes[j]也一定是primes[j] * i的最小质因子
            if (i % primes[j] == 0) {
                break;
            }
            // 如果条件不成立，i不能整除primes[j]，primes[j]小于i的所有质因子
            // 那么primes[j]是primes[j] * i的最小质因子
        }
    }
    return cnt;
}