PAT Basic 1013. 数素数
1. 题目描述:
令 \(P_i\) 表示第 \(i\) 个素数。现任给两个正整数 \(M≤N≤10^4\),请输出 \(P_M\) 到 \(P_N\) 的所有素数。
2. 输入格式:
输入在一行中给出 \(M\) 和 \(N\),其间以空格分隔。
3. 输出格式:
输出从 \(P_M\) 到 \(P_N\) 的所有素数,每 10 个数字占 1 行,其间以空格分隔,但行末不得有多余空格。
4. 输入样例:
5 27
5. 输出样例:
11 13 17 19 23 29 31 37 41 43
47 53 59 61 67 71 73 79 83 89
97 101 103
6. 性能要求:
Code Size Limit
16 KB
Time Limit
200 ms
Memory Limit
64 MB
思路:
构造一个判断素数的子函数,然后从头依次遍历素数即可,思路比较直接,但确实能满足时间要求。。。
My Code:
#include <stdio.h>
int isPrime(int num);
int main(void)
{
int tempM = 0, tempN = 0;
int flag = 0, numNow = 2;
scanf("%d%d", &tempM, &tempN); // to store M and N
for(flag = 0; flag < tempM; numNow++)
{
if(isPrime(numNow)) flag++;
}
numNow--; // back to Mth prime number
flag = 0;
while(flag < tempN-tempM+1)
{
if(isPrime(numNow))
{
if(flag % 10 == 0)
printf("%d", numNow);
else if(flag % 10 == 9)
printf(" %d\n", numNow);
else
printf(" %d", numNow);
flag++;
}
numNow++;
}
return 0;
}
// judge Prime number function
// 1: isPrime | 0: notPrime
int isPrime(int num)
{
for(int i = 2; i*i <= num; i++)
{
if(num % i == 0)
return 0;
}
return 1;
}
标签:10,PAT,int,素数,numNow,flag,Basic,isPrime,1013
From: https://www.cnblogs.com/tacticKing/p/17189900.html