素数求解的多种境界

大佬教我写程序 lv.1

发布时间：2023-01-14 00:01:16 339

相关标签：

#每日美图分享#

素数求解的多种境界_#include

请输出100~200的所有素数

用试除法输出素数：

#include
int main()
{
  int num = 0;
  int count = 0;
  for (num = 100; num <= 200; num++)
  {
    int j;
    for (j = 2; j < num; j++)
    {
      if (num % j == 0)
        break;
    }
    if (j == num)
    {
      printf("%d ", j);
      count++;
    }
  }
  printf("\ncount=%d\n", count);
  return 0;
}

运行结果如下：

素数求解的多种境界_库函数_02

结果虽然正确但这个代码还是可以进行进一步的优化的：

利用开平方函数sqrt()。

如果一个数不是素数的话那么必定有 num=a*b,其中必定有一个数小于

sqrt(num),这是就可以这样整代码了：

#include
#include   //与sqrt对应的库函数
int mian()
{
  int num;                              //如果num不是的话素数，一定有num=a*b,其中一定有一个
  int count = 0;                        //数小于sqrt（num），也有一个数大于sqrt（num）
  for (num = 100; num <= 200; num++)
  {
    int j;
    for (j = 2; j <= sqrt(num); j++)    //sqrt是开平方函数
    {
      if (num % j == 0)
        break;
    }
    if (j > sqrt(num))
    {
      printf("%d ", j);
      count++;
    }    
  }
  printf("\ncount=%d\n", count);
  return 0;
}

这样计算量就少了一半多，运行效率也就更高了。

其实我们还知道偶数必然不是素数，则我们还可以通过跳过所有的偶数来进一步的减少计算量。如下：

#include
#include   
int mian()
{
  int num;                              
  int count = 0;                       
  for (num = 101; num <= 200; num+=2) 
  {
    int j;
    for (j = 2; j <= sqrt(num); j++)    
    {
      if (num % j == 0)
        break;
    }
    if (j > sqrt(num))
    {
      printf("%d ", j);
      count++;
    }    
  }
  printf("\ncount=%d\n", count);
  return 0;
}

100是偶数，可以直接跳过，令num=101，再通过循环使此后所有的 num+=2，这样就可以直接跳过偶数部分使计算量进一步减少。

感谢阅读

素数求解的多种境界_库函数_03

文章来源： https://blog.51cto.com/u_15815053/5748564

特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。