that_one_nigga_you_k

problema de bachgold

Jun 6th, 2024
123
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.05 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4.  
  5. using namespace std;
  6.  
  7. vector<int> notPrimeInRange(int L, int R) {
  8.   vector<int> not_primes;
  9.   for (int i = L; i <= R; i++) {
  10.     if (i == 1 || i == 0) {
  11.       continue;
  12.     }
  13.     bool is_prime = true;
  14.     for (int j = 2; j <= sqrt(i); ++j) {
  15.       if (i % j == 0) {
  16.         is_prime = false;
  17.         break;
  18.       }
  19.     }
  20.     if (!is_prime) {
  21.       not_primes.push_back(i);
  22.     }
  23.   }
  24.   return not_primes;
  25. }
  26.  
  27. int main() {
  28.  
  29.   int t;
  30.   cin >> t;
  31.  
  32.   vector<pair<int, pair<int, int>>> results; // guardar o numero impar e o par da resposta
  33.  
  34.   for (int i = 0; i < t; i++) {
  35.     int temp;
  36.     cin >> temp;
  37.  
  38.     if (temp % 2 == 0) {
  39.       results.push_back({temp, {-1, -1}}); // numeros pares só recebem isso
  40.       continue;
  41.     }
  42.  
  43.     vector<int> not_primes = notPrimeInRange(2, temp); // lista de numeros não primos no range
  44.  
  45.     int mindist = 1000000;
  46.     // declare found here
  47.     bool found = false;
  48.     pair<int, int> solution = {-1, -1};  // possível par
  49.  
  50.     for (int j = 0; j < not_primes.size(); j++) {
  51.  
  52.       for (int k = j + 1; k < not_primes.size(); k++) {
  53.  
  54.         int sum = not_primes[j] + not_primes[k];     //soma 2 a 2 dos numeros primos da lista
  55.         if (sum == temp) {
  56.  
  57.           int distancia = abs(not_primes[j] - not_primes[k]); // caso a soma for igual, checar a distancia
  58.          
  59.           if (distancia < mindist) {
  60.             mindist = distancia;
  61.             solution = {not_primes[j], not_primes[k]};
  62.             found = true; //achou a menor distancia, criou o par
  63.           }
  64.         }
  65.       }
  66.     }
  67.  
  68.     results.push_back({temp, solution}); // armazena o numero da entrada com o par de soluções
  69.   }
  70.  
  71.   // printa tudo de uma vez
  72.   for (auto result : results) {
  73.     int odd_num = result.first;
  74.     pair<int, int> pair = result.second;
  75.  
  76.     if (odd_num % 2 == 0) {
  77.       cout << "nenhum numero par." << endl;
  78.     }
  79.     else {
  80.       cout << odd_num << ": " << pair.first << " " << pair.second << endl;
  81.     }
  82.   }
  83.  
  84.   return 0;
  85. }
  86.  
Add Comment
Please, Sign In to add comment