求范围内质数（素数）
发布时间
阅读量：
阅读量
素数定义：除了1和自身之外，不能被其他整数整除。
方法1：质朴的方法，重复调用的方法是判断一个数是不是质数。当求一个数是不是质数时，这种方法是正确的，也没有优化空间，但是当求一个区间内的质数时，可以进行优化。
方法2：方法1存在的问题是，没有有效利用已经确定的信息，也即对后续数字判断时无法利用已经求得的信息。如若判断某一数字为质数，那么以它为因子的所有数，都不会是质数，故将其剔除。（若想换区时间，必须消耗空间）
总结：方法1是找出所有质数；方法2是剔除所有非质数，判断是否是非质数，虽然不复杂，但是会重复判断，故用质数作为因子减少重复的情况。
#include<iostream>
#include<vector>
using namespace std;
bool check(int num)
{
for (int i = 2; i*i <= num; i++)
{
if (num%i == 0)
{
return false;
}
}
return true;
}
int countprimes(int n)
{
if (n < 2) return 0;
int num = 0;
vector<bool> flag(n+1,true);
for (int i = 2; i <= n; i++)
{
if (flag[i])
{
num++;
cout << i << " ";
for (int j = i*i; j <= n; j += i) //剔除非质数，注意从i*i开始，每次加i
{
flag[j] = false;
}
}
}
return num;
}
int main()
{
cout << "方法1" << endl;
for (int i = 2; i <= 100; i++)
{
if (check(i)) cout << i << " ";
}
cout << endl;
cout << "方法2" << endl;
countprimes(100);
system("pause");
return 0;
}
AI写代码
全部评论 (0)
还没有任何评论哟~