PAT乙级 1013.数素数

111

10个一行输出n~m的素数

题目


原题链接

令P~i~表示第i个素数。现任给两个正整数\(M<=N<=10^4\),请输出P~M~到P~N~的所有素数。

输入格式:
输入在一行中给出M和N,其间以空格分隔。

输出格式:
输出从P~M~到P~N~的所有素数,每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




解析


直接1007的代码即可。

代码


C++解法


#include <cstring>
#include <iostream>
using namespace std;

const int maxn = 110005;

int prime[maxn];
bool isPrime[maxn];
int pos;

void listPrime(int maxNum) {
    memset(isPrime, true, sizeof(isPrime));
    isPrime[0] = isPrime[1] = false;
    pos = 0;
    for (int i = 2; i <= maxNum; ++i) {
        if (isPrime[i])
            prime[pos++] = i;
        for (int j = 0; j < pos && i * prime[j] <= maxNum; ++j) {
            isPrime[i * prime[j]] = false;
            if (!(i % prime[j]))
                break;
        }
    }
}

int ans[maxn];
int main() {
    cin.tie(0);
    cin.sync_with_stdio(false);

    int n, m;
    cin >> n >> m;
    listPrime(110000);

    bool isFirst = true;
    int cnt = 0;
    for (int i = n; i <= m; ++i) {
        if (cnt == 10) {
            cout << endl;
            cnt = 0;
            isFirst = true;
        }
        if (isFirst)
            isFirst = false;
        else
            cout << " ";
        cnt++;
        cout << prime[i - 1];
    }
    cout << endl;
    return 0;
}


Python解法


def listPrime(MAX):
    isPrime = [True for i in range(MAX + 1)]
    isPrime[0] = isPrime[1] = False
    prime = []
    for i in range(2, MAX + 1):
        if isPrime[i]:
            prime.append(i)
        for j in range(0, len(prime)):
            if i * prime[j] > MAX:
                break
            isPrime[i * prime[j]] = False
            if not (i % prime[j]):
                break
    return prime


prime = listPrime(110000)
(n, m) = [int(i)for i in input().split(" ")]

isFirst = True
cnt = 0
for i in range(n, m + 1):
    if cnt == 10:
        print("\n", end="")
        cnt = 0
        isFirst = True
    if isFirst:
        isFirst = False
    else:
        print(" ", end="")
    cnt += 1
    print(prime[i - 1], end="")
print("\n", end="")



Java解法


import java.lang.reflect.Array;
import java.util.*;

class Main {

    public static final int maxn = 110005;
    public static int[] prime = new int[maxn];
    public static boolean[] isPrime = new boolean[maxn];
    public static int pos;

    public static void listPrime(int maxNum) {
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        pos = 0;

        for (int i = 2; i <= maxNum; ++i) {
            if (isPrime[i])
                prime[pos++] = i;
            for (int j = 0; j < pos && i * prime[j] <= maxNum; ++j) {
                isPrime[i * prime[j]] = false;
                if (i % prime[j] == 0)
                    break;
            }
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();

        listPrime(110000);
        int cnt = 0;
        boolean isFirst = true;
        for (int i = n; i <= m; ++i) {
            if (cnt == 10) {
                cnt = 0;
                System.out.print("\n");
                isFirst = true;
            }
            if (isFirst)
                isFirst = false;
            else
                System.out.print(" ");
            cnt++;
            System.out.print(prime[i-1]);
        }
        System.out.print("\n");
        in.close();
    }
}
发布评论
  • 点击查看/关闭被识别为广告的评论