文档介绍：简单数论(数论上)
素数求解是在ACM竞赛中很常用到的基本算法。那么大家平时是怎么求解素数的?
10以内:2、3、5、7
100以内:大家平时怎么求?
10000又怎么求?
1000000呢?
下面给大家介绍!
第一节素数
几种素数的求解方法
第一种(大家平时最常用的):
//用素数表判定素数,先调用initprime
int plist[10000],pcount=0;
int prime(int n){
int i;
if ((n!=2&&!(n%2))||(n!=3&&!(n%3))||(n!=5&&!(n%5))||(n!=7&&!(n%7)))
return 0;
for (i=0;plist[i]*plist[i]<=n;i++)
if (!(n%plist[i]))
return 0;
return n>1;
}
几种素数的求解方法
第二种求法:
void initprime(){
int i;
for (plist[pcount++]=2,i=3;i<50000;i++)
if (prime(i))
plist[pcount++]=i;
}
几种素数的求解方法
基本原理:
筛素数的基本方法是用来筛选出一定范围内的素数素数筛法的基本原理,利用的是素数p只有1和p这两个约数,并且一个数的约数一定不大于本身,素数筛法的过程:把从1开始的、某一范围内的正整数从小到大顺序排列, 1不是素数,首先把它筛掉。剩下的数中选择最小的数是素数,然后去掉它的倍数。依次类推,直到筛子为空时结束。
求解用途:
素数筛法经常作为一道题的一部分用来打一定范围内素数表,然后利用素数表作为基础解题。
几种素数的求解方法
第三种求素数的方法(筛选法)【重点须掌握】:
bool isprime[N];//N表示范围
int prime[N],cnt;
void Prime()
{
int i,j;
cnt=0;
memset(isprime,true,sizeof(isprime));
isprime[1]=false;
for(i=2;i<=N;i++)
{
if(isprime[i])
{
t++]=i;//记录素数
for(j=i*i;j<=N;j+=i)//因为小于i的所有的倍数都被筛过,所以直接从i*i开始,从这里也可以看出,筛素数时到N^
isprime[j]=false;
}
}
}
费尔马小定理:如果p是一个素数,且0<a<p,则a^(p-1)%p=1.
利用费尔马小定理,对于给定的整数n,可以设计素数判定算法,通过计算d=a^(n-1)%n来判断n的素性,当d!=1时,n肯定不是素数,当d=1时,n很可能是素数.
二次探测定理:如果p是一个素数,且0<x<p,则方程x^2%p=1的解为:x=1或 x=p-1.
利用二次探测定理,可以再利用费尔马小定理计算a^(n-1)%n的过程中增加对整数n的二次探测,一旦发现违背二次探测条件,即得出n不是素数的结论.
如果n是素数,则(n-1)必是偶数,因此可令(n-1)=m*(2^q),其中m是正奇数( 若n是偶数,则上面的m*(2^q)一定可以分解成一个正奇数乘以2的k次方的形式),q是非负整数,考察下面的测试:
序列:a^m%n; a^(2m)%n; a^(4m)%n; ……;a^(m*2^q)%n
把上述测试序列叫做Miller测试,关于Miller测试,有下面的定理:
定理:若n是素数,a是小于n的正整数,则n对以a为基的Miller测试,结果为真.
Miller测试进行k次,将合数当成素数处理的错误概率最多不会超过4^(-k).
Miller_Rabin测试T次时,它产生一个假的素数所花费的时间不超过1/4^T
用途:大素数的判断;
还有一种方法叫做随机素数的测试( Miller-Rabin) 此小节我不讲述
typedef long long ll;
#define times 10//伪素数测试次数,算法出错概率<=4^(-times)
ll quickmod(ll a, ll b, ll n) {
ll ret = 1;
a %= n;
while(b) {
if(b & 1)
ret = multi(ret, a, n);
a = multi(a, a, n);
b >>= 1;
}
return ret;
}
int witness(ll a, ll n)
{
ll m = n - 1;
int j = 0;
while(!(m & 1)) {
j++;
m >>= 1;
}
long long x = quick