跳到主要内容

素数

参考资料​

素性测试​

试除法​

时间复杂度为 O(n)O(\sqrt{n})。

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 素性测试​

时间复杂度为 O(klog⁡n)O(k\log n)。

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 素性测试​

时间复杂度为 O(klog⁡3n)O(k\log^3{n})。

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;
}

例题​

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

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

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

代码（1）
#include <bits/stdc++.h>
using namespace std;

bool palindrome(int n)
{
	int x=0,y=n;
	while(n)
	{
		x=x*10+n%10;
		n/=10;
	}
	return x==y;
}
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;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int a,b;
	cin>>a>>b;
	for(int i=a|1;i<=b;i+=2)
	{
		if(palindrome(i)&&prime(i))cout<<i<<'\n';
	}
	return 0;
}