fork download
copy 
  1. //
  2. //  main.cpp
  3. //  Sieve of Eratosthenes
  4. //
  5. //  Created by Himanshu on 18/08/21.
  6. //
  7. #include <iostream>
  8. #include <cmath>
  9. #include <cstdio>
  10. #include <vector>
  11. using namespace std;
  12. typedef unsigned long long ll;
  13. int sieve[2000000] = {0};
  14.  
  15. void solve() {
  16.     ll i,j;
  17.  
  18.     // marking all evens as non-prime
  19.     // if: sieve[i] = 0, it is prime
  20.     // if sieve[i] = 1, it is composite
  21.     for (i=4; i<=1000001; i+=2) {
  22.         sieve[i] = 1;
  23.     }
  24.  
  25.     // Checking all odd numbers
  26.     for (i=3; i<=1000001; i+=2) {
  27.         for (j=i*i; j<=1000001; j+=i) {
  28.             sieve[j] = 1;
  29.         }
  30.     }
  31.  
  32. }
  33.  
  34. // Utility function to check if a particular
  35. // number is prime
  36. bool isprime(ll n) {
  37.     ll i,root;
  38.     root = (ll)sqrt(n) + 1;
  39.  
  40.     for (i=2; i<=root; i++) {
  41.         if (n%i == 0) {
  42.             return false;
  43.         }
  44.     }
  45.  
  46.     return true;
  47. }
  48.  
  49.  
  50. int main() {
  51.  
  52.     ll T, n, sol, root, tp;
  53.     scanf("%llu",&T);
  54.  
  55.     solve();
  56.  
  57.     while (T--) {
  58.         scanf("%llu",&n);
  59.         root = (ll)sqrt(n) + 1;
  60.         sol = n;
  61.  
  62.         for (ll i=2; i<=root; i++) {
  63.  
  64.             if (n%i == 0) {
  65.                 tp = n/i;
  66.                 if (sieve[i] == 0) {
  67.                   sol = i;
  68.                 }
  69.  
  70.                 // selecting the larger prime between tp and i
  71.                 if (tp > i) {
  72.                     if (tp <= 1000000) {
  73.                         if (sieve[tp] == 0) {
  74.                             sol = tp;
  75.                             break;
  76.                         }
  77.                     } else if (isprime(tp)) {
  78.                         sol = tp;
  79.                         break;
  80.                     }
  81.                 }
  82.             }
  83.         }
  84.  
  85.         printf("%llu\n",sol);
  86.     }
  87.  
  88.     return 0;
  89. }
Success #stdin #stdout 0.01s 7660KB
comments (?)
stdin
copy 
2
10
17
stdout
copy 
5
17
https://ideone.com/oFXSTJ
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

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!