fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define mod 1000000007
  3. #define ll long int
  4. #define big 100000000000000000
  5. using namespace std;
  6.  
  7. ll n,k,ans,dp[1000010];
  8. ll sieve[1000010]={0};
  9. /*
  10. ll recur(ll n){
  11. 	if(n == 0)
  12. 		return 0;
  13. 	if(dp[n])
  14. 		return dp[n];
  15. 	ll temp = INT_MAX,x;
  16. 	vector<ll>::iterator hi,lo;
  17. 	hi = upper_bound(primes.begin(),primes.end(),sqrt(n));
  18. 	lo = primes.begin();
  19. 	if(hi == primes.end())
  20. 		hi--;
  21. 	for(;hi>=lo;hi--){
  22. 	//	cout<<n<<"-"<<*hi<<"\n";
  23. 		x = n/(*hi);
  24. 		if(sieve[x]==0 && n%(*hi)==0)
  25. 			temp = min(temp,1+recur(n-x));
  26. 		if(n%(*hi) == 0)
  27. 			temp = min(temp,1+recur(n-(*hi)));
  28. 	}
  29. //	cout<<n<<" "<<temp<<"\n";
  30. 	return dp[n] = temp;
  31. }*/
  32. int main(){
  33. //	freopen("input.txt","r",stdin);
  34. 	ios::sync_with_stdio(0);
  35.  
  36. 	ll i,j;
  37.  
  38. 	cin>>n;
  39. 	for(i=2;i<=n;i=i+2)
  40. 		sieve[i]=2;
  41. 	for(i=3;i<=sqrt(n);i=i+2){
  42. 		if(sieve[i] == 0){
  43. 			for(j=1;i*j<=n;j=j+2)
  44. 			{
  45. 				if(sieve[i*j]==0)
  46. 					sieve[i*j] = i;
  47. 			}
  48. 		}
  49. 	}
  50. 	for(i=2;i<=n;++i)
  51. 	{
  52. 		if(sieve[i]==0)
  53. 			sieve[i] = i;
  54. 	}
  55. 	dp[0]=0;
  56. 	dp[1]=0;
  57. 	dp[2] = 1;
  58. 	for(i=3;i<=n;++i)
  59. 	{
  60. 		ll x = i;
  61. 		dp[i] = INT_MAX;
  62. 		while(x>1)
  63. 		{
  64. 			dp[i] = min(dp[i],dp[i-sieve[x]]+1);
  65. 			x = x/sieve[x];
  66. 		}
  67. 	}
  68. 	/*for(i=0;i<=n;i++)
  69. 		cout<<dp[i]<<" ";
  70. 	cout<<"\n";*/
  71. 	cout<<dp[n];
  72. 	return 0;
  73. }
Success #stdin #stdout 0s 11224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ST5D6r
language:
C++14 (gcc 8.3)
created:
8 years 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!