一、定义
质数(prime number)又称素数,有无限个。一个大于1的自然数,除了1和它本身外,不能被其他自然数整除,换句话说就是该数除了1和它本身以外不再有其他的因数;否则称为合数。
二、相关定理
- 在一个大于1的数a和它2倍之间(即区间(a, 2a]中)必存在至少一个素数。
- 存在任意长度的素数等差数列。(格林和陶哲轩,2004年)
- 一个偶数可以写成两个数字之和,其中每一个数字都最多只有9个质因数。(挪威布朗,1920年)
- 一个偶数必定可以写成一个质数加上一个合成数,其中的因子个数有上界。(瑞尼,1948年)
- 一个偶数必定可以写成一个质数加上一个最多由5个因子所组成的合成数。后来,有人简称这结果为 (1 + 5) (中国,1968年)
- 一个充分大偶数必定可以写成一个素数加上一个最多由2个质因子所组成的合成数。简称为 (1 + 2) (中国陈景润)
三、著名猜想
哥德巴赫猜想:是否每个大于2的偶数都可写成两个素数之和?
孪生素数猜想:孪生素数就是差为2的素数对,例如11和13。是否存在无穷多的孪生素数?
斐波那契数列内是否存在无穷多的素数?是否有无穷多个的梅森素数?在n2与(n+1)2之间是否每隔n就有一个素数?是否存在无穷个形式如X2+1素数?
四、性质
(1)质数p的约数只有两个:1和p。
(2)初等数学基本定理:任一大于1的自然数,要么本身是质数,要么可以分解为几个质数之积,且这种分解是唯一的。
(3)质数的个数是无限的。
(4)质数的个数公式π(n)是不减函数。
(5)若n为正整数,在n的2次方到(n+1)的2次方 之间至少有一个质数。
(6)若n为大于或等于2的正整数,在n到n!之间至少有一个质数。
(7)若质数p为不超过n(n大于等于4)的最大质数,则p>n/2 。
五、著名难题
哥德巴赫猜想
黎曼猜想
孪生质数
梅森质数
六、求质数的方法
1、一般
从2到n-1判断有没有能整除n的数。如果有,则不是素数,否则,是素数
bool is_prime(int n){
if (n < 2){
return false;
}
int i;
for (i = 2; i < n; i++){
if (n%i == 0){
return false;
}
}
return true;
}
2、优化
从2一直算到sqrt(n),这样算法复杂度降低了很多
bool is_prime(int n){
if (n < 2){
return false;
}
int i;
for (i = 2; i*i <= n; i++){
if (n%i == 0){
return false;
}
}
return true;
}
3、米勒拉宾素数测试
int tab[]={2, 3, 5, 7};
long long qpow(int a, int b, int r) //(a^b)%r 快速幂取模
{
long long ret = 1, tmp = a;
while(b)
{
if (b&1)
ret = ret*tmp%r;
tmp = tmp*tmp%r;
b >>= 1;
}
return ret;
}
bool Miller_Rabbin(int n, int a)//米勒拉宾素数测试
{
int r = 0, s = n-1, j;
long long k;
if(n%a == 0) return false;
while((s&1) == 0)
{
s >>= 1;
r++;
}
k = qpow(a, s, n);
if(k == 1) return true;
for (j = 0; j < r; j++, k=k*k%n)
if (k == n-1)
return true;
return false;
}
bool Isprime(int n)//判断是否是素数
{
for (int i = 0; i < 4; i++)
{
if (n == tab[i])
return true;
if (!Miller_Rabbin(n, tab[i]))
return false;
}
return true;
}
4、普通筛
时间复杂度是O(nloglogn),不足之处在于一个合数可能被筛选多次。
void Prime(){
memset(tag,0,sizeof(tag));
tag[0]=tag[1]=1;
int cnt=0;
for(int i=2; i*i <= n; i++)
if(tag[i]==0){
prime[cnt++]=i;
for(int j=i+i;j<=n;j+=i)
tag[j]=1;
}
}
5、线性筛
时间复杂度为O(n),原因在于每个合数保证只被它最小的那个质因子筛选。关键代码在第10,11行,因为如果i能整出prime[j],那么i肯定是个合数,且i中有质因子肯定小于等于prime[j],所以到此就可以停止了,因为后面的prime[]会比i小的那个质因子要大。
void Prime(){
memset(tag,0,sizeof(tag));
int cnt=0;
tag[0]=tag[1]=1;
for(int i = 2; i<N; i++){
if(!tag[i])
prime[cnt++]=i;
for(int j=0;j<cnt && prime[j]*i<N; j++){
tag[i*prime[j]] = 1;
if(i % prime[j]==0)
break;
}
}
}