把int改成long long 就对了,太伤心了。。。
解题思路:一个合数n他的最小质因子不会超过sqrt(n),所以我们求区间[a,b]的素数,我们只需要
找出[2,sqrt(b)]以内的素数,然后将其倍数从[a,b]里面里面去掉就行,最后剩下的就是
[a,b]内的素数了。
注意:整形存不下,要用long long,区间不要开太大,也不要开太,还有,需要用到线性筛素数筛
选素数,普通方法会超时。
#include <iostream> #include <stdio.h> #include <string> #include <cmath> using namespace std; typedef long long ll; const int maxn = 1000001; bool vis[maxn]; //标记数组,true是素数,false是合数 int ans[maxn]; //存储得到的素数 int tot; bool isprime[maxn]; void Getprime(int n) //线性筛素数 { vis[1] = true; //1不是素数 for (int i = 2; i <= n; i++) //进行判断 { if (!vis[i]) ans[tot++] = i; for (int j = 0; j < tot&&(ll)ans[j] * i <= n; j++) /*用当前数i与i之前的素数相乘取得一个合数*/ { vis[ans[j] * i] = true; if (i%ans[j] == 0) break; } } } int main() { int n, m; cin >> n >> m; Getprime(sqrt(m)); //得到素数表 int num = m - n + 1; for (int i = 0; i < tot; i++) { for (ll j = (ans[i] + n - 1) / ans[i];;j++) /*(ans[i]+n-1)/ans[i]是求区间内的第一个数至少为i的几倍*/ { if (j == 1) continue; if (ans[i] * j > m) break; isprime[ans[i] * j - n] = true; //true则不是素数 } } int cnt = 0; for (int i = 0; i < num; i++) { if (!isprime[i]) cnt++; // 统计素数个数 } cout << cnt << endl; return 0; }
0.0分
6 人评分
Tom数 (C语言代码)浏览:2063 |
C语言程序设计教程(第三版)课后习题4.9 (C语言代码)浏览:711 |
C语言程序设计教程(第三版)课后习题11.3 (C语言代码)浏览:1061 |
C语言程序设计教程(第三版)课后习题7.2 (C语言代码)浏览:643 |
【绝对值排序】 (C语言代码)浏览:811 |
printf基础练习2 (C语言代码)浏览:316 |
C语言程序设计教程(第三版)课后习题1.5 (C++代码)浏览:1108 |
C语言程序设计教程(第三版)课后习题6.11 (C语言代码)浏览:2094 |
C语言程序设计教程(第三版)课后习题8.8 (C语言代码)浏览:665 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:877 |