主題

ZeroJudge - b513: 判斷質數-商競103 解題心得

Not In My Back Yard | 2021-09-30 00:00:15 | 巴幣 0 | 人氣 105

題目連結:


題目大意:
輸入第一列給定一正整數 n(1 ≦ n ≦ 5),代表有 n 筆測試資料,每筆佔一列。每列給定一正整數 x(2 ≦ x ≦ 65535),試問 x 是否為質數?如果是輸出「Y」;反之輸出「N」。



範例輸入:
3
31
19
2047


範例輸出:
Y
Y
N


解題思維:
可以視為 ZeroJudge 上的 a007 這個題目超級弱化版。a007 的解法當然可以解出本題(參見這篇文章)。但是因為數字範圍小甚至連數量也不多,所以一般的建表(如這題)一定可行。

而稍微暴力一點的也會過:對於每個數字 x,從 2 開始到 floor(sqrt(x))(即最接近 x 的平方根且不超過其值之整數) 為止試著去除 x。如果有任何一者整除 x 即代表 x 不是質數。

甚至連最暴力的也會過:把 2 ~ x - 1 的數字都除除看,有人整除 x 就代表 x 不是質數。

所以本題可以算是一個好的質數練習題,可供實作出許多不同的解法。




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

創作回應

相關創作

更多創作