C++ P0003--孪生素数

Hello, 又来啦~首先公示投票结果：

​​​​​​​​​​​​​​​​$No.1$ 水仙花数+孪生素数+数位分离系列 6票
$No.2$ 数列求和+鸡兔同笼 5票

孪生素数

题目描述

在素数的大家庭中，大小之差为 $2$ 的两个素数称之为一对“孪生素数”，如 $3$ 和 $5$ 、 $17$ 和 $19$ 等。请你编程统计出不大于自然数 $n$ 的素数中，孪生素数的对数。

输入格式

一行一个正整数$n$，$1<=n<=1000$

输出格式

若干行，每行两个整数，之间用一个空格隔开，从小到大输出每一对孪生素数。

输入输出样例

输入数据

1

输出数据

3 5
5 7
11 13
17 19
29 31
41 43
59 61
71 73

其他：

时间限制 ：$1000ms$ 存储大小：$526kib$ 测试点：$5$个

题目描述完毕，请作答。

读完了题目，我们做一下分析：

首先回顾一下什么是素数：

只有$1$和它本身两个因数的数叫做素数。
例如： $5$ $11$

函数

定义一个布尔类型的函数，进行素数判断

温馨提示：bool类型的函数返回值只有$true$和$false$。

首先写出结束条件：如果这个数小于2的话，就不能为素数,

if(n == 1 || n == 0)  return false;

if(n < 2)  return false;

然后循环判断，从2开始，到n结束（优化方法在后）
只要对 $i$ 取模为0，也就是说，他除了$1$和它本身两个因数外，还有其他因数（这个数是合数）返回值就为$false$.

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

否则返回值为$true$。

main（）函数

读入整型变量n，插入循环，判断一下如果$i$和它的兄弟$i+2$都是素数的话，输出即可（不要忘记空格哟）

for(int i = 1; i <= n; i++){
	if(isPrime(i) && isPrime(i + 2)   cout << i << " " << i + 2;    //判断素数的函数···

是时候展示真正的技术了：

#include<bits/stdc++.h>
using namespace std;
bool isPrime(int n){
	if(n == 1 || n == 0)  return false;
	for(int i = 2; i <= n; i++){
		if(n % i == 0)  return false;
	}
	return true;
}
int main(){
	int n;
	cin >> n;
	for(int i = 2; i <= n; i++){
		if(isPrime(i) && isPrime(i + 2))  cout << i << " " << i + 2 << endl;
	}
	return 0;

}

提交之后，竟然是一个大大的$TLE$.

超时点在于：isPrime的for循环时间复杂度足足有
$O(n)$，而如果$n$是一个很大的数，算得太慢了！！应该怎么办呢？
这个地方可以替换成两种办法：

for(int i = 1; i <= sqrt(n); i++)

for(int i = 1; i * i <= n; i++)

换了这两种方法，就好多了。

最后，附AC代码：

#include<bits/stdc++.h>
using namespace std;
bool isPrime(int n){
	if(n == 1 || n == 0)  return false;
	for(int i = 2; i <= sqrt(n); i++){
		if(n % i == 0)  return false;
	}
	return true;
}
int main(){
	int n;
	cin >> n;
	for(int i = 2; i <= n; i++){
		if(isPrime(i) && isPrime(i + 2))  cout << i << " " << i + 2 << endl;
	}
	return 0;

}