为啥总超时?

回复帖子

@2570256177haha 2018-11-30 21:54 回复

include <bits/stdc++.h>

using namespace std;

int prime(int n) { if(n == 1) return 0; for (int i = 2; i < n; ++ i) if (n % i == 0) return 0; return 1; }

int main() { int m, n, t; scanf("%d",&t); while (t --) { scanf("%d%d",&m,&n); for (int i = m; i <= n; ++ i) { if(prime(i)) printf("%d\n",i); } printf("\n"); } return 0; }

@StudyingFather 2018-11-30 21:58 回复

因为你判断质数的复杂度是 $ O(n) $ 的啊,总时间复杂度就是 $ O(n^2) $ ,怎么可能AC

@LinkinPony 2018-12-01 07:56 回复
1 <= m <= n <= 1000000000

这个数据范围你这个做法肯定要T……

希望更丰富的展现?使用Markdown