200101 - 函数——素数筛

时间限制

2000 毫秒

内存限制

128 MB

通过次数

22

提交次数

50

随着代码量的增加,把相同的计算过程单独编写一个函数有利于减少编写代码量、减少编写代码时的失误、更有利于对该部分代码进行调试。

求不大于n的素数中所有相差2的素数。

输入

一行,一个正整数,表示n

对于40%的数据:

1 \le n \le 1\cdot 10^4

对于80%的数据:

1 \le n \le 1\cdot 10^6

对于100%的数据:

1 \le n \le 1\cdot 10^7

输出

若干行,每行有单个空格分隔的按升序排列的两个正整数。

样例

输入

70

输出

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

提示

将生成素数筛过程写成一个函数:

const int MAXN=1e7;
bool flag[MAXN+1]={true,true};

void isp(){
	for( ){		//乘数1 
		if(flag[i]==false){
			for( ){	//乘数2 
				flag[ ]=true;
			}
		}
	}
}

输入输出数据量非常大时,c++为兼容c语言默认cin,cout等待stdio进行同步导致的时间损失非常明显,可以用ios::sync_with_stdio(false);来停止这种同步以节约时间,但这样使用会导致输入、输出方法不能混用。更简单的解决方法是当输入输出数据量非常大时使用scanf,printf输出,它不会等待cin,cout,也就不会有无谓的时间损失。