fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4.  
  5. const int mxn = 1e7+1;
  6.  
  7.  
  8. int fact[mxn+1];
  9. vector<int> criba(mxn+1,-1);
  10.  
  11. void sieve(){
  12.  
  13.     criba[0] = criba[1] = 1;
  14.     for(int i = 2; i <= mxn; i++){
  15.         if(criba[i] == -1){
  16.             for(int j = i*i; j <= mxn; j += i)
  17.                 if(criba[j] == -1)
  18.                     criba[j] = i;
  19.         }
  20.     }
  21.     for(int i = 2; i <= mxn; i++)
  22.         if(criba[i] == -1)
  23.             criba[i] = i;
  24. }
  25.  
  26. int divs(int n){
  27.     int ans = 0;
  28.     while(n % criba[n] == 0 && n > 1){
  29.         ans++;
  30.         n /= criba[n];
  31.     }
  32.     return ans;
  33. }
  34.  
  35. void preFact(){
  36.     fact[0] = fact[1] = 0;
  37.     for(int i = 2; i <= mxn; i++)
  38.         fact[i] = fact[i-1] + divs(i);
  39. }
  40.  
  41. void solve(){
  42.     int n;
  43.     int it = 0;
  44.     while(cin >> n){
  45.         if(n == -1)break;
  46.  
  47.         int lo = 0, hi = mxn, ans = -1;
  48.         while(lo <= hi){
  49.             int mid = lo + (hi-lo)/2;
  50.             if(fact[mid] >= n){
  51.                 if(fact[mid] == n)ans = mid;
  52.                 hi = mid-1;
  53.             }
  54.             else lo = mid+1;
  55.  
  56.         }
  57.         cout << "Case " << ++it << ": ";
  58.         if(ans>=0)cout << ans << "!" << "\n";
  59.         else cout << "Not possible." << "\n";
  60.     }
  61. }
  62.  
  63. int32_t main() {
  64.     ios::sync_with_stdio(false);
  65.     cin.tie(0);
  66. 	sieve();
  67. 	preFact();
  68. 	solve();
  69.  
  70.     return 0;
  71. }
  72.  
Success #stdin #stdout 1.83s 159412KB
comments (?)
stdin
copy 
1
2
3
-1
stdout
copy 
Case 1: 2!
Case 2: 3!
Case 3: Not possible.
https://ideone.com/Bezo8Y
language:
C++ (gcc 8.3)
created:
3 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!