求素数以及优化

求素数是面试中最常见的问题。一下给出了求素数的普通解法和优化解法。
摘抄于：
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