素数

参考资料

• 素数 - OI Wiki
• 素数 - 维基百科
• 素数列表 - 维基百科

素性测试

试除法

枚举 $2$ 到 $\sqrt 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 素性测试

基于费马小定理：若 $n$ 为素数，则对任意 $a$ 有 $a^{n-1}\equiv 1\pmod n$。随机取 $k$ 个底数检验，全部通过则大概率为素数；但卡迈克尔数会被误判。时间复杂度为 $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\cdot 2^t$，检验 $a^u$ 反复平方的过程中是否出现非平凡的 $1$ 的平方根，可滤掉卡迈克尔数，误判概率极低。时间复杂度为 $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;
}

常见素数

$100$ 以内：

$$2,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=10^8+7,1000000007=10^9+7,1000000009=10^9+9,1000000000000000009=10^{18}+9,998244353=119\times 2^{23}+1$$

梅森素数：

$$3=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,20200123$$

特殊含义：

$$13331,13337,23333,314159,2718281,1618033,1145141,52013141,23456789$$

例题

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

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