求一个一百万以内的所有质数的求解过程(用C++语言)
答案:1 悬赏:50 手机版
解决时间 2021-02-13 21:48
- 提问者网友：轻浮
- 2021-02-13 00:37
求一个一百万以内的所有质数的求解过程(用C++语言)
最佳答案
- 五星知识达人网友：第幾種人
- 2021-02-13 01:05
#include <iostream>
#include <cmath>
unsigned int primes[1000000];// 实际上只用开1000000以内质数个数那么大，也可以用链表
unsigned int num = 0;
int main()
{
for (unsigned int i=2;i<=1000000;i++)
{
unsigned int j, sqrti = std::sqrt(i);
for (j=0;j<num && primes[j]<=sqrti;j++)
if (!(i%primes[j]))
break;
if (i%primes[j])
{
std::cout<<i<<std::endl;
primes[num++] = i;
}
}
return 0;
}
这其实虽然麻烦了一点，但大幅优化了速度，用空间换取时间
#include <cmath>
unsigned int primes[1000000];// 实际上只用开1000000以内质数个数那么大，也可以用链表
unsigned int num = 0;
int main()
{
for (unsigned int i=2;i<=1000000;i++)
{
unsigned int j, sqrti = std::sqrt(i);
for (j=0;j<num && primes[j]<=sqrti;j++)
if (!(i%primes[j]))
break;
if (i%primes[j])
{
std::cout<<i<<std::endl;
primes[num++] = i;
}
}
return 0;
}
这其实虽然麻烦了一点，但大幅优化了速度，用空间换取时间
我要举报
如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
点此我要举报以上问答信息
大家都在看
推荐资讯