讀處

試撰寫一程式，由鍵盤輸入一個整數，然後判別此數是否為質數(prime)。

若是，則印出"此數是質數"字串，若不是，則印出"此數不是質數"字串。

(質數是指除了1和它本身之外，沒有其他的數可以整除它的數，例如，2,3,5,7與11等皆為質數)

上述做法時間複雜度為O(n)

若改用以下做法，時間複雜度為O(n^1/2)

判斷質數的方法，就是要找因數，對吧><

但是第一個做法是找出所有的因數

而我們不需要找所有的因數，只需要找一半的因數就行了

例如: 16的因數:1, 2, 4, 8, 16

i=4的時候，i*i=4*4<=16，迴圈就結束了

那8耶~~~~XD

因為判斷質數，如果16能被2整除，那表示也能被8整除，因為2*8=16

所以....

也就說...

跟剛才講的一樣

就是...

只需要找一半的因數就行了

=====================================================================

試撰寫一程式，可由鍵盤讀入一個正整數，並找出小於此數的最大質數。