求素数是面试中最常见的问题。一下给出了求素数的普通解法和优化解法。
摘抄于：
https://www.cnblogs.com/grubbyskyer/p/3852421.html
普通解法一
原理：由素数的定义，除1和它自身外不存在其他因数
#include<stdio.h>
int main()
{
int i,n;
while(scanf("%d",&n)==1)
{ for(i=2;i<n;i++)
if(n%i==0) break;
if(i==n) printf("YES\n");
else printf("NO\n");
}
}
普通解法二
原理： 由n缩小到sqrt(n),判断从1到sqrt（n）之间是否存在n的其他因数。
#include<stdio.h>
#include<math.h>
int main()
{ int i,n,x;
while(scanf("%d",&n)==1)
{ x=(int)sqrt(n);
for(i=2;i<=x;i++)
if(n%i==0) break;
if(i>x) printf("YES\n");
else printf("NO\n");
}
}
普通筛选法（埃拉托斯特尼筛法）
基本思想：素数的倍数一定不是素数
实现方法：用一个长度为N+1的数组保存信息（0表示素数，1表示非素数），先假设所有的数都是素数（初始化为0），从第一个素数2开始，把2的倍数都标记为非素数（置为1），一直到大于N；然后进行下一趟，找到2后面的下一个素数3，进行同样的处理，直到最后，数组中依然为0的数即为素数。
说明：整数1特殊处理即可。
以N=20举例如下图：
N = 20
最后数组里还是0的就是素数
memset(check, 0, sizeof(check));
int tot = 0;
for (int i = 2; i <= n; ++i)
{
if (!check[i])
{
prime[tot++] = i;
}
for (int j = i+i; j <= n; j += i)
{
check[j] = 1;
}
}
线性筛法--欧拉筛法
#include<cstdio>
#include<cstring>
#define MAXN 100005
#define MAXL 1299710
int prime[MAXN];
int check[MAXL];
int tot = 0;
memset(check, 0, sizeof(check));
for (int i = 2; i < MAXL; ++i)
{
if (!check[i])
{
prime[tot++] = i;
}
for (int j = 0; j < tot; ++j)
{
if (i * prime[j] > MAXL)
{
break;
}
check[i*prime[j]] = 1;
if (i % prime[j] == 0)
{
break;
}
}
}
它们保证每个合数只会被它的最小质因数筛去，因此每个数只会被标记一次，所以时间复杂度是O(n)
N = 20
