題目連結:
題目大意:
給定一個十位數長的正整數。從第一位(最高位)看起,如果不是質數,則加入第二位。如果還不是質數,重複以上步驟。如果是質數,則從下一位重新進行以上步驟。
求這個數字經由以上步驟會有幾個質數,輸出個數和那些質數。如果沒有質數,則輸出「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 ,則不需做任何額外動作;反之,輸出剛剛儲存的質數。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。