跳到主要内容

素数

概述

素性测试给出三种方法。试除法枚举 2 到根号 n 试除，存在因子即为合数，时间复杂度为 O(根号 n)。Fermat 测试基于费马小定理，随机取若干底数检验，卡迈克尔数会被误判。Miller–Rabin 在其上增加二次探测，把 n−1 写成 u 乘 2 的 t 次方，检验反复平方中是否出现非平凡的 1 的平方根，可滤掉卡迈克尔数、误判概率极低。另附常见素数表：100 以内素数、常用模数、梅森素数、日期素数与若干有特殊含义的数。

参考资料​

素性测试​

试除法​

枚举 22 到 n\sqrt n 的整数试除，存在因子则为合数。时间复杂度为 O(n)O(\sqrt{n})。

103 Bcpp
bool prime(int n)
{
	if(n<2)return 0;
	for(int i=2;i*i<=n;i++)
	{
		if(n%i==0)return 0;
	}
	return 1;
}

Fermat 素性测试​

基于费马小定理：若 nn 为素数，则对任意 aa 有 an−1≡1(modn)a^{n-1}\equiv 1\pmod n。随机取 kk 个底数检验，全部通过则大概率为素数；但卡迈克尔数会被误判。时间复杂度为 O(klog⁡n)O(k\log n)。

245 Bcpp
ll Pow(ll x,ll y,ll mod)
{
	x%=mod;
	ll res=1;
	while(y)
	{
		if(y&1)res=res*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return res;
}
bool prime(int n,int k)
{
	if(n<3)return n==2;
	while(k--)
	{
		if(Pow(rand()%(n-2)+2,n-1,n)!=1)return 0;
	}
	return 1;
}

Miller–Rabin 素性测试​

在费马测试上增加二次探测：把 n−1=u⋅2tn-1=u\cdot 2^t，检验 aua^u 反复平方的过程中是否出现非平凡的 11 的平方根，可滤掉卡迈克尔数，误判概率极低。时间复杂度为 O(klog⁡3n)O(k\log^3 n)。

416 Bcpp
ll Pow(ll x,ll y,ll mod)
{
	x%=mod;
	ll res=1;
	while(y)
	{
		if(y&1)res=res*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return res;
}
bool prime(int n,int k)
{
	if(n<3||n%2==0)return n==2;
	if(n%3==0)return n==3;
	int u=n-1,t=0;
	while(u%2==0){u>>=1;t++;}
	while(k--)
	{
		ll v=Pow(rand()%(n-3)+2,u,n);
		if(v==1)continue;
		int s;
		for(s=0;s<t;s++)
		{
			if(v==n-1)break;
			v=v*v%n;
		}
		if(s==t)return 0;
	}
	return 1;
}

常见素数​

100100 以内：

2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,972,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97

常见模数：

1009,10007,10009,100003,1000003,100000007=108+7,1000000007=109+7,1000000009=109+9,1000000000000000009=1018+9,998244353=119×223+11009,10007,10009,100003,1000003,100000007=10^8+7,1000000007=10^9+7,1000000009=10^9+9,1000000000000000009=10^{18}+9,998244353=119\times 2^{23}+1

梅森素数：

3=22−1,7=23−1,31=25−1,127=27−1,8191=213−1,131071=217−1,524287=219−1,2147483647=231−1,…,2136279841−13=2^2-1,7=2^3-1,31=2^5-1,127=2^7-1,8191=2^{13}-1,131071=2^{17}-1,524287=2^{19}-1,2147483647=2^{31}-1,\dots,2^{136279841}-1

日期素数：

19260817,19370707,19491001,19970701,2020012319260817,19370707,19491001,19970701,20200123

特殊含义：

13331,13337,23333,314159,2718281,1618033,1145141,52013141,23456789,8281807978777675747372717069686766656463626160595857565554535251504948474645444342414039383736353433323130292827262524232221201918171615141312111098765432113331,13337,23333,314159,2718281,1618033,1145141,52013141,23456789, 82818079787776757473727170696867666564636261605958575655545352515049484746454443424140393837363534333231302928272625242322212019181716151413121110987654321

例题​

洛谷 P1217 [USACO1.5] 回文质数 Prime Palindromes

写一个程序来找出范围 [a,b][a,b] 间的所有回文质数。（5≤a<b≤100,000,0005\le a<b\le 100,000,000）