素數的個數演算法

① 實現用於計算素數的演算法

#include <stdio.h>
void main()
{
int num[10] = {2,3,4,5,6,7,8,9,10,11};
int *temp = num; // 用於臨時存放素數
int j=0;

for(int i=0;i<10;i++)
{
if(num[i]%2 != 0 )
{
*temp++ = num[i];// 不是2的倍數，就放入temp中
j++; // 用於記錄素數的個數，以便之後的循環使用
}
}
for(int i=0;i<j;i++)
{
printf("%d\n",temp[i]);// 輸出所有素數
}

}

② 素數演算法

素數在計算機中經常被運用於計算機安全（密碼相關的計算），所以研究一下素數的判斷演算法是相當有必要的。所以現在就來看一下兩種比較常見的演算法，試除法和Eratosthenes演算法吧！

用需要驗證的數 N 逐個除以從 2 開始至 N-1 中的所有數，若能被一個數整除，表示它有一個因數，說明數 N 不是素數；若一直到 N-1 都不能被整除，則說明 N 是素數。（當然我們對於因數的判斷不必計算到 N-1,只需要到 就可以了）

Eratosthenes演算法的實現，其實就像是一個篩子，每次過濾掉合數，最後剩下的就是素數了，例如：如果要找出2~10000之間所有素數的演算法，可以先過濾調用 2 的倍數，再過濾掉 3 的倍數，依次再5,7,11,13...97 就是
以內的所有素數。剩下的就都是素數了。

兩種方法測試1000000個數據中找素數，對比如下

結果：

顯然，Eratosthenes演算法效率高得多了。

③ c語言求素數的演算法

根據素數的性質，代碼設計如下：

設計一：判斷n是否能被1~n-1整除，不能整除為素數

#include<stdio.h>

int main()

{

int i, n;

scanf("%d", &n);

for (i = 2; i < n ; i++)

{

if (n%i == 0)

break;

}

if (i < n) printf("This is not a prime.");

else printf("This is a prime.");

return 0;

}

設計二：判斷n是否能被2~√n間的整數整除，不能整除為素數

#include<stdio.h>

#include<math.h>

int main()

{

int n,i;

double k;

scanf("%d", &n);

k = sqrt(n);

for (i = 2; i <= k;i++)

{

if (n%i == 0) break;

}

if (i <=k) printf("This is not a prime.");

else printf("This is a prime");

return 0;

}

(3)素數的個數演算法擴展閱讀：

1.素數的定義是只能被1和他本身整除,1不是素數.因此要判斷一個數是否為素數.就要判斷它能不能被比他小的所有素數整除,這是一個演算法.(寫到演算法時,我只能寫出用它除以比他小的所有數,造成運算速度低下)

2.如果一個質數大於根號n，而n可以除盡它，那麼n必然也可以除盡一個更小的質數。由此可以得到一個法2較快的素數判斷演算法