简单素数筛

简单素数筛

今天，我看了一些数学知识，而数论是比较主要的，而素数筛是其中重要的一个，现在来介绍一下简单素数筛

首先来，普及一下素数的概念

若一个正整数无法被除了1和它本身之外的任何自然数整除，则称该数为素数，也称质数（或素数），否则称该正整数为合数。

通过介绍质数（下文统称质数）的概念，我们知道了一种判断质数的方法

通过枚举：这种方法的速度太慢了，因此我们需要更快的方法

ps：即使从1枚举到根号n也是很慢的

所以我们要引进一种好方法

就是大于二的所有数的倍数都是合数，那就好办了，我们可以从2开始（先初始化一个v[]数组的所有元素为零）2的倍数都是合数，标记v[i*j]为一,3的倍数都是合数，标记为1……

以此类推，我们就可以得出答案了

下面有一道例题

---

题目描述

给定一个范围N，你需要处理M个某数字是否为质数的询问（每个数字均在范围1-N内）

输入格式

第一行包含两个正整数N、M，分别表示查询的范围和查询的个数。

接下来M行每行包含一个不小于1且不大于N的整数，即询问该数是否为质数。

输出格式

输出包含M行，每行为Yes或No，即依次为每一个询问的结果。

输入输出样例

输入 #1

100 5
2
3
4
91
97

输出 #1

Yes
Yes
No
No
Yes

说明/提示

时空限制：500ms 128M

数据规模：

对于100%的数据：N<=10000，M<=10000

样例说明：

N=100，说明接下来的询问数均不大于100且不小于1。

所以2、3、97为质数，4、91非质数。

故依次输出Yes、Yes、No、No、Yes。

---

这道题就是一道标准的筛素数的题，因为它要访问多个数啊，不做素数筛不可以啊，所以经过努力，我写出了代码

#include <iostream>
#include <cstring>
using namespace std;
int v[10000005];//记录用
int n,m;
int p;
void primes(int n)//简单素数筛函数
{
	memset(v,0,sizeof(v));
	for(int i=2;i<=n;i++)
	{
		if(v[i])
		continue;
		for(int j=i;j<=n/i;j++)
		v[i*j]=1; 
	}
}
int main()
{
	cin>>n>>m;
	primes(n);//调用函数
	for(int i=1;i<=m;i++)
	{
		cin>>p;
		if(v[p])
		cout<<"No"<<endl;
		else 
		cout<<"Yes"<<endl;
	}
	return 0;
}

这就是简单素数筛，你get到了吗？

下集预告：高级素数筛（或其他的）