我們要判斷素數,首先要知道素數的定義。
知道瞭素數的定義,那麼我們應該想一下,如何去判斷一個數是否為素數?
以下除瞭第一種方法,第2~4種方法都是用第二種思路做的當要判斷的目標數很少時,第一種高效。但是當給定的目標數組很多,數也很大時。後面的思路配上高效的查找算法,顯然更高效
方法1:暴力求解
1-1:稍微動動腦
思想:根據素數的定義思考。素數是大於1的自然數,除瞭1和自身外,其他數都不是它的因子。 那我們就可以用一個循環,從2開始遍歷到這個數減去1,如果這個數都不能被整除,那麼這個數就是素數。 也就是說: 給定一個數 n , i 從 2 開始取值,直到 n – 1(取整數),如果 n % i != 0 , n 就是素數 進一步思考,有必要遍歷到 n – 1 嗎? 除瞭1以外,任何合數最小的因子就是2,那最大的因子就是 n/2 那我們就遍歷到 n/2就足夠瞭
這樣我們就可以寫出這個算法的核心代碼:
int isPrime(int target) {
int i = 0;
if (target <= 1) {
printf("illegal input!n");//素數定義
return -1;
}
for (i = 2; i <= target / 2; i++) {
if (target % i == 0)
return 0;//不是素數直接返回0
}
return 1;//是素數返回1
}