算法提高 拿糖果
时间限制：1.0s 内存限制：256.0MB
问题描述
妈妈给小B买了N块糖！但是她不允许小B直接吃掉。
假设当前有M块糖，小B每次可以拿P块糖，其中P是M的一个不大于根号下M的质因数。这时，妈妈就会在小B拿了P块糖以后再从糖堆里拿走P块糖。然后小B就可以接着拿糖。
现在小B希望知道最多可以拿多少糖。
假设当前有M块糖，小B每次可以拿P块糖，其中P是M的一个不大于根号下M的质因数。这时，妈妈就会在小B拿了P块糖以后再从糖堆里拿走P块糖。然后小B就可以接着拿糖。
现在小B希望知道最多可以拿多少糖。
输入格式
一个整数N
输出格式
最多可以拿多少糖
样例输入
15
样例输出
6
数据规模和约定
N <= 100000
作者注释：
1、题目易懂。
2、学会一招：#define max(a,b) (a>b)?a:b——若在之前学会，会省多少时间了。
#include<stdio.h>
#include<string.h>
#include<math.h>
#define max(a,b) (a>b)?a:b
int prime[], vis[], dp[];
main(){
int n, cur, i, j, k;
scanf("%d", &n);
cur=;
memset(vis, , sizeof(vis));
for(i=; i<; i++){
if(!vis[i]){
prime[cur++]=i;
for(j=i+i; j<; j=j+i){
vis[j]=;
}
}
}
memset(dp, , sizeof(dp));
for(i=; i<=n; i++){
for(j=; j<=cur-; j++){
if(prime[j]<=sqrt(i)){
if(i%prime[j]==)
dp[i]=max(dp[i],dp[i-*prime[j]]+prime[j]);//拿多的
}
else{
break;
}
}
}
printf("%d",dp[n]);
}