prime

发表于

质数

什么是质数？

一个正整数无法被除了1和自己之外的任何自然数整除

特殊情况 1既不是质数也不是合数

质数的数量 不超过N的质数大约有N/lnN个

质数的判定

一般使用试除法判断质数

若一个正整数N为合数，则存在一个能整除N的数 T 且T∈[2,√N]

证明方法：反证法

1
2
3
4
5
bool isprime(int n){
    for(int i=2;i*i<=n;++i)
    if(n%i==0)return false;
    return true;
}

质数的筛选

Eratosthenes

任意的整数N的倍数2N,3N……必定为合数

复杂度O(N log log N)趋于线性，比较常用

1
2
3
4
5
6
7
8
void prime(int n){
    memset(v,0,sizeof(v));
    for(int i=2;i<=n;++i){
        if(v[i])continue;
        printf("%d",i);//i是质数
        for(int j=i;j<=n/i;++j)v[i*j]=1;
    }
}

线性筛

在生成一个合数时，每次只向现有的数乘上一个质因子，并且让它是这个合数的最小质因子，这样可以避免重复标记合数

复杂度O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int v[MAX_N],prime[MAX_N];
void primes(int n){
    memset(v,0,sizeof(v));
    int m=0;
    for(int i=2;i<=n;++i){
        if(!v[i]){
            v[i]=i;
            prime[++m]=i;
        }
        for(int j=1;j<=m;++j){
            if(prime[j]>v[i]||prime[j]>n/i)break;
            v[i*prime[j]]=prime[j];
        }
    }
}

算术基本定理

任何一个大于 1 的正整数都能有限分解为有限个质数的乘积

N=p1^c1*p2^c2*...*pn^cn其中ci都是正整数 pi都是质数 且满足p1<p2<p3<…<pn

质因数分解

根据算术基本定理，我们可以分解正整数N

试除法

扫描2-√N的每个数d,若d能整除N，则从N中除掉所有的d,同时累积除去d的个数

1
2
3
4
5
6
7
8
9
void divide(int n){
    int m=0;
    for(int i=2;i*i<=n;++i){
        if(n%i==0){
            p[++m]=i;c[m]=0;
            while(n%i==0)n/=i,c[m]++;
        }
    }
}

pollard‘s Rho

对于一个大整数n，我们取任意一个数xx使得xx是nn的质因数的几率很小，但如果取两个数x1x1以及x2x2使得它们的差是n的因数的几率就提高了，如果取x1x1以及x2x2使得gcd(abs(x1−x2),n)>1gcd(abs(x1−x2),n)>1的概率就更高了。

其实，这是生日悖论

生日问题是指，如果一个房间里有23个或23个以上的人，那么至少有两个人的生日相同的概率要大于50%。这就意味着在一个典型的标准小学班级（30人）中，存在两人生日相同的可能性更高。对于60或者更多的人，这种概率要大于99%。从引起逻辑矛盾的角度来说生日悖论并不是一种悖论，从这个数学事实与一般直觉相抵触的意义上，它才称得上是一个悖论。大多数人会认为，23人中有2人生日相同的概率应该远远小于50%。

对于满足gcd(abs(x1−x2),n)>1gcd(abs(x1−x2),n)>1的x1x1和x2x2，gcd(abs(x1−x2),n)gcd(abs(x1−x2),n)就是n的一个因数，只需要判断它是否为素数，若为素数，则是n的质因数，否则递归此过程。

那么我们怎样不断取得x1x1和x2x2呢？ x1x1在区间[1,n][1,n]中随机出来，而x2x2则由x[i]=(x[i-1]*x[i-1]%n+c)%n推算出来，其中cc为任意给定值，事实证明，这样就是比较优的。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;

const int MAXN = 65;
long long x[MAXN];
vector<long long> f;

long long multi(long long a, long long b, long long p) {
    long long ans = 0;
    while(b) {
        if(b&1LL) ans = (ans+a)%p;
        a = (a+a)%p;
        b >>= 1;
    }
    return ans;
}

long long qpow(long long a, long long b, long long p) {
    long long ans = 1;
    while(b) {
        if(b&1LL) ans = multi(ans, a, p);
        a = multi(a, a, p);
        b >>= 1;
    }
    return ans;
}

bool Miller_Rabin(long long n) {
    if(n == 2) return true;
    int s = 20, i, t = 0;
    long long u = n-1;
    while(!(u & 1)) {
        t++;
        u >>= 1;
    }
    while(s--) {
        long long a = rand()%(n-2)+2;
        x[0] = qpow(a, u, n);
        for(i = 1; i <= t; i++) {
            x[i] = multi(x[i-1], x[i-1], n);
            if(x[i] == 1 && x[i-1] != 1 && x[i-1] != n-1) return false;
        }
        if(x[t] != 1) return false;
    }
    return true;
}

long long gcd(long long a, long long b) {
    return b ? gcd(b, a%b) : a;
}

long long Pollard_Rho(long long n, int c) {
    long long i = 1, k = 2, x = rand()%(n-1)+1, y = x;
    while(true) {
        i++;
        x = (multi(x, x, n) + c)%n;
        long long p = gcd((y-x+n)%n, n);
        if(p != 1 && p != n) return p;
        if(y == x) return n;
        if(i == k) {
            y = x;
            k <<= 1;
        }
    }
}

void find(long long n, int c) {
    if(n == 1) return;
    if(Miller_Rabin(n)) {
        f.push_back(n);
        return;
    }
    long long p = n, k = c;
    while(p >= n) p = Pollard_Rho(p, c--);
    find(p, k);
    find(n/p, k);
}