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

2019-11-06 06:06:23

字体：大中小

来源：转载

供稿：网友

质数概念：

质数（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;}

结果图：这里写图片描述

改进：众所周知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;}

结果图：这里写图片描述