【每日一题C】#79. 输出素数

系统管理员 2023-10-11 17:25 61阅读 0赞

![7d5844dea0864c0a81919be2e8545d0d.png][]

**初始代码：**

#include<stdio.h>
    #include<math.h>
    int main(){
    	int a,b;
    	scanf("%d%d",&a,&b);
    	if(a<2) a=2;
    	for(int i=a;i<=b;i++){
    	  int key=0,k=sqrt(i)+1;
    	  for(int j=2;j<k;j++)
    		if(i%j==0){
    			key=1;
    			break;
    		}
    	 if(key==0)
    	 printf("%d\n",i);
    	}
    	return 0;
    }

**也试过：**

#include<stdio.h>
    int main(){
    	int a,b;
    	scanf("%d%d",&a,&b);
    	if(a<2) a=2;
    	for(int i=a;i<=b;i++){
    	  int key=0;
    	  for(int j=2;j*j<=i;j++)
    		if(i%j==0){
    			key=1;
    			break;
    		}
    	 if(key==0)
    	 printf("%d\n",i);
    	}
    	return 0;
    }

**运行结果，显示超时：**

![8d65bd9b0bd2459395030410c3bb5a3f.png][]

**代码改善**：

#include<stdio.h>
    int main(){
    	int a,b,i;
    	int num[10000001]={0};
    	scanf("%d%d",&a,&b);
    	if(a<2) a=2;
    	for(i=2;i<=b;i++){
    		num[i]=1;
    	}
    	for(int j=2;j<i;j++){//剔除非质数
    		if(num[j]){
    			for(int k=2;k*j<=b;k++) //质数的倍数为非质数
    				num[k*j]=0;
    		}
    	}
    	for(int k=a;k<=b;k++){
    		if(num[k]) 
    			printf("%d\n",k);
    	}
    	return 0;
    }

**运行结果：**

![86b95743aa95405f865b4e83516c7143.png][]

**参考链接：**

1、[https://blog.csdn.net/Wansit/article/details/115439545][https_blog.csdn.net_Wansit_article_details_115439545]

2、

[https://fantianzuo.blog.csdn.net/article/details/81486370?spm=1001.2101.3001.6661.1&utm\_medium=distribute.pc\_relevant\_t0.none-task-blog-2%7Edefault%7ECTRLIST%7Edefault-1-81486370-blog-115439545.pc\_relevant\_default&depth\_1-utm\_source=distribute.pc\_relevant\_t0.none-task-blog-2%7Edefault%7ECTRLIST%7Edefault-1-81486370-blog-115439545.pc\_relevant\_default&utm\_relevant\_index=1][https_fantianzuo.blog.csdn.net_article_details_81486370_spm_1001.2101.3001.6661.1_utm_medium_distribute.pc_relevant_t0.none-task-blog-2_7Edefault_7ECTRLIST_7Edefault-1-81486370-blog-115439545.pc_relevant_default_depth_1-utm_source_distribute.pc_relevant_t0.none-task-blog-2_7Edefault_7ECTRLIST_7Edefault-1-81486370-blog-115439545.pc_relevant_default_utm_relevant_index_1]

[7d5844dea0864c0a81919be2e8545d0d.png]: https://img-blog.csdnimg.cn/7d5844dea0864c0a81919be2e8545d0d.png
[8d65bd9b0bd2459395030410c3bb5a3f.png]: https://img-blog.csdnimg.cn/8d65bd9b0bd2459395030410c3bb5a3f.png
[86b95743aa95405f865b4e83516c7143.png]: https://img-blog.csdnimg.cn/86b95743aa95405f865b4e83516c7143.png
[https_blog.csdn.net_Wansit_article_details_115439545]: https://blog.csdn.net/Wansit/article/details/115439545
[https_fantianzuo.blog.csdn.net_article_details_81486370_spm_1001.2101.3001.6661.1_utm_medium_distribute.pc_relevant_t0.none-task-blog-2_7Edefault_7ECTRLIST_7Edefault-1-81486370-blog-115439545.pc_relevant_default_depth_1-utm_source_distribute.pc_relevant_t0.none-task-blog-2_7Edefault_7ECTRLIST_7Edefault-1-81486370-blog-115439545.pc_relevant_default_utm_relevant_index_1]: https://fantianzuo.blog.csdn.net/article/details/81486370?spm=1001.2101.3001.6661.1&utm_medium=distribute.pc_relevant_t0.none-task-blog-2~default~CTRLIST~default-1-81486370-blog-115439545.pc_relevant_default&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-2~default~CTRLIST~default-1-81486370-blog-115439545.pc_relevant_default&utm_relevant_index=1