fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5.  
  6. int main() {
  7. 	ll n;
  8. 	cin>>n;
  9. 	vector<ll> spf(n + 1);
  10.     for(ll i=0;i<=n;i++) 
  11.     	spf[i]=i;
  12.  
  13. 	for(ll p=2;p<=sqrt(n);p++){
  14. 		if(spf[p]==p){
  15. 			for(ll i=p*p;i<=n;i=i+p){
  16. 				spf[i]=min(p, spf[i]);
  17. 			}
  18. 		}
  19. 	}
  20. 	cout<<spf[n];
  21. 	return 0;
  22. }
Success #stdin #stdout 0.01s 10892KB
comments (?)
stdin
copy 
994009
stdout
copy 
997
https://ideone.com/w8fDLX
language:
C++ (gcc 8.3)
created:
9 hours 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!