数学：数论问题

Posted on Edited on

Preface

Content

Problem

判断一个数是否是质数；

给大树作质因数分解；

Solution

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void divide(int n) {
    for (int i = 2; i <= n / i; ++i) {
        if (n % i == 0) {
            int s = 0;
            while (n % i == 0) {
                s ++;
                n /= i;
            }
            cout << i << ' ' << s << endl;
        }
    }
    if (n > 1) cout << n << ' ' << 1 << endl;
    cout << endl;
}

Miller_Rabin算法

U82118 【模板】Miller Rabin算法

Pollard rho 算法

P4718 【模板】Pollard rho 算法

Remark