解题思路:暴力耗时长显然不是最优算法,这里提供一种效率极高的算法——欧拉筛法。
注意事项:看代码
参考代码:
#include <iostream>
using namespace std;
#define MAX 10000000
int Prim[MAX]={0};
int f[MAX];
void Isprime(int m,int n)
{
int k = 0;
int sum = 0;
Prim[0] = 1;//0和1都不是素数,一开始就排除
Prim[1] = 1;
for(int i = 2; i < MAX; i++)
{
if(!Prim[i])//判断是否为素数
{
f[k++] = i;储存素数
}
for(int j = 0; j <= k&&i * f[j]<MAX;j++)
{
Prim[i*f[j]] = 1;
if((i%f[j]) == 0)//重点,如果i == 9;此时素数有2,3,5,7.9*2=18,Prim[18] = 1;9*3=27,Prim[27]=1
break;//但是因为9%3==0,所以break。因为5*9可以用3*15表示,如果此时计算了,i=15时又会重复计算。所以如果i%f[j] == 0,直接跳出循环
}
}
for(int i = m; i <= n; i++)
{
if(!Prim[i])
sum += i;
}
cout << sum << endl;
}
int main()
{
int m,n;
cin >> m >> n;
Isprime(m,n);
return 0;
}
0.0分
1 人评分
程序员的表白 (C语言代码)浏览:1319 |
C语言训练-列出最简真分数序列* (C语言代码)浏览:604 |
1157题解浏览:711 |
愚蠢的摄影师 (C++代码)浏览:934 |
【亲和数】 (C语言代码)浏览:597 |
C语言程序设计教程(第三版)课后习题1.6 (C语言代码)浏览:701 |
C语言程序设计教程(第三版)课后习题1.5 (C++代码)浏览:403 |
1218题求大神帮忙看看怎么不能过浏览:690 |
C语言程序设计教程(第三版)课后习题4.9 (C语言代码)浏览:431 |
简单的事情 (C语言代码)浏览:556 |