fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAX = 1e7 + 1;
  5. int spf[MAX];
  6.  
  7. void build_sieve() {
  8.     for (int i = 2; i < MAX; ++i) {
  9.         if (spf[i] == 0) { 
  10.             for (int j = i; j < MAX; j += i) {
  11.                 if (spf[j] == 0) spf[j] = i;
  12.             }
  13.         }
  14.     }
  15. }
  16.  
  17. vector<int> get_distinct_prime_factors(int x) {
  18.     vector<int> primes;
  19.     while (x > 1) {
  20.         int p = spf[x];
  21.         primes.push_back(p);
  22.         while (x % p == 0) x /= p;
  23.     }
  24.     return primes;
  25. }
  26.  
  27. int main() {
  28.     ios_base::sync_with_stdio(false);
  29.     cin.tie(0);
  30.  
  31.     build_sieve();
  32.  
  33.     int n;
  34.     cin >> n;
  35.     vector<int> a(n);
  36.  
  37.     for (int i = 0; i < n; ++i) 
  38.         cin >> a[i];
  39.  
  40.     vector<int> d1(n), d2(n);
  41.  
  42.     for (int i = 0; i < n; ++i) {
  43.         auto primes = get_distinct_prime_factors(a[i]);
  44.  
  45.         if (primes.size() < 2) {
  46.             d1[i] = d2[i] = -1; 
  47.         } else {
  48.             d1[i] = primes[0];  
  49.             d2[i] = primes[1];
  50.             for(int j=2;j<(int)primes.size();j++) d2[i]*=primes[j];
  51.         }
  52.     }
  53.  
  54.     for (int x : d1) cout << x << " ";
  55.     cout << "\n";
  56.     for (int x : d2) cout << x << " ";
  57.     cout << "\n";
  58.  
  59.     return 0;
  60. }
  61.  
Success #stdin #stdout 0.21s 42640KB
comments (?)
stdin
copy 
10
2 3 4 5 6 7 8 9 10 24
stdout
copy 
-1 -1 -1 -1 2 -1 -1 -1 2 2 
-1 -1 -1 -1 3 -1 -1 -1 5 3
https://ideone.com/mrJ8w6
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!