【PAT乙级】数素数
- 2019 年 11 月 8 日
- 笔记
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_42449444/article/details/84866104
题目描述:
令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
解题思路:
首先自定义一个isPrime(int n)的函数用来判断一个数是否为素数,然后再主函数中用count来记录素数的个数,当count在[m,n]这个范围内时,对这个素数进行输出,需要注意的是行末没有多余空格,每10个素数换一行。
AC代码:
#include <bits/stdc++.h> using namespace std; bool isPrime(int n) { if(n<=1) { return false; } for(int i=2;i<=sqrt(n);i++) { if(n%i==0) { return false; } } return true; } int main() { int m,n; cin >> m >> n; int a[10001]; for(int i=1, j=1;j<=10000;i++) { if(isPrime(i)) { a[j++] = i; } } int count = 0; for (int i = m; i <= n; i++) { if(count == 0) { cout << a[i]; } else { cout << " " << a[i]; } count++; if(count%10 == 0) { count = 0; cout << endl; } } return 0; }