蒟蒻君的数学学习之路2——质数相关算法

⭐前言

质数,是数学里很重要的东东。若

p

p

p为质数,

p

p

p

>

1

>1

>1的整数且

p

p

p有且仅有

1

1

1

p

p

p两个因数。
今天,蒟蒻君将和大家一起学习质数相关算法(难度递增qwq)。


在这里插入图片描述

⭐一、质数判定

?

1.1

1.1

1.1 试除法

?思路

最常用的算法。

  1. 假设

    n

    n

    n不是质数,则必有

    a

    ,

    b

    a,b

    a,b使得

    n

    =

    a

    ×

    b

    n = a times b

    n=a×b

  2. a

    <

    b

    a < b

    a<b, 则

    a

    n

    a le sqrt n

    an

  3. 枚举

    a

    =

    1

    n

    a = 1 - sqrt n

    a=1n

    ,若所有

    a

    a

    a均不被

    n

    n

    n整除,则

    n

    n

    n为质数,否则为合数。

  4. 注意特判

    0

    0

    0

    1

    1

    1

时间复杂度

O

(

n

)

O(sqrt n)

O(n

)
空间复杂度

O

(

1

)

O(1)

O(1)

?代码
inline bool isprime(int n) {
	if (n < 2) {
		return false;
	}
	for (int i = 2; i * i <= n; ++i) {
		if (n % i == 0) {
			return false;
		}
	}
	return true;
}

?

1.2

1.2

1.2 卡常写法

?思路

在法一的基础上可以进行以下优化:

n

n

n为质数,则

n

m

o

d

  

2

0

n mod 2 neq 0

nmod2=0

n

m

o

d

  

3

0

n mod 3 neq 0

nmod3=0,则

n

m

o

d

  

6

=

1

/

5

n mod 6 = 1/5

nmod6=1/5。跳过

2

4

2 - 4

24,时间复杂度可提高到之前的

1

3

frac{1}{3}

31
注意特判

n

=

2

/

3

/

5

/

7

/

11

n=2/3/5/7/11

n=2/3/5/7/11还有

n

=

2

/

3

/

5

k

(

k

N

)

n=2/3/5k(kin N)

n=2/3/5k(kN)

时间复杂度

O

(

n

)

O(sqrt n)

O(n

),只是常数有些变化;
空间复杂度

O

(

1

)

O(1)

O(1)

?代码
inline bool isprime(int n) {
	if (n < 2) {
		return false;
	}
	if (n == 2 || n == 3 || n == 5 || n == 7 || n == 11) {
		return true;
	}
	if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0) {
		return false;
	}
	for (int i = 1; i <= n / 6 + 1; ++i) {	// 枚举n = 6 * i +/- 1 
		if (i * 6 >= sqrt(n) + 5) {
			break;
		}
		if ((n % (i * 6 + 1) == 0) || (n % (i * 6 + 5) == 0)) {
			return false;
		}
	}
	return true;
}

如果让你从

1

100

1 - 100

1100这些数里筛出质数,那你还会一个一个数地试除吗 (当然你没有背过)
质数筛法适用于先预处理,然后多次查询的条件下。
下面我们来学习质数的两种筛法叭~
注意,质数筛法标程以洛谷P3383【模板】线性筛素数为例。

?

1.3

1.3

1.3 埃氏筛法

?思路

相信大家也都对这种方法不陌生。
比如我们要判断

1

100

1 - 100

1100中选出所有质数,那么我们可以这样做:

  1. 先将

    1

    100

    1 - 100

    1100写在纸上。

  2. 我们在

    2

    2

    2上画一个小圈圈,然后叉掉所有

    2

    2

    2的倍数;

  3. 再在

    3

    3

    3上画一个小圈圈,删掉所有

    3

    3

    3的倍数;

  4. 现在你发现

    4

    4

    4已经被删掉了,那么就可以在

    5

    5

    5上画一个圈圈,然后删掉所有

    5

    5

    5的倍数。

  5. 以此类推,直到

    1

    100

    1 - 100

    1100中所有数都被划掉或圈起为止,质数为所有被圈出来的数。

接下来我们来分析一下ta的时间复杂度。
因为所有数要么都被删除或圈出一次,则时间复杂度为

O

(

n

)

O(n)

O(n)
nonono
仔细思考可知,有些数会被删除多次,如

6

6

6

2

2

2

3

3

3删除,则:

T

(

n

)

=

O

(

p

n

n

p

)

=

O

(

p

n

1

p

)

=

O

(

n

l

o

g

l

o

g

n

)

T(n)=O(displaystyle sum_{p le n} frac{n}{p})=O(displaystyle sum_{p le n} frac{1}{p})=O(nloglogn)

T(n)=O(pnpn)=O(pnp1)=O(nloglogn)
时间复杂度

O

(

n

l

o

g

l

o

g

n

)

O(nloglogn)

O(nloglogn)
空间复杂度

O

(

n

)

O(n)

O(n)

?代码

注意:此方法时间复杂度较高,需使用scanf/printf/ios :: sync_with_stdio(0)方可AC。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e8 + 5;
bool vis[N];
int p[N], cnt;
void init(int n) {
	vis[1] = true;
	for (int i = 2; i <= n; ++i) {
		if (vis[i]) {
			continue;
		}
		p[++cnt] = i;
		for (long long j = 1ll * i * i; j <= n; j += i) {
			vis[j] = true;
		}
	}
}
int main() {
	int n, q;
	scanf("%d %d", &n, &q);
	init(n);
	while (q--) {
		int k;
		scanf("%d", &k);
		printf("%dn", p[k]);
	}
	return 0;
} 

?

1.4

1.4

1.4 欧拉筛法

?思路

相当于是埃氏筛法的优化版。
分析可知,

n

=

p

1

a

1

×

p

2

a

2

×

p

3

a

3

×

.

.

.

×

p

m

a

m

n = p1^{a1} times p2^{a2} times p3^{a3} times ... times pm^{am}

n=p1a1×p2a2×p3a3×...×pmam只会被

p

1

a

1

1

×

p

2

a

2

×

p

3

a

3

×

.

.

.

×

p

m

a

m

p1^{a1-1} times p2^{a2} times p3^{a3} times ... times pm^{am}

p1a11×p2a2×p3a3×...×pmam划掉,不用考虑别的了。
时间复杂度

O

(

n

)

O(n)

O(n)
空间复杂度

O

(

n

)

O(n)

O(n)

?代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e8 + 5, M = 1e6 + 5;
bool P[N];
int n, q;
vector<int> p;
void init() {
	memset(P, true, sizeof P);
	P[1] = false;
	p.push_back(0); 
	for (int i = 2; i <= n; ++i) {
		if (P[i]) {
            p.push_back(i);
        }
		for (int j = 1; j <= p.size() && i * p[j] <= n; ++j) {
			P[i * p[j]] = false;
			if (i % p[j] == 0) {
				break;
            }
		}
	}
}
int main() {
    cin >> n >> q;
    init();
    while (q--) {
        int k;
        cin >> k;
        cout << p[k] << 'n';
    }
	return 0;
}

?

1.5

1.5

1.5 Miller-Rabin测试

?思路

巧妙但会出现失误的方法(但非常好用),适用于大数判断。
用到了一点后面的费马小定理。

  1. 算出整数

    m

    m

    m使得

    n

    =

    2

    k

    ×

    m

    +

    1

    n = 2^{k} times m+1

    n=2k×m+1,随机

    1

    a

    <

    n

    1 le a < n

    1a<n

  2. 对于

    i

    <

    r

    (

    i

    N

    )

    i < r(i in N)

    i<r(iN),若

    a

    2

    i

    m

    m

    o

    d

      

    n

    =

    n

    1

    a^{2^{i}*m} mod n=n-1

    a2immodn=n1

    a

    m

    m

    o

    d

      

    n

    =

    1

    a^m mod n=1

    ammodn=1,则

    n

    n

    n通过

    a

    a

    a的测试;

  3. 选择多个

    a

    a

    a,若全部通过则认为

    n

    n

    n为质数。通过

    t

    t

    t次测试,

    n

    n

    n为合数的概率为

    1

    4

    t

    frac{1}{4^{t}}

    4t1

  4. 虽然还是有一定概率判断失误的,但这惊人的时间复杂度确实令人羡慕。如果你每次都用前7个素数测试,所有不超过341550071728320的数都不会判断失误。

注意:这里没有考虑直接乘会超出范围的情况(考虑的话加一点模拟就可以了)。
时间复杂度

O

(

l

o

g

n

2

)

O(logn^2)

O(logn2)
空间复杂度

O

(

1

)

O(1)

O(1)

?代码
int qpow(int x, int y, int p) {
	int res = 1;
	while (y) {
		if (y & 1) {
			(res *= x) %= p;
		}
		(x *= x) %= p;
		y >>= 1;
	}
	return res;
}
inline bool isprime(int n) {
	if (n <= 2) {
		return n == 2;
	}
	for (int i = 0; i < 10; ++i) {
		int a = rand() % (n - 2) + 2;	// 最小为2 
		if (qpow(a, n, n) != a) {
			return false;
		}
	}
	return true;
}

在这里插入图片描述

⭐二、相关定理

?

2.1

2.1

2.1 威尔逊定理

?结论

{

p

,

(

p

1

)

!

1

(

m

o

d

p

)

(

p

1

)

!

1

(

m

o

d

p

)

,

p

begin{cases} 若p为质数,(p-1)!equiv -1pmod{p}\ 若(p-1)!equiv -1pmod{p}, p为质数 end{cases}

{p,(p1)!1(modp)(p1)!1(modp),p

?证明

[

2

,

p

2

]

[2,p-2]

[2,p2]必被

p

1

2

frac{p-1}{2}

2p1对逆元覆盖。

1

1

1的逆元为

1

1

1,故此定理成立。

?

2.2

2.2

2.2 欧拉定理

?结论

欧拉函数:

φ

(

n

)

φ(n)

φ(n)表示满足

1

m

n

,

m

N

1 le m le n,m in N

1mn,mN

g

c

d

(

n

,

m

)

=

1

gcd(n,m)=1

gcd(n,m)=1

m

m

m的个数。
欧拉定理:

a

,

m

N

a,m in N

a,mN

g

c

d

(

a

,

m

)

=

1

gcd(a,m)=1

gcd(a,m)=1,则

a

φ

(

m

)

1

(

m

o

d

m

)

a^{φ(m)}equiv1pmod{m}

aφ(m)1(modm)

?证明

{

b

φ

(

m

)

}

left { b_{φ(m)} right }

{bφ(m)}

1

m

1 to m

1m中于

m

m

m互质的数的集合。
我们发现

b

b

b数组中所有数

m

o

d

  

m

mod m

modm余数各不相同,且余数都与

m

m

m互质。
仔细观察后发现,

a

×

b

1

,

a

×

b

2

,

a

×

b

3

,

.

.

.

a

×

b

φ

(

m

)

{a times b_1,a times b_2,a times b_3,...a times b_{φ(m)}}

a×b1,a×b2,a×b3,...a×bφ(m)也符合以上两个条件。
综合以上结论,

g

c

d

(

a

,

m

)

=

1

,

g

c

d

(

b

i

,

m

)

=

1

g

c

d

(

a

×

b

i

,

m

)

=

1

because gcd(a,m)=1,gcd(b_i,m)=1 therefore gcd(a times b_i,m) = 1

gcd(a,m)=1,gcd(bi,m)=1gcd(a×bi,m)=1

a

×

b

1

φ

(

m

)

m

o

d

  

n

because a times b_{1 to φ(m)} mod n

a×b1φ(m)modn的结果是

φ

(

m

)

φ(m)

φ(m)个不同且与

m

m

m互质的数、

therefore

这些数就是

b

b

b了(真香)。

a

×

b

1

×

a

×

b

2

×

a

×

b

3

×

.

.

.

×

a

×

b

φ

(

m

)

b

1

×

b

2

×

b

3

×

.

.

.

×

b

φ

(

m

)

(

m

o

d

m

)

therefore a times b_1 times a times b_2 times a times b_3 times ... times a times b_{φ(m)} equiv b_1 times b_2 times b_3 times ... times b_{φ(m)} pmod{m}

a×b1×a×b2×a×b3×...×a×bφ(m)b1×b2×b3×...×bφ(m)(modm)

a

φ

(

m

)

1

(

m

o

d

m

)

a^{φ(m)}equiv1pmod{m}

aφ(m)1(modm)

?

2.3

2.3

2.3 费马小定理

?结论

若有

p

p

p为质数,

a

N

a in N

aN使得

g

c

d

(

a

,

p

)

=

1

gcd(a,p)=1

gcd(a,p)=1,则

a

p

1

1

(

m

o

d

p

)

a^{p-1}equiv 1pmod{p}

ap11(modp)

?证明

看完了刚才的欧拉定理,费马小定理的证明应该很简单了叭~

p

because p

p为质数

φ

(

p

)

=

p

1

thereforeφ(p)=p-1

φ(p)=p1,然后代入即可证明。
其实,费马小定理就是欧拉定理的一个特例。
在这里插入图片描述

⭐三、分解质因数

?

3.1

3.1

3.1 试除法

?思路

遍历

i

=

2

n

i = 2 - sqrt n

i=2n

,若

i

i

i是质数且

i

i

i

n

n

n的因数,则让

n

n

n不断除以

i

i

i,不能整除为止,使用常规算法判断质数(筛不筛复杂度都一样qwq)。
时间复杂度:

O

(

n

)

O(n)

O(n)
空间复杂度:

O

(

1

)

O(1)

O(1)

?代码
#include <bits/stdc++.h>
using namespace std;
inline bool isprime(int n) {
	if (n < 2) {
		return false;
	}
	for (int i = 2; i * i <= n; ++i) {
		if (n % i == 0) {
			return false;
		}
	}
	return true;
}
int main() {
	int n;
	cin >> n;
	for (int i = 1; i * i <= n; ++i) {
		if (n % i == 0 && isprime(i)) {
			while (n % i == 0) {
				cout << i << ' ';
				n /= i;
			}
		}
	}
	if (isprime(n)) {
		cout << n << 'n';
	}
	return 0;
} 

?

3.2

3.2

3.2 Pollard Rho算法

?思路

适用于大数分解。
我们每次寻找

n

n

n的任意一个因数

m

m

m,然后递归分解

m

m

m

n

m

frac{n}{m}

mn
最大的问题就是,如何找到一个因数?当然不是去试除,而是有点随机的试验。
我们随机取出一个数

x

x

x,然后构造

y

y

y,使得

m

(

x

y

)

,

n

(

x

y

)

m mid (x-y),n nmid (x-y)

m(xy),n(xy)

m

=

g

c

d

(

x

y

,

n

)

m=gcd(x-y,n)

m=gcd(xy,n)。若结果为

1

1

1的话我们就要继续不断调整

y

y

y,否则就成功找到了一个因数。
对于调整

y

y

y,一般策略为

y

=

y

2

+

t

y=y^2+t

y=y2+t(t自定)。
直到

x

=

y

x=y

x=y,需要重新选取

x

x

x
时间复杂度:

O

(

n

1

4

)

O(n^{frac{1}{4}})

O(n41)
空间复杂度:

O

(

n

)

O(n)

O(n)

?代码
#include <bits/stdc++.h>
using namespace std;
int x[1 << 7];
queue<int> q;
int qpow(int x, int y, int p) {
	int res = 1;
    while (y) {
        if (y & 1) {
            (res *= x) %= p;
        }
        (x *= x) %= p;
        y >>= 1;
    }
	return res;
}
bool isprime(int n) {
    if (n <= 2) {
        return n == 2;
    }
    int t = n - 1, sum = 0;
    int times = 20;
    while (!(t & 1)) {
        ++sum;
        t >>= 1;
    }
    while (times--) {
        int a = rand() % (n - 2) + 2;
        x[0] = qpow(a, t, n);
        for (int i = 1; i <= sum; ++i) {
            x[i] = x[i - 1] * x[i - 1] % n;
            if (x[i] == 1 && x[i - 1] != 1 && x[i - 1] != n - 1) {
                return false;
            }
        }
        if (x[sum] != 1) {
        	return false;
		}
    }
	return true;	
}
int Pollard_Rho(int n, int t) {
    int x = rand() % (n - 1) + 1, y = x;
    int i = 1, j = 2;
	while (true) {
        ++i;
        x = (x * x % n + t) % n;
		int m = __gcd((y - x + n) % n, n);
		if (m != 1 && m != n) {
            return m;
        }
		if (x == y) {
            return n;
        }
		if (i == j) {
			y = x;
			j <<= 1;
		}	
	}
}
void calc(int n, int t) {
	if (n == 1)	{
        return ;
    }
	if (isprime(n)) {
		q.push(n);
		return ;
	}
	int m = n, k = t;
	while (m >= n) {
		m = Pollard_Rho(m, t--);
	}
	calc(m, k);
	calc(n / m, k);
}
int main() {
	int n;
    cin >> n;
	calc(n, 110);
	while (q.size()) {
		cout << q.front() << ' ';
		q.pop();
	}
	return 0;
}

在这里插入图片描述

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>