【刷题】求出一定范围内的素数

什么是素数？

“素数”又称作“质素”，是指大于1的自然数，除了1与其自身外，不能被其它自然数整除的数，被称为素数（质素）。

如何求出n以内的素数？

这里总结出两种方法，并以这两种方法做讲解。分别是“筛选法”与“试除法”。

①筛选法：

用筛选法求n以内的素数。筛选法求解过程为：将2-n之间的正整数放在数组内存储，将数组中2之后的所有能被2整除的数清0，再将3之后的所有能被3整除的数清0，以此类推，直到n为止。数组中不为0的数即为素数。

②试除法：

判断某个数是不是素数，就用它与它之前所有的整数逐个进行整除一遍，如果没有能够被它整除的数，那么它就是素数。
比如：判断7是不是素数，用7整除1–6这六个数，结果这六个数都不能被7整除，那么7就是素数。

两种方法的具体实现

方法一：筛选法

//方法一：筛选法
#include 
int main()
{int n = 0;	//输入范围int arr[101];printf("筛选法-----\n");printf("请输入范围：");scanf("%d",&n);printf("素数：");for (int i = 2; i <= n; i++){            arr[i] = i;     //从2开始包括到n为止的数都存进数组里面//列举出所有的除数for (int j = 2; j <= n; j++){for (int k = j+1; k <= n; k++){if (arr[k]%j == 0)  //如果余数是0，说明被整除（不是素数）。{arr[k] = 0; //之所以置0，就是为了把素数留下。}    }                }}//打印输出素数for (int i = 2; i <= n; i++){if (arr[i] != 0){printf("%d " ,arr[i]);}}printf("\n");return 0;
}

运行结果：

方法二：试除法

方法二：试除法
#include 
int main()
{int n = 0;int i = 0;int j = 0;printf("试除法-----\n");printf("请输入范围：");scanf("%d",&n);printf("素数：");//判断i是否为素数for (i = 2; i <= n; i++){/*用i把i到i-1的数看看能不能进行整除，如果能整除，则说明这个数不是素数那么就来到if判断*/for (j = 2; j < i; j++){if (i%j == 0){break;}                }if (j == i)		//说明已经试除到最后一个数，还未能被整除，就说明是素数。{printf("%d ",j);	//打印输出素数}}printf("\n");  return 0;
}

运行结果：

总结：

看到这里，想必对这两种方法已经有了自己的认识。“试除法”中间不用把数值先存起来，节省了一定的空间，同时也没有那么耗时。
这是我了解到的两种方法，如有不对的地方，还望大家多多指点。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！