[ACM] Q884: Factorial Factors

本來先建100以下的質數表

後來便炸了!

最後想到假設每個數都是質數,但0和1不是

舉例來說

若現在是2的質數在跑 假設49為質數.. 98=dp[49]+1=2

但事實上不合因為49並非質數

但不用急... 因為到跑7是質數時

98=dp[14]+1, 而14已經在有猜對為2*7,dp[14]=2

so dp[98]=3;

我的寫法有很多重複的地方,但比爆搜好很多了

其實也沒必要優化, 不要浪費時間 ㄎ

秒數:8604821 884 Factorial Factors Accepted ANSI C 0.064 2011-02-27 01:34:03

ㄎ
[c]
/* @file 884.c
* @date 02/27/2011
* @version v0.01
* @author "TXShon" <txshon@gmail.com>
* @note CreativeCommons(cc) 2011 TXShon, cc by-nc-nd
*
*Description
* Acm practice using c
*History
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int dp[1000010];

int main()
{
int n, i, j;
for( i=0; i<=1000000; i++){
dp[i] = 1;
}
dp[0] = 0;
dp[1] = 0;
for( i=2; i<1000000; i++){
if(dp[i]==1){
for(j=2; i*j<=1000000; j++){
dp[i*j]=dp[j]+1;
}
}
}
for( i=3; i<=1000000; i++){
dp[i]+=dp[i-1];
}
while(scanf("%d", &n)==1){
printf("%d\n", dp[n]);
}
return 0;
}

[/c]