数论(一)

一.质数判断

质数(素数)的定义:一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数

1.朴素法判断质数

bool isPrime(int n){
    if(n < 2) return false;
    for(int i = 2; i < n; i ++)
    {
        if(n % i == 0) return false;
    }
    return true;
}

复制

2.优化版判断素数法

注意:约数是成对出现的,i和n/i,只需要枚举到较小的那个,此处也可以用sqrt()这个库函数,由于反复调用会使得运行效率偏低;

bool isPrime(int n){
    if(n < 2) return false;
    for(int i = 2; i <= n/i; i ++)
    {
        if(n % i == 0) return false;
    }
    return true;
}

复制

二.筛质数

1.朴素法筛质数

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

void getPrimes(int n){
    for(int i = 2; i <= n; i ++){
        if(!st[i]) primes[cnt ++] = i;
        //依次删掉每个i的倍数
        for(int j = i + i; j <= n; j += i)
        {    
            st[j] = true;
        }
    }
}

复制

2.优化版筛质数法(埃氏筛法)

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

void getPrimes(int n){
    for(int i = 2; i <= n; i ++){
        if(!st[i])
        {
            primes[cnt ++] = i;
            //只删掉质数i的倍数
            for(int j = i + i; j <= n; j += i){
                st[j] = true;
            }
        }
    }
}

复制

3.线性筛质数

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

void getPrimes(int n){
    for(int i = 2; i <= n; i ++){
        if(!st[i]) primes[cnt ++] = i;
        for(int j = 0; primes[j] <= n / i; j ++){
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
            //primes[j]一定是i的最小质因子
        }
    }
}

复制

三.求约数

1.试除法求约数

vector<int> get_divisors(int n){
    vector<int> res;
    for(int i = 1; i <= n / i; i ++){
        if(n % i == 0){
            res.push_back(i);
            if(i != n / i) res.push_back(n / i);
        }
    }
    sort(res.begin(), res.end());
    return res;
}

复制

2.约数个数

约数个数：任何一个数 n ，一定能够表示成 n = a0^p0 * a1^p1 * a2^p2 … ak^pk, 其中 a0,a1,a2…ak都是质数，那么数 n的所有约数个数 T = (1+p0)(1+p1)(1+p2)…(1+pk)

#define long long  LL;
LL ans = 1;
unordered_map<int,int> hash;
cin >> x;
for(int i = 2;i <= x/i; ++i){
    while(x % i == 0){
        x /= i;
        hash[i] ++;
    }
}
if(x > 1) hash[x] ++;

for(auto i : hash) ans = ans*(i.second + 1) % mod;
cout << ans;

复制

3.约数之和

unordered_map<int,int> q;
cin >> x;
for(int i = 2 ; i <= x / i ; i++)
{
    while(x % i == 0)
    {
        x /= i;
        q[i]++;
    }
}
if(x > 1)
{
    q[x]++;
}

long long mul = 1;
for(auto t : q)
{
    int p = t.first; //底数
    int j = t.second; //指数
    long long res = 1;
    while(j--)
    {
        res = (res * p + 1) % mod;
    }
    mul = mul * res % mod;
}
printf("%lld\n",mul);

复制