Range nombres premiers C++

Question

J'ai une question, j'ai cette mission
Étant donné un entier positif X, nous voulons trouver l'intervalle le plus court [A, B] avec X contient, où aussi, A et B sont des nombres de nombres premiers .

Entrée La première ligne de l'entrée contient un nombre entier M (1 < = M < = 100). M lignes suivent, chacune avec un nombre X (1 < X < = 10^5).

sortie M lignes contenant A et B (1 < A = B < < = 10^6), B-A < = 10^4.

Exemple d'entrée

Exemple de sortie

Je l'ai fait, mais cela ne résout pas le problème. Comment puis-je imprimer les nombres premiers du nombre X? si je n'ai pas de gamme.

#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

Eh bien, vous pouvez utiliser la formule pour trouver les numéros sont les nombres premiers, puis comparer avec votre numéro de X, puis résumer 1 ou repos 1.

Answer 2

Si votre code est pour un juge en ligne (comme il semble être) alors vous devriez essayer quelque chose comme ceci:

#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; 
} 

il a ensuite construit un Sieve Eratosthène et juste effectue une recherche binaire à la recherche du plus bas premier qui est> = au nombre donné et regards (si ce n'est pas le plus petit) pour son prédécesseur. x sera contenue dans cet intervalle; et bien sûr il est facile de noter que c'est le plus petit intervalle possible.