CHAPTER_5  数学问题入门

5.4.1素数的判断

素数又叫质数，是指除了1和本身之外，不能被其他数整除的一类数。反之称为合数。

注意：1既不是素数也不是合数。

题目：

给定一个整数，请判断它是否为素数。

思路：

判断n是否为素数最直接的思路为，枚举2~n-1依次判断它们是否能被n整除。这样做的时间复杂度为O(n)。

实际上经过数学推导，我们只需枚举  ~  中的每个数，依次判断它们是否能被n整除即可。这样时间复杂度优化为O( )。

参考代码：

bool isPrime(int n) {
	if(n<=1)
		return false;
	int sqr=(int)sqrt(1.0*n);
	for(int i=2;i<=sqr;i++) {
		if(n%2==0)
			return false;
	}
	return true;
} 

 

5.4.2素数表的获取

通过上面的学习，我们已能判断单个数是否为素数。那么我们由此可以打印1~n范围内的素数表，即枚举1~n中的每个数，依次执行isPrime()函数，如果返回true则为素数，将其存入数组中。

上述方法的时间复杂度为O()，这个复杂度对n<=10^5是没有问题的。对于更大的数据，我们有更优秀的“埃氏筛法”和“欧拉筛法”，这里不再赘述，有兴趣可以百度。

题目：

令Pi表示第i个素数，现任意给两个正整数m<=n<=10^4，请输出Pm到Pn的所有素数。

输入格式：

在一行中输入m和n，中间用空格分隔

输出格式： 

输出从Pm~Pn的所有素数，每10个数字占一行，中间以空格分隔，行末不能有多余空格 

输入样例： 

5 27

输出样例： 

11 13 17 19 23 29 31 37 41 43

47 53 59 61 67 71 73 79 83 89

97 101 103

参考代码： 

#include<iostream>
#include<cmath>

using namespace std;

const int maxn=1000001;
int p[maxn]={0},count=0;


bool isPrime(int n) {
	if(n<=1)
		return false;
	int sqr=(int)sqrt(1.0*n);
	for(int i=2;i<=sqr;i++) {
		if(n%i==0)
			return false;
	}
	return true;
}

void findPrime() {
	for(int i=2;i<maxn;i++) {
		if(isPrime(i))
			p[++count]=i;
	}
}

int main() {
	int m,n;
	cin>>m>>n;
	findPrime();
	for(int i=m;i<=n;i++) {
		if(p[i]){
			if((i-m)%10==9)
				cout<<p[i]<<endl;
			else
				cout<<p[i]<<' ';
		}
	}
	return 0;
}