快速求质数 题解

日常竞赛测试讨论
1

题目链接：problem

题意：

输入正整数 N , M 输出 N , M 之间的所有质数。

看看这题的数据，哇

约定
(N<=M<2^{31},M−N<=20000)

看来筛素数是不行了,只能判断素数 ( 用 is_ prime )

但是这题会卡常 ！！！

1、开 long long , 而且要开 define int long long ， int main 可删 int 或改成 signed main
2、用cin、cout要在前面加

ios::sync_with_stdio (false) ;
cin.tie (NULL) ; cout.tie (NULL) ;

3、(选) 最后开 return 0;
4、开 O_2 、 O_3 优化

只能想到这么多了，这题真的很恶心

放出AC代码，因为有些自己思考一模一样都会 TLE ！！！

#include <bits/stdc++.h>
#define int long long
#define LL (long long)
#pragma G++ optimize (2)
#pragma G++ optimize (3)
using namespace std ;
int n , m ;
bool is_prime (int x) {
	if (x < 2)  return 0 ;
	for (int i = 2 ; i <= sqrt (x) ; i ++)
		if (x % i == 0)  return 0 ;
	return 1 ;
}
main () {
	ios::sync_with_stdio (false) ;
	cin.tie (NULL) ; cout.tie (NULL) ;
	cin >> n >> m ;
	for (int i = n ; i <= m ; i ++)
		if (is_prime (i))  cout << i << " " ;
	return 0 ;
}

编译结果：

恭喜，你通过了这道题
compiled successfully
time: 160ms, memory: 3516kb, score: 100, status: Accepted
> test 1: time: 0ms, memory: 3468kb, points: 20, status: Accepted
> test 2: time: 1ms, memory: 3516kb, points: 20, status: Accepted
> test 3: time: 11ms, memory: 3468kb, points: 20, status: Accepted
> test 4: time: 147ms, memory: 3392kb, points: 20, status: Accepted
> test 5: time: 1ms, memory: 3396kb, points: 20, status: Accepted
1 个赞