（3种）编写一个程序，求1-n的素数个数。给出两种解法。对于相同的n，给出这两种解法的结果和求解时间，并用相关数据进行测试

ゞ浴缸里的玫瑰 2022-09-09 11:51 4阅读 0赞

**质数又称[素数][Link 1]。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为[合数][Link 2]（规定1既不是质数也不是合数）。**

**1不是素数，1不是素数。。。。**

## 方法一 ##

**单个数据输入，一次测试**

#include "stdio.h"
    #include "time.h"
    #include <math.h>
    clock_t start,stop;
    double duration;
    double f1(int n)
    {
    	int i,flag,j,sum=0;
    	for(i=3;i<=n;i++)//输入n=1的时候,判断条件i>n,不满足条件，不执行循环
    	{
    		flag=1;
    		for(j=2;j<i;j++)
    		{
    			if(i%j==0)
    				flag=0;
    		}
    		if(flag==1)sum++;
    	}
    	if(n>=2)sum+=1;
    	return sum;
    }
     
    double f2(int n)
    {
    	int i,j,flag,k,sum=0;
     
    	if(n>=2)sum+=1;
    	for(i=3;i<=n;i++)
    	{
    		flag=1;
    		k=sqrt(i);
    		for(j=2;j<=k;j++)
    		{
    			if(i%j==0)
    				{
    					flag=0;
    					break;
    			}
    		}
    		if(flag==1)sum++;
    	}
    	return sum;
     
    }
     
    int main()
    {
      int n;
      printf("输入一个正整数n:");
       scanf("%d",&n);
      start=clock();f1(n);
      stop=clock();
      duration=(double)(stop-start)/CLK_TCK;
      printf("ticks1=%f\n",(double)(stop-start));
      printf("duration1=%6.2e\n",duration);
      printf("1~%d的素数个数为%.0f\n",n,f1(n));
     
      start=clock();
      f2(n);
      stop=clock();
      duration=(double)(stop-start)/CLK_TCK;
      printf("ticks2=%f\n",(double)(stop-start));
      printf("duration2=%6.2e\n",duration);
      printf("1~%d的素数个数为%.0f",n,f2(n));
      return 1;
    }

**方法1和2**

# 方法二 #

方法3

double f1(int n)
    {
    	int i,flag,j,sum=0;
    	for(i=2;i<=n;i++)//i=2时候开运行到n，1不是素数
    		//输入n=1的时候,判断条件i>n,不满足条件，不执行循环
    	{
    		flag=1;
    		for(j=2;j<i;j++)
    		{
    			if(i%j==0)
    				flag=0;
    		}
    		if(flag==1)sum++;
    	}
    	return sum;
    }

**完整代码**

#include "stdio.h"
    #include "time.h"
    #include <math.h>
    clock_t start,stop;
    double duration;
    double f1(int n)
    {
    	int i,flag,j,sum=0;
    	for(i=2;i<=n;i++)//i=2时候开运行到n，1不是素数
    		//输入n=1的时候,判断条件i>n,不满足条件，不执行循环
    	{
    		flag=1;
    		for(j=2;j<i;j++)
    		{
    			if(i%j==0)
    				flag=0;
    		}
    		if(flag==1)sum++;
    	}
    	return sum;
    }
     
    double f2(int n)
    {
    	int i,j,flag,k,sum=0;
     
    	if(n>=2)sum+=1;
    	for(i=3;i<=n;i++)
    	{
    		flag=1;
    		k=sqrt(i);
    		for(j=2;j<=k;j++)
    		{
    			if(i%j==0)
    				{
    					flag=0;
    					break;
    			}
    		}
    		if(flag==1)sum++;
    	}
    	return sum;
     
    }
     
    int main()
    {
      int n;
      printf("输入一个正整数n:");
       scanf("%d",&n);
      start=clock();f1(n);
      stop=clock();
      duration=(double)(stop-start)/CLK_TCK;
      printf("ticks1=%f\n",(double)(stop-start));
      printf("duration1=%6.2e\n",duration);
      printf("1~%d的素数个数为%.0f\n",n,f1(n));
     
      start=clock();
      f2(n);
      stop=clock();
      duration=(double)(stop-start)/CLK_TCK;
      printf("ticks2=%f\n",(double)(stop-start));
      printf("duration2=%6.2e\n",duration);
      printf("1~%d的素数个数为%.0f",n,f2(n));
      return 1;
    }

**输出**

**运行时间与代码简洁性、电脑的性能、运行同时电脑里面运行多个软件数量等等有关。**

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA546L6ZmI6ZSL_size_15_color_FFFFFF_t_70_g_se_x_16][]

**输入**

1000

**k=sqrt(n); 数学原理**

例如：求100是否是素数，k=sqrt(100)=10，我们只需要找100能否被2到10整除，如果被整除，就判断其不是素数。我们找100能否被2到10整除，因为后面的都是重复的。 所以只需要判断0到开根号的数字就行。

#include <stdio.h>
    #include<math.h>
    int main() {
        int k=17,a;
        a=sqrt(k);
        printf("%d",a);
    
    }

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA546L6ZmI6ZSL_size_20_color_FFFFFF_t_70_g_se_x_16][]

# 方法三 #

**单个数据输入，多次测试**

#include "stdio.h"
    #include "time.h"
    #include <math.h>
    #define MAXK 1e7
    clock_t start,stop;
    double duration;
    int i;
    double f1(int n)
    {
    	int i,flag,j,sum=0;
    	for(i=2;i<=n;i++)//i=2时候开运行到n，1不是素数
    		//输入n=1的时候,判断条件i>n,不满足条件，不执行循环
    	{
    		flag=1;
    		for(j=2;j<i;j++)
    		{
    			if(i%j==0)
    				flag=0;
    		}
    		if(flag==1)sum++;
    	}
    	return sum;
    }
    
    double f2(int n)
    {
    	int i,j,flag,k,sum=0;
    
    	if(n>=2)sum+=1;
    	for(i=3;i<=n;i++)
    	{
    		flag=1;
    		k=sqrt(i);
    		for(j=2;j<=k;j++)
    		{
    			if(i%j==0)
    				{
    					flag=0;
    					break;
    			}
    		}
    		if(flag==1)sum++;
    	}
    	return sum;
    
    }
    
    int main()
    {
      int n;
      printf("输入一个正整数n:");
       scanf("%d",&n);
      start=clock();for(i=0;i<MAXK;i++) f1(n);
      stop=clock();
      duration=(double)(stop-start)/CLK_TCK/MAXK;
      printf("ticks1=%f\n",(double)(stop-start));
      printf("duration1=%6.2e\n",duration);
      printf("1~%d的素数个数为%.0f\n",n,f1(n));
    
      start=clock();
      for(i=0;i<MAXK;i++) f2(n);
      stop=clock();
      duration=(double)(stop-start)/CLK_TCK/MAXK;
      printf("ticks2=%f\n",(double)(stop-start));
      printf("duration2=%6.2e\n",duration);
      printf("1~%d的素数个数为%.0f",n,f2(n));
      return 1;
    }

**输出**

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA546L6ZmI6ZSL_size_16_color_FFFFFF_t_70_g_se_x_16][]

**输入**

100

[Link 1]: https://baike.baidu.com/item/%E7%B4%A0%E6%95%B0/115069
[Link 2]: https://baike.baidu.com/item/%E5%90%88%E6%95%B0/49186
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA546L6ZmI6ZSL_size_15_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/d6fbe15971444fb384c2e93fe07ea630.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA546L6ZmI6ZSL_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/cf9eeefb9c1d41ddabf26bbb7999937e.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA546L6ZmI6ZSL_size_16_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/0e32bc61cd434cda9fd1f51415b1e7d3.png