#18420: 建2個表


rmp4joxj6 (盧邊談話)

學校 : 中原大學
編號 : 97841
來源 : [27.247.230.6]
最後登入時間 :
2020-10-20 18:00:03
d362. 10394 - Twin Primes -- UVa10394 | From: [119.77.170.142] | 發表日期 : 2019-07-11 21:14

第100,000對=(18409199, 18409201)

判斷質數只要試除sqrt(n)以內的質數就好

其中√18409199=4290.,,,,,,,  , 4289是質數,若把3當作是第1個質數,則4289是第588個質數

所以我建了第一個表存質數 Prime[588]

接下來建第二個表 table[10,0000]={3,5} 存答案,例如:輸入n,則輸出 table[n-1] , table[n-1]+2

除了5之外,其他的尾數5都不是質數,所以先把這個例外處理好

ex 13 15 17    因為15的關係,所以13,17不用算是不是質數

for(int a=11;a<=18409199;a+=2){
  if(a%10==3){
    a+=2;
    continue; 
  }

接下來要判別 a,a+2是不是質數 , 如果a+2不是質數,就不用算a+4了

 

我拿去測試執行TLE(1s) , 送出解答是AC(1.1s)

 
ZeroJudge Forum