素数求解的多种境界

#每日美图分享#

请输出100~200的所有素数

用试除法输出素数：

#include<stdio.h>
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;
}

运行结果如下：

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

利用开平方函数sqrt()。

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

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

#include<stdio.h>
#include<math.h>   //与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<stdio.h>
#include<math.h>   
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，这样就可以直接跳过偶数部分使计算量进一步减少。

感谢阅读