境界再再+1 sqrt（i）🍊

实际上这个才是我们最应该掌握的方法，我们来看看如何优化。

>我们现在是从2~ √i 去试除，
举个例子如果一个数不是素数那么它一定是可以进行分解的，
分解成两个因子相乘的情况，
我们看上面12的因子，这么多因子实际上我们只需要判断√12前面的就行，
为什么呢？
如果√12前面没有一个因子能被整除，那么后面（√12后面）就没有一个因子能够被整除，
因为因子都是要相乘的，比如2和6，我都已经判断2能够被整除，那我还需要判断后面的6吗？如果不是很肯定对不对就多试试多分解几组。
我们来看代码吧。

#define  _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<math.h>
int main()
{
  int i = 0;
  int count1 = 0;//用以统计素数的个数
  int count2 = 0;//用以计算要试除多少次
  printf("2是素数 ");
  for (i = 3; i <= 150; i+=2)
  {
    int j = 0;
    for (j = 2; j <=sqrt(i); j++)
    {
      count2++;
      if (i % j == 0)
      {
        break;
      }
    }
    if ( j > sqrt(i) )
    {
      printf("%d是素数 ", i);
      count1++;
    }
  }
  printf("\n素数的个数为%d", count1);
  printf("\n试除的次数为%d", count2);
  return 0;
}

这个代码需要在第二个for循环改变第二个判断条件，让j<=sqrt(i),并且还要在最后if的判断条件变为 j >sqrt (i) ,因为已经解释很多次这里我就不解释了。我们来看效率

我们最后试除的次数变成仅仅只要343了，还记得我们最开始有多少吗？我记得是2414，现在我们感受到优化的快乐了吗？

总得来说试除法的思路都差不多。还是比较好理解的。我们来看看另一种方法也是我们真正能够与别人方法不一样的一种，希望大家能够掌握。

筛选法🍊

我们筛选法还有一个名字叫，埃拉托斯特尼算法。这个名字念起来非常拗口，这是一个古希腊的名字。此人是个古希腊的大牛，是大名鼎鼎的阿基米德的好友。他虽然没有阿基米德那么出名，但是也非常非常厉害，在数学、天文学、地理学、文学、历史学等多个领域都有建树。并且还自创方法测量了地球直径、地月距离、地日距离以及黄赤交角等诸多数值。要知道他生活的年代是两千五百多年前，那时候中国还是春秋战国时期，可以想见此人有多厉害。

思路

埃式筛法的思路非常简单，就是用已经筛选出来的素数去过滤所有能够被它整除的数。这些素数就像是筛子一样去过滤自然数，最后被筛剩下的数自然就是不能被前面素数整除的数，根据素数的定义，这些剩下的数也是素数。

如果还不懂我就来解释一下，假如我们要筛选出120以内所以的素数，那我们就可以从2这个第一个素数开始，我们把因子中含有2的，也就是偶数全部筛选掉，简单理解就是去掉。然后我们从2的下一个素数开始，2的下一个素数是3，那么我们就把因子中有3的全部筛选掉，3的下一个素数又是谁？是5，然后我们再重复上面的过程，5 之后的素数是7，然后再再循环上面的过程。当7的循环结束之后我们就可以去找还有哪些数没有被筛掉，没有被筛掉的数就是素数。

给大家一个经典的gif加强理解

接下来我们看代码

#define  _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<math.h>
int main()
{
  int i = 0;
  int count1 = 0;//用以统计素数的个数
  int count2 = 0;//用以计算要筛掉多少次
  int arr[151] = { 0 };//创建数组
  for (i = 2; i <= 150; i++)//初始化
  {
    arr[i] = 1;
  }
  for (i = 2; i <= 150; i++)//用下标代表数字
  {
    if (arr[i]) //是1才进入if
    {
      int j = 0;
      printf("%d ", i);//打印素数
      count1++;
      for (j = i+i; j <= 150; j += i)//把素数的倍数都赋为0；
      {                    //让下一个进入if的必定是素数     {
        arr[j] = 0;
        count2++;     //
      }
    }
  }
  printf("\n素数的个数为%d", count1);
  printf("\n试除的次数为%d", count2);
  return 0;
}

*简单说一下代码思路，我是建立一个数组，

把应该筛掉的数全部变为0，

让被筛掉的那些数作为数组的下标。

比如我从2开始筛，2之后的偶数就无法打印，然后就是3，然后就是5，然后就是7，然后就是11。*大家知道为什么这里要筛11吗？因为我们要筛的最大值为150，而√150的值是12.2。12.2是大于11的所以我们这次要多筛11（这里我不是很确定，大家看看就好，影响不大）

让大家看看筛选法的效率是多么的惊人。

234次就直接能够把2 ~150 的素数全部筛选完。

筛选法优化🍊

我们讲解一下优化的思路，

其实我上面筛选法的代码还是可以优化的，

为什么呢？

在最后我们是把有关的倍数数组全部赋值为0，

>但是假如这个数是12呢？
12我们在以2为筛选倍数的时候赋为0，
但是在以3位筛选倍数的时候又赋值为0。

这样就重复了。大家能明白我的意思吗

？如果不明白大家可以再看看那个gif相信大家可以发现这个道理。

埃拉托斯特尼也注意到过这一点。

当 i=2 时，我们只需从 2 * 2 = 4 开始筛2的倍数；当 i=3 时，其实我们只需从3 * 3 = 9开始筛3的倍数 当 i = 5 时，我们应该从25开始筛。

for (j = i+i; j <= 150; j += i)

当i = 3时，优化前的代码我们是从6开始筛，但是6其实已经被作为2的倍数筛过一次，而3+3+3，也就是9还没有被筛。
当i = 5时，优化前的代码我们是从10开始筛，但是10也被作为2的倍数筛走，那15呢？对是的，被作为3的倍数筛走，那么20？ 也不行只有25才行。

那么我们就发现了规律，我们应该从该素数的平方开始筛。

最后再来看代码

#define  _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<math.h>
int main()
{
  int i = 0;
  int count1 = 0;//用以统计素数的个数
  int count2 = 0;//用以计算要筛掉多少次
  int arr[151] = { 0 };//创建数组
  for (i = 2; i <= 150; i++)//初始化
  {
    arr[i] = 1;
  }
  for (i = 2; i <= 150; i++)//用下标代表数字
  {
    if (arr[i]) //是1才进入if
    {
      int j = 0;
      printf("%d ", i);//打印素数
      count1++;
      for (j = i*i; j <= 150; j += i)//把素数的倍数都赋为0；
      {                              //让下一个进入if的必定是素数     {
        arr[j] = 0;
        count2++;     //
      }
    }
  }
  printf("\n素数的个数为%d", count1);
  printf("\n试除的次数为%d", count2);
  return 0;
}

最后也是最激动人心的时刻，咱们来看看效率

芜湖！！！166！！！，看到这里的你被埃式筛法震惊了吗？说真的我被震惊了。

总结🍊

首先很感谢能看到这里的小伙伴，真的很感谢有人能看我的博客，说真的我在写这篇博客的时候真的很用心，我要感谢链接: 圣喵学长的博客，以及一些知乎上面的大佬的文章提供给我的参考。

通过这篇博客希望大家能够明白算法的奥秘，如果有兴趣的同学可以去知乎上寻找更有难度的方法如欧拉筛等等。这篇博客到这里就结束了。

各位看官姥爷如果这篇博客有帮助到你，麻烦你动动小手点点赞吧，只需要一个赞就能让我高兴很久，^ _ ^.如果有任何错误有麻烦在评论区指出。