SHARE
TWEET

Untitled

a guest May 19th, 2017 46 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <vector>
  2. #include <cstdio>
  3.  
  4. using namespace std;
  5.  
  6. const int MAXN = 2000000;
  7.  
  8. int at[MAXN];
  9. int next[MAXN];
  10.  
  11. void sieve()
  12. {
  13.     for(int i = 0;i < MAXN; i++)
  14.         at[ i ] = 1 ;
  15.  
  16.     for(int i = 2; i < MAXN; i ++)
  17.     {
  18.         if( at[ i ] > 1 ) continue ;
  19.         for(int j = i ; j < MAXN; j += i)
  20.             at[ j ] *= i;
  21.     }
  22.  
  23.     for(int i = 2; i < MAXN; i++)
  24.     {
  25.         next[ at[at[i]] ] = i;
  26.         at[ at[i] ] = i ;
  27.     }
  28.  
  29.     return ;
  30. }
  31.  
  32. int main()
  33. {
  34.     sieve ();
  35.  
  36.     int n ;
  37.  
  38.     while ( scanf ("%d" ,&n) != EOF)
  39.     {
  40.         if( next[n] <= n )
  41.             puts ("Not Exist!");
  42.         else
  43.             printf ("%d\n" , next[n]);
  44.     }
  45.  
  46.     return 0;
  47. }
RAW Paste Data
Top