跳转至

Prime

判断一个整数N是否是质数

从2开始到\sqrt{N}的所有质数是否可以整除N

先算出N的平方根，然后扫描判断一遍，这里其实不用筛质数，因为筛质数已经略大于线性时间，不如全部扫描

筛[2, N)的质数表

埃拉托色尼筛法(the Sieve of Eratosthenes)

开一个长为N的数组，标记每个数是不是质数

之后从2开始直到\sqrt{N}来筛质数，遇到质数i后从i*i开始将所有i的倍数置为合数

这里从i*i开始因为小于这个的倍数肯定在之前已经被置为合数

复杂度是O(NlglgN)，证明

int countPrimes(int n) {
    vector<int> nums(n, 1);
    for (int i = 2; i * i < n; i ++) {
        if (nums[i])
            for (int j = i * i; j < n; j += i) nums[j] = 0;
    }
    int result = 0;
    for (int i = 2; i < n; i ++) result += nums[i];        
    return result;
}

线性筛法

同时开一个数组来存储之前出现的所有质数，内部for循环其实是将小于i的最小质因子的所有质数和i的乘积置为合数

这样一个数k被置为合数当且仅当i*q=k，这里q是最小质因子，因此只会被置1次

但实际运行中，因为vector的插入也花费时间，因此并不会显著优于上一种解法

int countPrimes(int n) {
    vector<int> A(n, 1), B;
    for (int i = 2; i * 2 < n; i++) {
        if (A[i] == 1) B.push_back(i);
        for (int prime : B) {
            if (prime * i < n) A[prime * i] = 0;
            else break;
            if (i % prime == 0) break;
        }
    }
    int result = B.size();
    for (int i = B.empty() ? 2 : B.back() + 1; i < n; i++) result += A[i];
    return result;
}

因数个数

Euler Project 179

对N的所有因数，遍历一遍，用较小的因子来计算，每次因数个数加2即可

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> factors(N + 1, 0);
    for (int i = 1; i * i <= N; i++) {
        factors[i * i]++;
        for (int j = i * i + i; j <= N; j += i) factors[j] += 2;
    }
    int res = 0;
    for (int i = 2; i < N; i++)
        if (factors[i] == factors[i + 1]) res++;
    cout << res << '\n';
}

欧拉函数

定义: 对正整数n，欧拉函数\phi(n)是小于或等于n的正整数中与n互质的数的数目，如果n是质数，那么\phi(n)=n-1，如果n有m个质因子，那么

\phi(n)=(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_m})

求\phi(n)

求出所有质因子即可，方法类似于筛法求质数，不过不用维持质数表，而是从2开始依次扫描。在遇到第一个可以被n整除的数时，这个数一定是n最小的质因子，在更新欧拉函数的值后，用n反复除以这个因子直到不包含为止，然后继续扫描，那么下一个遇到的可以被n整除的数也是质因子

int getPhi(int n) {
    int ans = n;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            ans -= ans / i;
            while (n % i == 0) n /= i;
        }
    }
    if (n != 1) ans -= ans / n;
    return ans;
}

筛法求欧拉函数

同时求解1到n的欧拉函数，也可以利用类似质数筛法的方法，一开始所有值都置为1，这里\phi(1)的值可以单独设置，可以为1也可以为0，根据题目调整。然后从2开始，在发现\phi(i)的值是0时，说明i是质数，那么将之后所有i的倍数的欧拉函数的值都进行更新即可

void eular(vector<int>& eu) {
    for (int i = 2; i < eu.size(); i++) {
        if (eu[i] == 0) {
            for (int j = i; j < eu.size(); j++) {
                if (eu[j] == 0) eu[j] = j;
                eu[j] -= eu[j] / i;
            }
        }
    }
}