fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define N 10001
  4.  
  5. typedef long long ll;
  6. bool visit[N];
  7. vector<int> prime;
  8.  
  9.  
  10. void sieve()
  11. {
  12.         	memset( visit , 0 , sizeof(visit));
  13.         	for( int i=2;i<N;i++ )
  14.         	{
  15.         	    if( visit[i] == 0)
  16.         	    {
  17.         	        prime.push_back(i);
  18.         	        for( int j=i*2; j<N; j=j+i )
  19.         	        {
  20.         	            visit[j] = 1;
  21.         	        }
  22.         	    }
  23.         	}	
  24. }
  25.  
  26. void sol(long long n, vector<int>&prime)
  27. {
  28.             ll ans = n;
  29.     	    for(int i=0; i<prime.size() || prime[i]>n; i++)
  30.     	    {
  31.     	        while(n%prime[i]==0)
  32.     	        {
  33.     	            n=n/prime[i];
  34.     	            ans = prime[i];
  35.     	        }
  36.     	    }
  37.     	    ans = max(ans, n);
  38.     	    cout<<ans<<endl;
  39. }
  40.  
  41. int main() 
  42. {
  43.            ll tc, n;
  44.            sieve();
  45.  
  46. 	       cin>>n;
  47. 	       sol(n, prime);
  48.  
  49.            return 0;
  50. }
  51.  
  52.  
  53.  
  54.  
  55.  
Success #stdin #stdout 0s 15248KB
comments (?)
stdin
copy 
600851475143
stdout
copy 
6857
https://ideone.com/kizzWs
language:
C++14 (gcc 8.3)
created:
5 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!