C++中关于质数的判定方法_c++判断质数

C++中关于质数的判定方法

1、试除法
顾名思义，对于要判断的数n，我们枚举[2,n-1]里的所有整数，看看能不能整除n，若[2,n-1]里的所有整数中不存在一个数能整除n，那么n为质数，反之为复数。
优化
实际上我们只需枚举[2，√n]之间的整数试除n就行了。
命题：对于合数n，在[2，√n]之间的整数中必定存在一个数能整除n。
证明：假设[2，√n]之间的整数中不存在一个数能整除n。
由于n为合数，则[√n+1，n]之间的整数中必定存在一个数能整除n。
设m属于[√n+1，n]且能整除n
则m/n也能整除n
由于m/n属于[2, √n]且能整除n，与假设不符合。
所以若n为合数，[2，√n]之间的整数中必定存在一个数能整除n。
证毕。

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;

int main(){
	int n;
	bool flag;
	int i,j,temp;
	scanf("%d",&n);
	for(i=2;i<=n;i++){
		temp=sqrt(i);
		flag=true;
		for(j=2;j<=temp;j++){
			if(!(i%j)){
				flag=false;
				break;
			}
		}
		if(flag){
			printf("%d ",i);
		}
				
	}

	
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

2、Era