判断素数

注：
在C中定义数组，函数内部的数组大小最大长度在1e5(不准确值，但是不会超过或等于 1e6)， 函数外部的数组大小最大长度在1e8左右(不会超过或等于 1e9)
（还有一个小知识点： 1e5 是 double 类型）
这里我分为两种情况：

• 1、数据量小于 1e5 (用筛选法 素数打表)
  下面这个博客写的很详细 分析得也很好：https://blog.csdn.net/gtuif/article/details/73732070
  欧拉筛法：

#include <stdio.h>
#include <string.h>
#define maxn 100005

int prime[maxn];
bool visit[maxn];
void getPrime(){
	memset(prime, 0, sizeof prime);
	memset(visit, true, sizeof visit);
	int k = 0;
	for(int i =0; i < maxn; i++){
		if(visit[i]){//为素数
			prime[k++]= i; 
		}
		for(int j = 0; j < k; j++){
			if(i*prime[j] > maxn) break;
			visit[i*prime[j]] = false;
			if(i % prime[j] == 0){
				break;
			}
		}
	}
}
int main(){
	getPrime(); 
	return 0;
}

对于第4列及后面的列里面出现的数字所出现的次数都是一次
i = 3 6 9
i = 4 8
i = 5 10
i = 6 12
i = 8 16
i = 9 18 27
i = 10 20
i = 12 24
i = 13 26 39 65 91 143
i = 14 28
i = 15 30 45

• 2、数据量小于 1e9
  相应题目：http://nyoj.top/problem/1437
  博客：https://blog.csdn.net/hans_xing/article/details/81041233

#include <stdio.h>
#include <math.h>
typedef long long ll;

bool isPrime(ll n){
	if(n == 1) return false;
	if(n==2 || n==3) return true;
	if(n%6 != 1 && n%6 != 5) return false;
	ll ans = sqrt(n);
	for(int i = 5; i <= ans; i+=6){
		if(n%i == 0 || n%(i+2) == 0) return false;
	}
	return true;
} 
int main(){
	ll n;
	while(~scanf("%lld", &n)){
		printf(isPrime(n) ? "是素数\n" : "不是素数\n");	
	}
	return 0;
}