PAT乙级(Basic Level)真题数素数（素数筛法）

青旅半醒 2024-02-17 21:09 57阅读 0赞

#### **题目描述** ####

令Pi表示第i个素数。现任给两个正整数M <= N <= 10000，请输出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

分析：素数筛法打表

AC代码：

#include<cstdio>
    #include<cstring>
    #include<cmath>
    using namespace std;
    const int maxn=1e6;
    int a[maxn];
    int vis[maxn];
    void table(){
    	memset(vis,0,sizeof(vis));
    	
    	for(int i=2;i<=sqrt(maxn);i++){
    		if(!vis[i]){
    			for(int j=i*i;j<maxn;j+=i)
    			vis[j]=1;
    		}
    	}
    	
    	int j=1;
    	for(int i=2;i<maxn;i++)
    	 if(!vis[i])
    	  a[j++]=i;
    }
    int main(){
    	int m,n;
    	table();
    	while(scanf("%d%d",&m,&n)==2){
    		int cnt=0;
    		for(int i=m;i<=n;i++){
    			if(cnt%10==0){
    				if(cnt==0)printf("%d",a[i]);
    				else printf("\n%d",a[i]);
    		    }
    		    else printf(" %d",a[i]);
    		    cnt++; 
    	   }
    	} 
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，57人围观）

还没有评论，来说两句吧...

相关阅读

相关 PAT乙级(Basic Level)真题数素数（素数筛法）

题目描述令Pi表示第i个素数。现任给两个正整数M <= N <= 10000，请输出PM到PN的所有素数。输入描述: 输入在一行中给

青旅半醒/ 2024年02月17日 21:09/ 0 赞/ 58 阅读

相关 POJ 2689【筛法求素数+区间筛素数】

Discription The branch of mathematics called number theory is about properties of numb

桃扇骨/ 2023年07月04日 06:15/ 0 赞/ 22 阅读

相关【JAVA】1007 素数对猜想 (20分) PAT乙级 PAT (Basic Level) Practice (中文)

你是最棒的前言题目：1007 素数对猜想 (20分) 要点：代码前言 > 学得越多，不会得越多 > 种一颗树的最佳时间是十年前

我会带着你远行/ 2022年12月24日 09:57/ 0 赞/ 180 阅读

相关素数筛法略

用筛法求素数的基本原理，是把从1开始的某一范围内的正整数从小到大顺序排列，逐步筛掉非素数留下素数。用筛法求素数的基本思想是：把从1开始的、某一范围内的正整数从小到大顺序排列

墨蓝/ 2022年10月25日 01:23/ 0 赞/ 181 阅读

相关 PAT乙级(Basic Level)真题 1003数素数 Java

题目描述令Pi表示第i个素数。现任给两个正整数M <= N <= 10000，请输出PM到PN的所有素数。输入描述: 输入在一行中给出M

深藏阁楼爱情的钟/ 2022年05月16日 06:28/ 0 赞/ 190 阅读

相关 PAT乙级(Basic Level)真题 1002.数字分类 java

题目描述给定一系列正整数，请按要求对数字进行分类，并输出以下5个数字： A1 = 能被5整除的数字中所有偶数的和；

雨点打透心脏的1/2处/ 2022年05月16日 06:21/ 0 赞/ 183 阅读

相关 PAT乙级(Basic Level)真题锤子剪刀布 java

题目描述大家应该都会玩“锤子剪刀布”的游戏：现给出两人的交锋记录，请统计双方的胜、平、负次数，并且给出双方分别出什么手势的胜算最大。

小灰灰/ 2022年05月15日 03:16/ 0 赞/ 166 阅读

相关筛法求素数

用筛法求素数的基本思想是：把从1开始的、某一范围内的正整数从小到大顺序排列， 1不是素数，首先把它筛掉。剩下的数中选择最小的数是素数，然后去掉它的倍数。依次类推，直到筛子为空时

我不是女神ヾ/ 2022年05月12日 14:42/ 0 赞/ 263 阅读

相关素数筛法

//暴力枚举素数筛法 o(n 根号n) for(int i=2;i<=n;i++){ bool g=0; for(int j=2;jj<

╰+哭是因爲堅強的太久メ/ 2022年04月04日 10:54/ 0 赞/ 259 阅读

相关 PAT~乙级~1013 数素数 ~C++

题目描述：令 Pi 表示第 i 个素数。现任给两个正整数 M≤N≤104，请输出 PM 到 PN 的所有素数。输入格式：输入在一行中给出

约定不等于承诺〃/ 2021年12月17日 13:15/ 0 赞/ 294 阅读