【PTA乙级】1013.数素数
2021/11/5 23:13:54
本文主要是介绍【PTA乙级】1013.数素数,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述:
令Pi表示第 i 个素数。现任给两个正整数 M≤N≤10^4,请输出PM到PN的所有素数。
输入格式
输入在一行中给出 M 和 N,其间以空格分隔。
输出格式
输出从PM到PN的所有素数,每 10 个数字占 1 行,其间以空格分隔,但行末不得有多余空格。
样例输入
5 27
样例输出
11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103
标签:素数筛法
解题思路:
从2开始筛开素数的倍数直到题目给出的范围为止,得到一个素数表,最后根据题目要求输出即可
AC代码:
#include<cstdio> using namespace std; const int max=1001000; //尽量开大些 int prime[100100]; void find_prime(int m){ int pnum=0; bool p[max]={0}; //先模拟所有的数是素数再筛开素数的倍数,设为true,剩余的数就是素数 for(int i=2;pnum<m;i++){ if(p[i]==false){ prime[pnum++]=i; //存素数 for(int j=i+i;j<max;j+=i){ p[j]=true; } } } } int main(){ int n,m,count=0; scanf("%d %d",&n,&m); find_prime(m); for(int i=n-1;i<m;i++){ //素数表从0开始 printf("%d",prime[i]); count++; if(count%10!=0&&i<m-1){ //确保输出每第十个数后面没有空格且最后一个数后面没有空格 printf(" "); } else printf("\n"); //这样每十个数就换行且输出最后一个数后换行 } return 0; }
这篇关于【PTA乙级】1013.数素数的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现