素数的判断方法

  相信学习C语言的小伙伴们，一定都遇到过用C语言去判断素数的题目。

今天和大家分享一些素数的判断方法，希望能够给刚入门的小伙伴们提供清晰的思路，废话不多说，开整。

举例：请列举出100~200之间的素数

1

什么是素数？

       素数——只能被1和本身整除的数字（除了数字1）

2

如何判断这些素数？

       假设 i 是我们要判断的数字

1、试除法——每拿到一个数的时候，如果 i 能被 2 ~ i-1 之间任一整数整除，可以说明是素数；

2.每拿到一个数据，只需要检测其：[2, i/2]区间内是否有元素可以被2i整除即可，可以说明i不是素数；

3.如果i能够被[2, sqrt(i)]之间的任意数据整除，则i不是素数——如果 m 能被 2 ~ m-1 之间任一整数整除，其二个因子必定有一个小于或等于sqrt(m)，另一个大于或等于 sqrt(m)；

方法一：

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
int main()
{
  int i, j, count = 0;
  for (i = 100; i <= 200; i++)//外层循环让其产生100~200之间的所有数字
  {
        //判断素数
    for (j = 2; j < i; j++)//试除阶段
    {
      if (i % j == 0) 
                break;
    }
    // 上述循环结束之后，如果j和i相等，说明[2, i）之间的所有数据都不能被i整除，则i为素数
    if (j == i)
    {
      count++;//记录素数的个数
      printf("%d ", i);
    }
  }
  printf("\ncount=%d\n", count);
  return 0;
}

上述方法虽然可行，但是我们不难发现，超过 i 一半的数据，不是 i 的倍数，进行了多次无效的循环试除；接下来看看优化后的代码二；

方法二：

既然多次无效的试除，我们可以将试除数据减少一半；只要拿到一个数字在试除的过程中，只要被[2, i/2]区间整除，就一定不是素数；

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
int main()
{
  int i, j, count = 0;
  for (i = 100; i <= 200; i++)//外层循环让其产生100~200之间的所有数字
  {
        //判断素数
    for (j = 2; j <= i / 2; j++)
    {
      if (i % j == 0)
        break;
    }
    if (j > i / 2)
    {
      count++;
      printf("%d ", i);
    }
  }
  printf("\ncount = %d\n", count);
  return 0;
}

方法二确实是比方法一减少循环试除的次数，但是细心一点还是会发现，当减少一半试除数据时，还是存在少部分没用的数据；再次优化，看代码三

方法三：

如果 m 能被 2 ~ m-1 之间任一整数整除，其二个因子必定有一个小于或等于sqrt(m)，另一个大于或等于 sqrt(m)；

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <math.h>
int main()
{
  int i, j;
  int count = 0;
  for (i = 100; i <= 200; i++)//外层循环让其产生100~200之间的所有数字
  {
        //判断素数
    for (j = 2; j <= sqrt(i); j++)
    {
      if (i % j == 0)
        break;
    }
    if (j > sqrt(i))
    {
            count++;
      printf("%d ", i);
    }
  }
  printf("\ncount = %d\n", count);
  return 0;
}

方法四：

继续对方法三优化，只要i不被[2, sqrt(i)]之间的任何数据整除，则i是素数，但是实际在操作时i不用从100逐渐递增到200，

因为出了2和3之外，不会有两个连续相邻的数据同时为素数

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <math.h>
int main()
{
  int i, j;
  int count = 0;
  for (i = 101; i <= 200; i += 2)//偶数不可能是素数
  {
        //判断素数
    for (j = 2; j <= sqrt(i); j++)
    {
      if (i % j == 0)
      {
        break;
      }
    }
    if (j > sqrt(i))
    {
      count++;
      printf("%d ", i);
    }
  }
  printf("\ncount = %d\n", count);
  return 0;
}

  素数的求解有多种方法，这里我们只简单地介绍两种算法，以及优化；如果大家有兴趣，我给大家推荐一篇文章叫《素数求解的n种境界》，大家可以下去自己去好好研究一下；拓宽自己的思路。

       总结一些小经验：编写代码现以实现为主，在此基础上去培养优化代码的思想，在以后的学习或者面试中会有很好的效果。