求质数（素数）算法及其改进

秒速五厘米 2022-09-27 04:57 190阅读 0赞

### 质数概念： ###

质数（prime number）又称素数，有无限个。质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数的数称为质数。

数学还是要认真扣概念的，各位看官首先默读一遍概念吧~

### 算法思路： ###

本例演示求n以内的素数个数。同时类比打印n以内的素数；求前n个素数的乘积模50000；求前n个素数的乘积等题目。

判断一个数k是否为素数需要判断这个数有没有其他因数，也就是k能否除尽区间\[2，根号k\]。

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

改进前代码：

#include <iostream>
    #include<math.h>
    
    using namespace std;
    
    int main()
    {
        int n, sum = 0, m;
        cin >> n;
        for(int i = 2; i <= n; i++){
            m = sqrt(i);
            int j;
            for(j = 2; j <= m+1; j++){
                if(i%j == 0){
                    break;
                }
            }
            if(j > m) sum++;
    
        }
        cout << sum <<endl;
        return 0;
    }

结果图：  
![这里写图片描述][SouthEast]

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

改进：众所周知C++开根号费时，此处改进就是不进行开根号。例如：\[9, 24\]开根号都是3，我们设开根号的结果为m，即是\[m\*m, m\*(m+2)\]，这样就大大减少了计算次数，也不用开根号，只需让在区间里的数都去除2到m，并判断每一个结果的余数是否为0，为0则跳出循环即可。

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

改进后代码

#include <iostream>
    
    using namespace std;
    
    int main()
    {
        int n, m = 1, Max;
        int sum = 0;
        cin >> n;
        Max = m*m + 2*m;
        for(int i = 2; i <= n; i++){
    
            if(i > Max){
                m++;
                Max = m*m + 2*m;
            }
            int j;
            for(j = 2; j <= m+1; j++){
                if(i%j == 0) break;
            }
            if(j > m){
                sum++;
            }
    
        }
    
        cout << sum <<endl;
        return 0;
    }

结果图：  
![这里写图片描述][SouthEast 1]

[SouthEast]: /images/20220708/a3e1165a598b4626a9b7627177c9d624.png
[SouthEast 1]: /images/20220708/ec8739f12d1a4b60aa7da5312f3d250d.png