python反素数算法优化_【数学】素数相关算法、结论总结
赞
踩
弱菜开始学数论了，不定时更新。。。
一.素数定理
素数分布：小于x的素数大约有 x/ln(x)个
推论：如果Pn为第n个素数 那个Pn约等于n*ln(n);
二.素数测试
1.sqrt(n)的朴素测试。这个就不多说了，数据范围小的时候比较方便
2.nlogn的筛法
voidsetprime()
{
memset(prime, 0, sizeof(prime));//为了方便赋值。令prime[i]=0 表示 i是素数for (int i=2; i
{for (int k=i*i; k
prime[k]=1;
}return;
}
3.线性筛
2中筛法会重复筛掉部分合数，因此复杂度还可以优化，得到线性筛
voidsetprime()
{for(long i = 2 ; i < N ; i ++)
{if(!isNotPrime[i])
prime[num_prime++]=i;for(long j = 0 ; j < num_prime && i * prime[j] < N ; j ++)
{
isNotPrime[i* prime[j]] = 1;if( !(i %prime[j] ) )break; //关键优化
}
}return;
}
此筛法的关键在于注释中的break。prime[]数组记录素数。当i可以整除prime[j]的时候break，原理见 http://blog.csdn.net/leolin_/article/details/6642126
2,3中的筛法单独使用都只能筛出较小范围的素数，范围较大，如1e9时，数组开不了，时间也是不允许的
4.改进的筛法素数测试
此方法是2.3中方法的应用和延伸，用来筛超大范围的质数。。由1中朴素判断法我们可以知道，判断素数只需要判断sqrt范围内有没有因子即可，所以在范围变大的时候，我们可以先用筛法筛出
sqrt(n)中的素数并保存在数组中。范围1e9的话只需要筛出30000多内的素数即可，再用保存下来的素数去对更大范围的数进行素数测试。例题poj2689(最大所测试数达到了2147483647)
5.miller-robin大素数测试
理论基础，费马小定理： 若p为素数，则对于正整数a，有a^p%p==a%p;若存在a不满足上式，则p为合数
同时我们规定 若n为合数且满足 a^n %n=a%n,称n为以a为底的伪素数。
mille robin素数测试的算法原理：随机取多个a进行测试，若都满足a^p%p==a%p，则可以近似认为 p为素数。
模板:
long long random(long longn)
{
srand(time(0));return (long long)(rand()%(n-1)+1);
}long long multi(long long a,long long b,long long m)//a*b%m
{long long res=0;while(b>0)
{if(b&1)
res=(res+a)%m;
b>>=1;
a=(a<<1)%m;
}returnres;
}long long quickmod(long long a,long long b,long long m) //a^b%m
{long long res=1;while(b)
{if(b&1)
res=multi(res,a,m);
b>>=1;
a=multi(a,a,m);
}returnres;
}int primetest(long longn)
{for(int i=1;i<=100;i++)
{long long a=random(n-1);if(quickmod(a,n,n)!=a)return 0;
}return 1;
}
//这个是一次判断，会受到卡迈克尔数的影响，下面的是二次判断版int check(long long a,long long n,long long x,long longt)
{long long res=quickmod(a,x,n);long long last=res;for(int i=1;i<=t;i++)
{
res=multi(res,res,n);if(res==1&&last!=1&&last!=n-1) return 1;
last=res;
}if(res!=1) return 1;return 0;
}int primetest(long longn)
{if(n<2)return 0;if(n==2)return 1;if((n&1)==0) return 0;long long x=n-1;long long t=0;while((x&1)==0){x>>=1;t++;}for(int i=0;i<20;i++)
{long long a=random(n);if(check(a,n,x,t))return 0;
}return 1;
}
三.算术基本定理
任何一个大于1的正整数都可以表示为素数的积的形式。
令a=p1^a1*p2^a2......*pn^an b=p1^b1*p2^b2......*pn^bn
(1)设d(a)为a的正因子的个数，s(n)为所有因子之和，则
d(n)=(a1+1)(a2+1).....*(an+1);
s(n)=乘积(i=1...n):(pi^(ai+1)-1)/(pi-1);
(2)gcd(a,b)=p1^min(a1,b1)...*pn^(min(an,bn));
lcm则为 max..这两个很好理解
(3)n!的素因子分解中的素数P的幂为
sum(i=1.....∞)[n/(p^i)]; 例题： 求n！末尾0的个数。只需要用此公式算出因子中5的个数。
四.反素数
(1)定义：对于任何正整数x,其约数的个数记做g(x).例如g(1)=1,g(6)=4.如果某个正整数x满足:对于任意i(0
(2)性质：性质一:一个反素数的质因子必然是从2开始连续的质数.
性质二:p=2^t1*3^t2*5^t3*7^t4.....必然t1>=t2>=t3>=....
结合算数基本定理(1)对性质2进行证明：如果ti
因子数目相同，但x更小的情况，与反素数的定义矛盾。
(3)例题：zoj2562，给定n，求不大于n的正整数中因子最多的数 题解
五.素因子分解
基于miller-robin的随机数算法：模板如下 原理及延伸 例题：poj1881题解 poj2429题解
long long pollardrho(long long n,long longc)
{long longx,y,d,i,k;
i=1;k=2;
x=random(n);
y=x;while(1)
{
i++;
x=(multi(x,x,n)+c)%n;long long tmp=y-x>=0?y-x:x-y;
d=gcd(tmp,n);if(d>1&&d
{
y=x;
k+=k;
}
}
}void findfac(long longn)
{if(n==1)return;if(primetest(n))
{
fac[nfac++]=n;return;
}long long p=n;while(p>=n)
p=pollardrho(n,random(n-1));
findfac(p);
findfac(n/p);
}
