主題

ZeroJudge - a505: B. T-primes 解題心得

Not In My Back Yard | 2020-11-02 00:00:01 | 巴幣 0 | 人氣 43

題目連結:


題目大意:
第一列輸入給定一正整數 n (1 ≦ n ≦ 10 ^ 6),代表有 n 個正整數。接著的一列給定 n 個正整數(皆介於 1 ~ 10 ^ 14 之間),判斷該數是否為一個 T-prime。

T-prime 定義為一個只有三個相異因數的正整數。



範例輸入:
3
4 5 6


範例輸出:
YES
NO
NO


解題思維:
如果一數 X 是 T-prime,則可以發現 X 的平方根必為整數,且為 X 除了 1 和自身以外的第三個因數,而且還必是一個質數(如果不是質數,則會有此數以外的因數且那些因數不為 1 也不為 X)。

因此,我們可以先建立一個質數表(作法如這題)以便查找一數是否為質數(做到 10 ^ 7 以內的質數即可(雖然其實可以再將範圍壓低),因為 X 最大為 10 ^ 14)。

然後將 X 開平方根取整數部分(假設值為 Y),然後判斷 Y × Y 是否等於 X (看平方根是否為一整數的其中一個方式)以及 Y 是否為質數(根據質數表查詢)。如果都符合,則代表 X 是一個 T-prime;反之則不是。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作