國中數學告訴我們，任何大於1的正整數，皆有其質因數分解

是故，凡包含兩個質因數的合數皆可透過詢問質數得知其是否整除

ex: 我想知道答案是否"可能"為15 ，只要問3、5即可   因為 15  = 3x5

那30呢 ?  就問 2、3、5 (都質數)

那45呢?   就問 2、5、9  (9是合數!!! ) 沒錯!  但9可寫成 3*3 所以，所有質數的冪次方(小於等於N)都要算進去 

你可以試著舉任何例子，應該都會符合 (畢竟我也是AC後才敢發文)

國中數學告訴我們，任何大於1的正整數，皆有其質因數分解

是故，凡包含兩個質因數的合數皆可透過詢問質數得知其是否整除

ex: 我想知道答案是否"可能"為15 ，只要問3、5即可   因為 15  = 3x5

那30呢 ?  就問 2、3、5 (都質數)

那45呢?   就問 2、5、9  (9是合數!!! ) 沒錯!  但9可寫成 3*3 所以，所有質數的冪次方(小於等於N)都要算進去 

你可以試著舉任何例子，應該都會符合 (畢竟我也是AC後才敢發文)

你好可以請問一下我不太懂你的意思

照你的意思的話為甚麼題目的4會輸出2,3,4呢

不好意思，我現在才看到您的留言

輸入如果是4

代表學姊想的數字為 1~4 其中一個

那我們就要想想，要如何才能決定是哪一個數字呢?

於是我就想說，是否可以用質因數分解的概念呢?

因為每一個正整數(1除外)，都有其質因數分解

因此，我只要討論在N以下的質因數，就可以確定是哪一個數了

真的嗎? 其實這樣還不太對

例如說 4

4 = 2x2

如果我告訴你這個數可以被2整除

那麼請問這個數是 2 還是 4 ?   (N = 4)

我們不知道

因此質數的冪次方(4 9 16 25 36 49 64 81 ..... )都必須考慮進去

那至於1的部分，我們不必詢問

因為如果所有 <= N 的質因數都無法整除的話

那麼這個數就是1

這樣懂嗎?

EX:  N = 4

ans:  1  2  3  4  (其中1個)

Q1: 此數能否被2整除?

Y: 2  4  (其中一個)

N: 1  3 (其中一個)

若Q1答案Y

此數能否被4整除?

Y: 4

N: 2

若Q1答案N

此數能否被3整除?

Y: 3

N: 1

希望您能接受

如果我對質數的冪次二分搜呢?