素数的个数算法

① 实现用于计算素数的算法

#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较快的素数判断算法