fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define FOR(i, a, b) for(int i=(a), _b=(b); i<_b; ++i)
  4. #define fi first
  5. #define se second
  6. #define pb push_back
  7. #define ll long long
  8. #define sz(a) a.size()
  9. #define all(a) a.begin(),a.end()
  10. const int N = 1 + 1e7;
  11. const int INF = 1e9;
  12.  
  13. int t;
  14.  
  15. vector <int> p;
  16. vector <bool> prime(N + 9, true);
  17.  
  18. void sang() {
  19.     p.pb(2);
  20.     for(ll i = 3; i <= N; i += 2)
  21.         if(prime[i] == true) {
  22.             p.pb(i);
  23.             for(ll j = i * i; j <= N; j += i * 2)
  24.                 prime[j] = false;
  25.         }
  26. }
  27.  
  28. void solve() {
  29.     ll n;
  30.     cin >> n;
  31.     for(auto i : p) {
  32.         if(i * i > n) // => n là số nguyên tố vì n không có ước nguyên tố từ 1 -> sqrt(n) 
  33.             break;
  34.         if(n % i == 0) {
  35.             cout << n / i << '\n';
  36.             return; // kết thúc hàm
  37.         }
  38.     }
  39.     cout << -1 << '\n';
  40. }
  41.  
  42. int32_t main() {
  43.     ios_base::sync_with_stdio (false);
  44.     cin.tie(NULL); cout.tie(NULL);
  45.     sang();
  46.     cin >> t;
  47.     while(t--) 
  48.         solve();
  49.     return 0;
  50. }
Success #stdin #stdout 0.04s 9416KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Mfw3ZZ
Ước chung lớn nhất(sàng)
language:
C++14 (clang 8.0)
created:
7 days 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!