13194: DPA Number II ★★☆☆☆ 題組：Problem Set Archive with Online Judge 題號：13194: DPS Numbers II 解題者：林浩陽 解題日期：2019年4月17日 題意： 首先輸入一個數字，找出這個數字所有的因數，並 將這個數字除了自己以外所有的因數加起來與原來的數 字做比較 ， 如果比較小輸出 deficient ，如果一樣大輸出 perfect ，如果比較大輸出 abundant 。 1 1
先製作質數表，再利用質數表對目標數字做質因數分 解，並且利用排列組合來找出所有的因數，再將找出的 因數相加。 題意範例： Input: 8 // 8 的因數有 1 , 2 , 4 6 // 6 的因數有 1 , 2 , 3 18 // 18 的因數有 1 , 2 , 3 , 6 , 9 Output: deficient // 1 + 2 + 4 = 7 < 8 perfect // 1 + 2 + 3 = 6 = 6 abundant // 1 + 2 + 3 + 6 + 9 = 21 > 18 解法： 先製作質數表，再利用質數表對目標數字做質因數分 解，並且利用排列組合來找出所有的因數，再將找出的 因數相加。 2 2
質數表: 由於3是白色的，所以3是質數，而3的倍數都不是質數。 以此列推，將剩下的質數找出來。 假設要找出2 ~ 10的因數，先列出2 ~ 10，將他們設為白色。 由於2 是白色，所以2 是質數，2 的倍數則都不是質數。(藍色表示質數，紅色表示非質數) 由於3是白色的，所以3是質數，而3的倍數都不是質數。 以此列推，將剩下的質數找出來。 2 3 4 5 6 7 8 9 10 2 3 4 5 6 7 8 9 10 2 3 4 5 6 7 8 9 10 2 3 4 5 6 7 8 9 10
因數總合: 假設以504為目標數，先對它做質因數分解。 504 = 2³ X 3² X 7¹ 利用排列組合可以找到504所有的因數 504的因數總合= ( 1 + 2 + 2² + 2³ )*( 1 + 3 + 3² )*( 1 + 7 )=1560 因為題目要求的因數不包含自己，所以再減去自己 504的因數總合為: 1560 - 504 = 1056
解法範例：無 討論： 原本想要做成每次輸入數字就直接從1~1000000找出這個 數字的因數，但這樣太浪費時間了，所以後來改用做質 數表的方式來解再加上排列組合來解。 5 5