发新帖
  2. 技术文章
  3. 质数

[算法] 质数

零下一度 2024-2-18 617

质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数（规定1既不是质数也不是合数）。质数的个数是无穷的。欧几里得的《几何原本》中有一个经典的证明。它使用了证明常用的方法：反证法。具体证明如下：假设质数只有有限的n个，从小到大依次排列为p1，p2，……，pn，设N=p1×p2×……×pn。如果 为素数，则 要大于p1，p2，……，pn，所以它不在那些假设的素数集合中。如果N+1为合数，因为任何一个合数都可以分解为几个素数的积；而N和N+1的最大公约数是1，所以不可能被p1，p2，……，pn整除，所以该合数分解得到的素因数肯定不在假设的素数集合中。因此无论该数是素数还是合数，都意味着在假设的有限个素数之外还存在着其他素数。所以原先的假设不成立。也就是说，素数有无穷多个。其他数学家给出了一些不同的证明。欧拉证明了全部素数的倒数之和是发散的，恩斯特·库默的证明更为简洁，哈里·弗斯滕伯格则用拓扑学加以证明。尽管整个素数是无穷的，仍然有人会问“100，000以下有多少个素数？”，“一个随机的100位数多大可能是素数？”。素数定理可以回答此问题。

性质

1、质数p的约数只有两个：1和p。

2、算术基本定理：任一大于1的自然数，要么本身是质数，要么可以分解为几个质数之积，且这种分解是唯一的。

3、质数的个数是无限的。

4、质数的个数公式 是不减函数。

5、若n为正整数，在 到 之间至少有一个质数。

6、若n为大于或等于2的正整数，在n到 之间至少有一个质数。

7、在一个大于1的数a和它的2倍之间（即区间（a, 2a]中）必存在至少一个素数。

8、存在任意长度的素数等差数列 [1]。

9、任一充分大的偶数都可以表示成一个素数加一个素因子个数不超过2个的数的和，简称为“1+2”。 [2]。

应用

质数被利用在密码学上，所谓的公钥就是将想要传递的信息在编码时加入质数，编码之后传送给收信人，任何人收到此信息后，若没有此收信人所拥有的密钥，则解密的过程中（实为寻找素数的过程），将会因为找质数的过程（分解质因数）过久，使即使取得信息也会无意义。

在汽车变速箱齿轮的设计上，相邻的两个大小齿轮齿数设计成质数，以增加两齿轮内两个相同的齿相遇啮合次数的最小公倍数，可增强耐用度减少故障。

在害虫的生物生长周期与杀虫剂使用之间的关系上，杀虫剂的质数次数的使用也得到了证明。实验表明，质数次数地使用杀虫剂是最合理的：都是使用在害虫繁殖的高潮期，而且害虫很难产生抗药性。

以质数形式无规律变化的导弹和鱼雷可以使敌人不易拦截。

多数生物的生命周期也是质数（单位为年），这样可以最大程度地减少碰见天敌的机会。

编程

基本判断思路

在一般领域，对正整数n，如果用2到 之间的所有整数去除，均无法整除，则n为质数。

代码

Python 代码：

from math import sqrt
def is_prime(n):
    if n == 1:
        return False
    for i in range(2, int(sqrt(n))+1):
        if n % i == 0:
            return False
    return True

Java代码：

1.  
public static boolean testIsPrime2(int n){
   if (n <= 3) {
return n > 1;
}
   
   for(int i=2;i<n;i++){
   if(n%i == 0)
   return false;
   }
   return true;
}
/*优化后*/
public static boolean testIsPrime3(int n){
   if (n <= 3) {
return n > 1;
}
   
   for(int i=2;i<=Math.sqrt(n);i++){
   if(n%i == 0)
   return false;
   }
   return true;
}
2.
public class Prime {
    public static void main（String[] args） {
        int a = 17; //判断17是不是质数
        int c = 0;
        for (int b = 2; b < a; b++) {
            if (a % b != 0) {
                c++;
            }
        }
        if (c == a - 2) {
            System.out.println(a + "是质数");
        } else {
            System.out.println(a + "不是质数");
        }
    }
}

PHP代码：

function isPrime($n) {//TurkHackTeam AVP production
    if ($n <= 3) {
        return $n > 1;
    } else if ($n % 2 === 0 || $n % 3 === 0)  {
        return false;
    } else {
        for ($i = 5; $i * $i <= $n; $i += 6) {
            if ($n % $i === 0 || $n % （$i + 2) === 0） {
                return false;
            }
        }
        return true;
    }
}

C#代码：

using System;
namespace 计算质数
{
class Program
{
static void Main(string[] args)
{
　           for (int i = 2,j=1; i < 2100000000&&j<=1000; i++)//输出21亿内的所有质数，j控制只输出1000个。
　           {
　               if (st(i))
　               {
　                   Console.WriteLine("{0,-10}{1}",j,i);
　                   j++;
　               }
　           }
　       }
　       static bool st(int n)//判断一个数n是否为质数
　       {
　           int m = (int)Math.Sqrt(n);
　           for(int i=2;i<=m;i++)
            {
                if(n%i==0 && i!=n)
                    return false;
　          } 
            return true;
　       }
　   }
}

C代码：

#include <stdio.h>
#include <windows.h>
int main()
{
    double x,y,i;
    int a,b;
    x = 3.0;
    do{
        i = 2.0;
        do{
            y = x / i;
            a = (int)y;
            if(y != a)//用于判断是否为整数
            {
                if(i == x - 1)
                {
                    b = (int)x;
                    printf("%d\n",b);
                }
            }
            i++;
        }while(y != a);
        x++;
    }while(x <= 10000.0);//3到10000的素数
    system("pause");//防止闪退
    return 0;
}

C/C++代码：

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const long long size=100000;//修改size的数值以改变最终输出的大小
long long zhishu[size/2];
void work (){//主要程序
    zhishu[1]=2;
    long long k=2;
    for(long long i=3;i<=size;i++){//枚举每个数
        bool ok=1;
        for(long long j=1;j<k;j++){//枚举已经得到的质数
            if(i%zhishu[j]==0){
                ok=!ok;
                break;
            }
        }
        if（ok）{
            zhishu[k]=i;
            cout<<"count"<<k<<' '<<i<<endl;
            k++;
        }
    }
}
int main（）{
    freopen("zhishu.out","w",stdout);
    cout<<"count1 2"<<endl;
    work();
    return 0;
}
bool isPrime(unsigned long n) {
    if (n <= 3) {
        return n > 1;
    } else if (n % 2 == 0 || n % 3 == 0) {
        return false;
    } else {
        for (unsigned short i = 5; i * i <= n; i += 6) {
            if (n % i == 0 || n % （i + 2） == 0) {
                return false;
            }
        }
        return true;
    }
}

Pascal代码：

function su(a:longint):boolean;
var
begin
    if a=2 then exit(true) else for i:=2 to trunc(sqrt(a))+1 do if a mod i=0 then exit（false）;
    exit(true);
end.

Javascript代码：

function isPrime(n) {
    if (n <= 3) { return n > 1; }
    if (n % 2 == 0 || n % 3 == 0) { return false; }
    for (var  i = 5; i * i <= n; i ++) {
        if (n % i == 0 || n % (i + 1) == 0) { return false; }
    }
    return true;
}

Go代码：

func isPrime(value int) bool {
    if value <= 3 {
        return value >= 2
    }
    if value%2 == 0 || value%3 == 0 {
        return false
    }
    for i := 5; i*i <= value; i += 6 {
        if value%i == 0 || value%（i+2） == 0 {
            return false
        }
    }
    return true
}

Basic 代码

Private Function IfPrime（ByVal x As Long） As Boolean
    Dim i As Long
    If x < 0 Then x = -x
    If x = 2 Then Return True
    If x = 1 Then Return True
    If x = 3 Then Return False
    If x = 0 Then 
        MsgBox("error",,)
        Return False
    End If
    For i = 2 To Int(Sqrt(x)) Step 1
        If x Mod i = 0 Then Return False
    Next i
    Return True
End Function

ALGOL代码

begin
    Boolean array a[2:100];
    integer i,j;
    for i := 2 step 1 until 100 do
    a[i] := true;
    for i := 2 step 1 until 10 do
        if a[i] then
                for j := 2 step 1 until 1000÷i do
                    a[i × j] := false;
    for i := 2 step 1 until 100 do
        if a[i] then
            print (i);
end

    

素性检测

素性检测一般用于数学或者加密学领域。用一定的算法来确定输入数是否是素数。不同于整数分解，素性测试一般不能得到输入数的素数因子，只说明输入数是否是素数。大整数的分解是一个计算难题，而素性测试是相对更为容易（其运行时间是输入数字大小的多项式关系）。有的素性测试证明输入数字是素数，而其他测试，比如米勒 - 拉宾（Miller–Rabin ）则是证明一个数字是合数。因此，后者可以称为合性测试。

素性测试通常是概率测试（不能给出100%正确结果）。这些测试使用除输入数之外，从一些样本空间随机出去的数；通常，随机素性测试绝不会把素数误判为合数，但它有可能为把一个合数误判为素数。误差的概率可通过多次重复试验几个独立值a而减小；对于两种常用的测试中，对任何合数n，至少一半的a检测n的合性，所以k的重复可以减小误差概率最多到 ，可以通过增加k来使得误差尽量小。

随机素性测试的基本结构：

1、随机选取一个数字a。

2、检测某个包含a和输入n的等式（与所使用的测试方法有关）。如果等式不成立，则n是合数，a作为n是合数的证据，测试完成。

3、从1步骤重复整个过程直到达到所设定的精确程度。

在几次或多次测试之后，如果n没有被判断为合数，那么可以说n可能是素数。

常见的检测算法：费马素性检验（Fermat primality test），米勒拉宾测试（Miller–Rabin primality test） ，Solovay–Strassen测试，卢卡斯-莱默检验法（Lucas–Lehmer primality test）。

筛素数法

筛素数法可以比枚举法节约极大量的时间（定n为所求最大值，m为≤n的质数个数，那么枚举需要O（n^2）的时间复杂度，而筛素数法为O（m*n）,显然m<<n，所以时间效率有很大提升。）。如1000000的数据范围，用筛素数法可在2s内解决。

思路：建立一个bool型数组M，若已知一个数M[k]是质数，那么其i（i为正整数）倍M[k*i]必然为合数，可将其去除。

//c++代码 all rights reserve.
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const long long size=1000000;//修改此值以改变要求到的最大值
bool zhishu[size+5]={false};
int main（）{
    freopen（"zhishu.out","w",stdout）;//输出答案至“筛质数（shaizhishu）.exe”所在文件夹内
    zhishu[2]=true;
    for（long long i=3;i<=size;i+=2）zhishu[i]=true;//所有奇数标为true，偶数为false
    for（long long i=3;i<=size;i++）{
        if（zhishu[i]）{//如果i是质数
            int cnt=2;
            while（cnt*i<=size）{//把i的倍数标为false（因为它们是合数）
                zhishu[cnt*i]=false;
                cnt++;
            }
        }
    }
    int cnt=1;
    for（int i=2;i<=size;i++）{//全部遍历一遍
        if（zhishu[i]）{//如果仍然标记为true（是质数）则输出
            cout<<cnt<<' '<<i<<endl;
            cnt++;
        }
    }
    return 0;
}
/*
样例输出结果，第一个数是个数，第二个是第几个质数
1 2
2 3
3 5
4 7
5 11
6 13
7 17
8 19
9 23
10 29
11 31
12 37
13 41
14 43
15 47
16 53
17 59
18 61
19 67
20 71
21 73
22 79
23 83
24 89
25 97
*/

筛选法的Java实现，如下：

/**
 * @title SOE
 * @desc 简单的埃氏筛选法计算素数 
 * @author he11o
 * @date 2016年5月3日
 * @version 1.0
 */
public class SOE {
    public static int calPrime（int n）{
        if（n<=1）{
            return 0;
        }
        byte[] origin = new byte[n+1];
        int count = 0;
        for（int i=2;i<n+1;i++）{
            if（origin[i] == 0）{
                count++;
                int k = 2;
                while（i*k<=n）{
                    origin[i*k] = 1; 
                    k++;
                }
            }else{
                continue;
            }
        }
        return count;
    }
}

采用简单的埃氏筛选法和简单的开方判断素数法计算1000000以内素数的个数的效率比较：

StopWatch '计算1000000以内素数的个数': running time （millis） = 268

-----------------------------------------

ms % Task name

-----------------------------------------

00024 009% 简单的埃氏筛选法；

00244 091% 简单的开方判断素数法。


@百度百科



最新回复 (0)
返回
零下一度
主题数
931
帖子数
0
注册排名
1
©2018 
冀ICP备13018807号-1
Time: 0.007