切換
舊版
前往
大廳
主題

ZeroJudge - b552: 3.找質數 解題心得

Not In My Back Yard | 2018-11-14 23:44:39 | 巴幣 0 | 人氣 268

題目連結:


題目大意:
給定一個十位數長的正整數。從第一位(最高位)看起,如果不是質數,則加入第二位。如果還不是質數,重複以上步驟。如果是質數,則從下一位重新進行以上步驟。

求這個數字經由以上步驟會有幾個質數,輸出個數和那些質數。如果沒有質數,則輸出「0」。各筆輸出之間要空一行。



範例輸入:
1359376716
2359837607
8888888819
8888888809
8765432107
8765412107


範例輸出:
4
13
5
937
67

6
2
3
5
983
7
607

0

1
8888888809

0

2
87654121
7


解題思維:
用字串讀取數字,方便從最高位讀取。

預先建立 ≦ 100000 的質數,然後利用 O(n ^ (1 / 2)) 的演算法判斷現在讀到的數字群是否為質數(一個數是否為質數,只要判斷到平方根以下的數字可否整除即可)。

如果是質數,就先放入陣列,且數量 + 1 。然後繼續讀下一個數字。

最後輸出數量。如果數量為 0 ,則不需做任何額外動作;反之,輸出剛剛儲存的質數。




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

創作回應

可以用stringstream節省中間那段字串轉數字的行數,至於有沒有比較快我不清楚
2019-06-14 13:48:34

更多創作