筛选法求素数⼀般⽅法求素数判断⼀个数是否是素数
筛选法求素数&⼀般⽅法求素数&判断⼀个数是否是素数
1.判断⼀个数是否是素数
#include<stdio.h>
#include<math.h>
int main()
{
int n, i, k;
printf("please enter a integer number");
scanf_s("%d", &n);
k = sqrt(n);
for (i = 2; i < k; i++)
if (n % i == 0)break;
if (i <= k)printf("%d is not a prime number.\n", n);
else printf("%d is a prime number.\n", n);
return 0;
}
运⾏结果
2.筛选法求素数（以求200以内素数为例）
1.解释下什么是筛选法？
筛选法⼜称，具体做法是：先把N个⾃然数按次序排列起来。1不是，也不是，要划去。第⼆个数2是质数留下来，⽽把2后⾯所有能被2整除的数都划去。2后⾯第⼀个没划去的数是3，把3留下，再把3后⾯所有能被3整除的数都划去。3后⾯第⼀个没划去的数是5，把5留下，再把5后⾯所有能被5整除的数都划去。这样⼀直做下去，就会把不超过N的全部合数都筛掉，留下的就是不超过N的全部质数。
2.程序步骤：
<1> 先将1挖掉(因为1不是素数)。
<2> ⽤2去除它后⾯的各个数，把能被2整除的数挖掉，即把2的倍数挖掉。
<3> ⽤3去除它后⾯的各数，把3的倍数挖掉。
<4> 分别⽤5…各数作为除数去除这些数以后的各数。
3.具体应⽤（求100以内的素数）：
基本思想是：把从1开始的、某⼀范围内的正整数从⼩到⼤顺序排列，把不是素数的数全部赋值为0，最后只输出不是零的数即素数。1不是素数，⾸先把它换为0。剩下的数中选择最⼩的数是素数，然后把它的倍数全部换为0。依次类推，直到结束。
如有：
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
1不是素数，换为0。剩下的数中2最⼩，是素数，然后把它的倍数全部换为0，余下的数是：
0 2 3 0 5 0 7 0 9 0
11 0 13 0 15 0 17 0 19 0
21 0 23 0 25 0 27 0 29 0
剩下的数中3最⼩，是素数，然后把它的倍数全部换为0，如此下去直到所有的数都被筛完，求出的素数为：
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97      （载⾄）
{
int i, j, n, a[N+1];
for (i = 1; i < N; i++)
{
a[i] = i;
}
a[0] = 0;
for (i = 2; i <= sqrt(N); i++)//筛选
{
for (j = i + 1; j <=N; j++)
{
if (a[i] != 0 && a[j] != 0)
if (a[j] % a[i] == 0)
{
a[j] = 0;
}
}
}
printf("\n");
for (i = 2, n = 0; i < N; i++)
{
if (a[i] != 0)
{
printf("%5d", a[i]);
n++;
}
if (n == 10)//控制换⾏
{
printf("\n");
n = 0;
}
}
return 0;
}
运⾏结果
3.⼀般法求素数 (200以内)
c++判断素数sqrt是求平⽅根的函数，其对参数的要求是双精度，在执⾏时会⾃动将 i 转换为双精度数，求出的函数值也是双精度，再把它赋值给k，系统会⾃动舍弃⼩数部分，将整数部分赋给k。
{
int i, j, k, n = 0;
for (i = 101; i <= N; i = i + 2)    {
k = sqrt(i);
for (j = 2; j <= k; j++)
{
if (i % j == 0)break;
}if (j >= k + 1)
{
printf("%5d", i);
n++;
}
if (n % 10 == 0)//控制换⾏        {
printf("\n");
}
}
return 0;
}
运⾏结果
作者也不知道为什么会有这么多空⾏，有知道的⼤佬可以留⾔。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。