范围素数 C++

Question

我有一个问题，我有这个作业
给定一个正整数X，我们要找到其中包含X的最短区间[A,B]，其中A和B也是质数。

输入输入的第一行包含一个整数 M (1 <= M <= 100)。接下来是 M 行，每行都有一个数字 X (1 < X <= 10^5).

输出 M 行包含 A 和 B (1 < A <= B <= 10^6), B-A <= 10^4.

样本输入

2

4

示例输出

2 2

3 5

我这样做了，但这并没有解决问题。如何打印 X 数的素数？如果我没有范围。

#include <iostream>
using namespace std;

int main()
{
    int n = 0, c = 0, c2 = 0, res = 0, nc = 0;
    cout << "Introduce el limite de numeros: ";
    cin >> n;
    for (c = 1; c <= n; c++) {
        for (c2 = 1; c2 <= n; c2++) {
            res = c % c2;
            if (res == 0) {
                nc = nc + 1;
            }
        }
        if (nc == 2) {
            cout << " " << c;
        }
        nc = 0;
    }
}

Answer 1

嗯，你可以用公式找出哪些数是质数，然后与你的X数比较，然后加1或取1。

Answer 2

如果您的代码适用于在线裁判（似乎是），那么您应该尝试这样的事情：

#include <bits/stdc++.h>

#define MAX 1000005
#define endl '\n'

using namespace std;

bool prime[MAX];
vector<int> primes;

void build() {
    memset(prime, true, sizeof prime);
    prime[0] = prime[1] = false;

    for (int i = 2; i < MAX; ++i) {
        if (!prime[i]) continue;
        primes.push_back(i);

        for (int j = i + i; j < MAX; j += i) {
            prime[j] = false;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    build();

    int m;
    cin >> m;

    while (m--) {
        int x;
        cin >> x;

        auto b = lower_bound(primes.begin(), primes.end(), x);
        auto a = b;

        if (*a != primes[0])
            a--;

        cout << *a << " " << *b << endl;
    }

    return 0;
}

它只是建立一个埃拉托色尼筛法，然后执行二分搜索寻找 >= 给定数字的最低素数，然后查找（如果它不是最小的）它的前身。 x 将包含在该间隔内；当然很容易注意到它是可能的最小间隔。

范围素数 C++

Range Primes C++

c++

primes

range