枚举法判断素数

素数（质数）定义：除了1和本身以外，不能被其他数整除。
简单的说，只有两个因数的整数叫素数（质数）。
$1$只有$1$个因数，所以它不是质数。
$2$的因数有$1$和$2$，所以$2$是最小的素数（质数）
$4$的因数有:$1$、$2$、$4$。所以$4$不是素数（质数）。
从定义出发，我们判断一个数是否为素数。

cin>>n;
sxt = 0; //记号，用于判断有没有找到因数
for(int i = 2; i < n; i++){
	if(n%i==0){  //找到一个因数
		sxt = 1;
		break;
	}
}

$n$如果上亿，则要时间超限。
我们可以两个两个找的思路来判断素数，只要找完第$1$个因数，就可以判断找完了因数。

cin>>n;
sxt = 0;  //记号，用于判断有没有找到因数
for(int i = 2; i <= sqrt(n); i++){
     if(n%i==0){
	     sxt = 1;
	     break;
     }
}

一般情况下，我们把素数判断写成函数，方便使用。

#include<bits/stdc++.h>
using namespace std;
bool ss(int m)
{
	if(m < 2) return 0;
	for(int i = 2; i <= sqrt(m); i++){
		if(m % i == 0) return 0;
	}
	return 1;
}

int main()
{
	for(int i = 1; i <= 100; i++){
		if(ss(i)==1) cout<<i<<endl;
	}
    return 0;
}

1228-哥德巴赫猜想(easy)