线性筛素数

int prime[N], num[N], tot;
void init() {
    for(int i = 2; i < N; i++) {
        if(!num[i]) {
            prime[++tot] = i;
        }
        for(int j = 1, x; j <= tot && (x = i * prime[j]) < N; j++) {
            num[x] = 1;
            if (i % prime[j] == 0) {
                break;
            }
        }
    }
}

大区间素数筛选

例题：洛谷P1835 素数密度

MillerRabin素数测试

inline ll mul(ll x, ll y, ll mod) {
    return (x * y - (ll)((long double)x / mod * y) * mod + mod) % mod;
}
namespace Miller_Rabin {
    ll ksm(ll a, ll b, ll c) {
        ll ans = 1;
        for (ll base = a; b; b >>= 1) {
            if (b & 1) {
                ans = mul(ans, base, c);
                //ans = ans * base % c;
            }
            base = mul(base, base, c);
            //base = base * base % c;
        }
        return ans;
    }
    int mr(ll x, ll b) {
        ll d, p=0;
        d = x - 1;
        while ((d & 1) == 0) {
            d>>=1;
            ++p;
        }
        ll cur = ksm(b, d, x);
        if (cur == 1 || cur == x-1) return true;
        for (int i = 1; i <= p; i++) {
            //cur = cur * cur % x;
            cur = mul(cur, cur, x);
            if (cur == x-1) return 1;
        }
        return 0;
    }
    int isprime(ll x) {
        if (x==46856248255981 || x<2) return false;
        if (x==2 || x==3 || x==7 || x==61 || x==24251) return true;
        return mr(x, 2) && mr(x, 3) && mr(x, 7) && mr(x, 61) && mr(x, 24251);
    }
}
using Miller_Rabin::isprime;

PollardRho找最大素因子

namespace Pollard_Rho {
    ll gcd(ll a, ll b) {
        return b == 0 ? a : gcd(b, a%b);
    }
    ll f(ll x, ll c, ll n) {
        return (mul(x, x, n) + c) % n;
    }
    ll PR(ll x) {
        ll s = 0, t = 0, c = 1ll * rand() % (x - 1) + 1;
        int stp = 0, goal = 1;
        ll val = 1;
        for (goal = 1; ; goal <<= 1, s = t, val = 1) {
            for (stp = 1; stp <= goal; stp++) {
                t = f(t, c, x);
                val = mul(val, abs(t - s), x);
                if (stp % 127 == 0) {
                    ll d = gcd(val, x);
                    if (d > 1) return d;
                }
            }
            ll d = gcd(val, x);
            if(d > 1) return d;
        }
    }
    ll max_factor = 0;
    void fac(ll x) {
        if (x <= max_factor || x < 2) return;
        if (isprime(x)) {
            max_factor = max_factor > x ? max_factor : x;
            return;
        }
        ll p = x;
        while (p >= x) p = PR(x);
        while (x % p == 0) x /= p;
        fac(x); fac(p);
    }
}
using namespace Pollard_Rho;
int main() {
    srand((unsigned)time(NULL));
    scanf("%d", &T);
    while(T--) {
        scanf("%lld", &n);
        if(isprime(n)) {puts("Prime"); continue;}
        max_factor = 0;
        fac(n);
        printf("%lld\n", max_factor);
    }
    return 0;
}

反素数

定义：一个数 x 是反素数，当且仅当所有小于 x 的正整数的因子个数均严格小于 x。

分析：每个反质数，都是由一个比其小的反质数乘以一个质数而来。并且其分解成 p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k} 的形式（p_1,p_2,\cdots ,p_k为2,3,5,\cdots 这些最小的 k 个质数），有 a_1\leq a_2\leq\cdots\leq a_k。

搜索n以内最大的反素数

例题：51nod 1060 最复杂的数

预处理出全部反素数

例题：51nod 1061 最复杂的数V2

求因子个数为n的最小数

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int prime[16] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
int n;
ll ans = 2e18;

void dfs(int dep, ll tmp, ll num, int up, int tar) {
    if (num > tar || dep >= 16) return;
    if (num == tar) {
        ans = min(ans, tmp);
        return;
    }
    for(int i = 1; i <= up; i++) {
        if(tmp / prime[dep] > ans) break;
        dfs(dep+1, tmp *= prime[dep], num * (i+1), i, tar);
    }
}

int main() {
    scanf("%d", &n);
    dfs(0, 1, 1, 64, n);
    printf("%lld\n", ans);
    return 0;
}

约数

设 n=p_1^{k_1}p_2^{k_2}\cdots p_s^{k_s}：

合数分解

long long fac[100][2];
// 首先先要筛一遍sqrt(x)以内的质数！
int getFactors(long long x) {
    int cnt = 0;
    for (int i = 1; prime[i] <= x / prime[i]; i++) {
        if (x % prime[i] == 0) {
            fac[++cnt][0] = prime[i];
            while (x % prime[i] == 0) {
                fac[cnt][1]++;
                x /= prime[i];
            }
        }
    }
    if (x != 1) {
        fac[++cnt][0] = x;
        fac[cnt][1] = 1;
    }
    return cnt;
}

求约数个数

x=\prod_{i=1}^{s}(k_i+1)=(k_1+1)(k_2+1)\cdots (k_s+1)

int Factornum(long long x) {
    int cnt = getFactors(x), ret = 1;
    for (int i = 1; i <= cnt; i++) {
        ret *= (fac[i][1] + 1);
    }
    return ret;
}

求约数和

y=\prod_{i=1}^{s}\frac{1-p_i^{n+1}}{1-p_i}

=(1+p_1+p_1^2+\cdots+p_1^{k_1})(1+p_2+p_2^2+\cdots+p_2^{k_2})\cdots(1+p_s+p_s^2+\cdots+p_s^{k_s})

long long Factorsum(int x) {
    int cnt = getFactors(x);
    long long ret = 1;
    for (int i = 1; i <= cnt; i++) {
        long long a = fac[i][0], b = fac[i][1];
        long long tmp = (ksm(a, b + 1) - 1) / (a - 1);
        ret *= tmp;
    }
    return ret;
}

线性筛约数个数与约数和

int p[N], v[N], tot;
int d[N], num[N];
int g[N], f[N];
// d->约数个数；num->最小质因子出现次数；
// f->约数和；g->连乘项中属于最小质因子的幂次和
void init() {
    d[1] = g[1] = f[1] = 1;
    for (int i = 2; i < N; i++) {
        if (!v[i]) {
            v[i] = 1; p[++tot] = i;
            d[i] = 2; num[i] = 1;
            g[i] = i + 1; f[i] = i + 1;
        }
        for (int j = 1, x; j <= tot && (x = i * p[j]) < N; j++) {
            v[x = 1;
            if (i % p[j] == 0) {
                num[x] = num[i] + 1;
                d[x] = d[i] / num[x] * (num[x] + 1);
                g[x] = g[i] * p[j] + 1;
                f[x] = f[i] / g[i] * g[x];
                break;
            }
            else
            {
                num[x] = 1;
                d[x] = d[i] * 2;
                f[x] = f[i] * f[p[j]];
                g[x] = 1 + p[j];
            }
        }
    }
}