fork download 
  1. #include <iostream>
  2. using namespace std;
  3. #define INF 1000000007
  4. int main() {
  5. 	// your code goes here
  6. 	int dp[101] = {0};
  7. 	int a,b,i,j;
  8. 	scanf("%d%d",&a, &b);
  9. 	for(i=a;i<=b;i++)
  10. 		dp[i] = INF;
  11. 	dp[a] = 0;
  12. 	for(i=a; i<=b; i++){
  13. 		for(j=2; j*j<=i; j++){
  14. 			if(i%j == 0){
  15. 				dp[i+j] = min(dp[i+j], dp[i]+1);
  16. 				dp[i+i/j] = min(dp[i+i/j], dp[i]+1);
  17. 			}
  18. 		}
  19. 		printf("i=%d dp=%d\n",i, dp[i]);
  20. 	}
  21. 	printf("%d\n", dp[b]);
  22. 	return 0;
  23. }
Success #stdin #stdout 0s 16064KB
comments (?)
stdin 
4 24
stdout 
i=4 dp=0
i=5 dp=1000000007
i=6 dp=1
i=7 dp=1000000007
i=8 dp=2
i=9 dp=2
i=10 dp=3
i=11 dp=1000000007
i=12 dp=3
i=13 dp=1000000007
i=14 dp=4
i=15 dp=4
i=16 dp=4
i=17 dp=1000000007
i=18 dp=4
i=19 dp=1000000007
i=20 dp=5
i=21 dp=5
i=22 dp=6
i=23 dp=1000000007
i=24 dp=5
5
https://ideone.com/labUid
language:
C++14 (gcc 8.3)
created:
6 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!