轉站通知

本站已停止更新!!想繼續收看我的新文章的話,請前往我的新Blog - Chino's

2014年2月25日 星期二

STEP5::Problem 0005 : Ch1-2.梗賤橋

http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0005
這題題目要我們先換位置再判斷第m個木板是不是質數。

首先先建質數表,move[數字]=位置,用質數表去跑這個(交換位置),然後再用lu[數字]=位置轉換回位置對到數字。這樣好像是(根號N)^2=O(N)吧...
之後O(1)查詢,如果 lu[m] 是質數(g[]是篩質數的bool陣列)直接輸出質數,另外如果 lu[m]比n大,代表這一個是n以下最後一個合數的位置(質數應該移到這格,只是我跑的是n最大的狀態,所以這格會是大於n的合數),輸出質數。
其他狀況就直接輸出 lu[m]。