ulvis.paste.net

preprocess
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5. const int mx = 3*1000*1000 + 5;
  6. int max_factor[mx], del[mx];
  7. vector<int> pr;
  8.  
  9. void preprocess() {
  10.         for (int i=0; i<mx; i++) max_factor[i] = i;
  11.         for (int i=2; i<mx; i++) {
  12.                 if (max_factor[i]==i)  {
  13.                         pr.push_back(i);
  14.                         for (int j=2*i; j<mx; j+=i) {
  15.                                 max_factor[j] = min(max_factor[j], i);
  16.                         }
  17.                 } else {
  18.                         max_factor[i] = i / max_factor[i];
  19.                 }
  20.         }
  21. }
  22.  
  23. int main() {
  24.         // your code goes here
  25.         preprocess();
  26.         int n;
  27.         cin >> n;
  28.         vector<int> res, a(2*n);
  29.         for (int i=0; i<2*n; i++) {
  30.                 cin >> a[i];
  31.                 del[a[i]]++;
  32.         }
  33.         sort(a.begin(), a.end());
  34.         for (int i=a.size()-1; i>=0; i--) {
  35.                 if (del[a[i]]) {
  36.                         if (max_factor[a[i]] == a[i]) {
  37.                                 del[pr[a[i]-1]]--;
  38.                                 res.push_back(pr[a[i]-1]);
  39.                         } else {
  40.                                 del[max_factor[a[i]]]--;
  41.                                 res.push_back(a[i]);
  42.                         }
  43.                 }
  44.         }
  45.         for (int x: res) cout << x << " ";
  46.         cout << "\n";
  47.         return 0;
  48. }
Parsed in 0.008 seconds