求質數（素數）算法及其改進

2019-11-06 06:06:23

字體：大中小

來源：轉載

供稿：網友

質數概念：

質數（PRime number）又稱素數，有無限個。質數定義為在大于1的自然數中，除了1和它本身以外不再有其他因數的數稱為質數。

數學還是要認真扣概念的，各位看官首先默讀一遍概念吧~

算法思路：

本例演示求n以內的素數個數。同時類比打印n以內的素數；求前n個素數的乘積模50000；求前n個素數的乘積等題目。

判斷一個數k是否為素數需要判斷這個數有沒有其他因數，也就是k能否除盡區間[2，根號k]。

改進前代碼：

#include <iostream>#include<math.h>using namespace std;int main(){ int n, sum = 0, m; cin >> n; for(int i = 2; i <= n; i++){ m = sqrt(i); int j; for(j = 2; j <= m+1; j++){ if(i%j == 0){ break; } } if(j > m) sum++; } cout << sum <<endl; return 0;}

結果圖：這里寫圖片描述

改進：眾所周知C++開根號費時，此處改進就是不進行開根號。例如：[9, 24]開根號都是3，我們設開根號的結果為m，即是[m*m, m*(m+2)]，這樣就大大減少了計算次數，也不用開根號，只需讓在區間里的數都去除2到m，并判斷每一個結果的余數是否為0，為0則跳出循環即可。

改進后代碼

#include <iostream>using namespace std;int main(){ int n, m = 1, Max; int sum = 0; cin >> n; Max = m*m + 2*m; for(int i = 2; i <= n; i++){ if(i > Max){ m++; Max = m*m + 2*m; } int j; for(j = 2; j <= m+1; j++){ if(i%j == 0) break; } if(j > m){ sum++; } } cout << sum <<endl; return 0;}

結果圖：這里寫圖片描述