#16997: 建表 by C


freedom501999@gmail.com (帥氣魔方生)

學校 : 不指定學校
編號 : 88611
來源 : [39.8.203.54]
最後登入時間 :
2019-05-30 22:56:25
d386. 10200 - Prime Time -- UVa10200 | From: [27.52.9.157] | 發表日期 : 2019-02-27 15:37

這題 n 範圍從 0 ~ 10000,只要建一個判斷 n^2 + n + 41 是否為質數的陣列 IsPrime [ 10001 ]

IsPrime [ n ] = 0 表示非質數,= 1 表示是質數

而 n^2 + n + 41 最大為 100010041,用傳統判斷質數的方法,需要從 2 開始共 1230 個質數來除

所以首先要找出 1230 個質數,存進一個陣列 prime [ 1230 ]

然後 i = 42 開始到 i = 10000,令 a = i^2 + i + 41

若 sqrt ( a ) 以內的質數都不能整除 a,IsPrime [ i ] = 1

而當 i 或 i + 1 是 41 的倍數時,a 一定不是質數,因為此時 a 可被 41 整除

( a = i * ( i + 1 ) + 41 ),用迴圈找的可以多判斷這個加速

建完表就可以開始讀測資了,至於四捨五入,可以搜尋 math.h 裡的 round() 函式,用這個處理

 
ZeroJudge Forum