素数筛法-欧拉筛-个人理解()

素数筛法-欧拉筛-个人理解

素数筛选有两种流派,一种是埃氏筛法,一种是欧拉筛,由于埃氏筛法很简单,而且效率没有欧筛效率高。因此本文介绍欧拉筛。

本文用另一种角度讲解为何在时跳出循环,是个人理解,如有不正确的地方欢迎指点

if(i%b[j]==0)
#include<iostream>
using namespace std;
bool a[100001]={1,1};//i=0,i=1的时候都不是质数 ,所以直接标记
int b[100001];//存质数 
int k;	long long n;
int main()
{
	cin>>n;
	for(int i=2;i<=100001;i++)//这个意思是在100001里面找到质数并且标记 ,质数最小是2,所以i=2 
	{
		if (a[i]==0)	b[++k]=i;	//如果没有被标记为1,就是质数。我接下来会讲解为什么是质数。 
		for(int j=1;j<=k;j++)// //j小于当前所有的质数的个数
		{
			if(i*b[j]>100001)break;// 如果超出给出的范围,那么就退出循环 
			a[i*b[j]]=1;//用质数数依次×i,结果标记为合数(也就是标记为1)。 
			if(i%b[j]==0)break;//最关键的只标记一次 
		}	
	}
	for(int i=1;i<=n;i++) //你想查询的个数 
	{int m;
		cin>>m;//在100001里面输入你想查询的数
		if(a[m]==0)//如果没有被标记,就是质数,直接输出。 
		{
			cout<<m<<' ';
		}		
	}	
 } 

欧拉筛法和埃氏筛法一样,围绕{素数的倍数不是素数}筛选,但是欧拉筛为避免重复筛选,只会通过:最小素因子来消除。

对讲解:这时候不妨通过另一种视角,将变量在循环的内层和外层作用是不一样的,在外层:很好理解,就是循环查看某个数是不是素数。在内存:将理解成一个新的变量,它的作用是与相乘,从而筛选掉合数,关键是为什么会呢?如果,表示曾经被筛掉的,得赶紧退出,以防后面再被筛掉一次。

if(i%b[j]==0)break;
i
j
i
b[j]
break
i%b[j]==0
i
b[j]

这里i%b[j]要跳出循环了,要注意这里的b[j]代表的是第j个素数,注意我们这里的标记是素数的是:i*b[j] 。是第j个素数的i倍,如果不跳出,在后面某一个素数的i倍可能与现在的第j个素数的i倍重复,即后面某一个素数的i倍可能是第j个素数的i倍的倍数,导致重复。
举个例子,假如现在第j个素数是3,i=33,后面某一个素数是11。那么i是素数3的倍数,也是素数11的倍数,如果在时不退出的话,后面到了时它又要在计算一次,重复

这里i%b[j]要跳出循环了,要注意这里的b[j]代表的是第j个素数,注意我们这里的标记是素数的是:i*b[j] 。是第j个素数的i倍,如果不跳出,在后面某一个素数的i倍可能与现在的第j个素数的i倍重复,即后面某一个素数的i倍可能是第j个素数的i倍的倍数,导致重复。
举个例子,假如现在第j个素数是3,i=33,后面某一个素数是11。那么i是素数3的倍数,也是素数11的倍数,如果在时不退出的话,后面到了时它又要在计算一次,重复

33%3==0
33%11==0

欢迎指正!

参考

https://blog.csdn.net/m0_57071296/article/details/119873446

https://blog.csdn.net/gaoqiandr/article/details/126871298

acwing

————————

素数筛法-欧拉筛-个人理解

素数筛选有两种流派,一种是埃氏筛法,一种是欧拉筛,由于埃氏筛法很简单,而且效率没有欧筛效率高。因此本文介绍欧拉筛。

本文用另一种角度讲解为何在时跳出循环,是个人理解,如有不正确的地方欢迎指点

if(i%b[j]==0)
#include<iostream>
using namespace std;
bool a[100001]={1,1};//i=0,i=1的时候都不是质数 ,所以直接标记
int b[100001];//存质数 
int k;	long long n;
int main()
{
	cin>>n;
	for(int i=2;i<=100001;i++)//这个意思是在100001里面找到质数并且标记 ,质数最小是2,所以i=2 
	{
		if (a[i]==0)	b[++k]=i;	//如果没有被标记为1,就是质数。我接下来会讲解为什么是质数。 
		for(int j=1;j<=k;j++)// //j小于当前所有的质数的个数
		{
			if(i*b[j]>100001)break;// 如果超出给出的范围,那么就退出循环 
			a[i*b[j]]=1;//用质数数依次×i,结果标记为合数(也就是标记为1)。 
			if(i%b[j]==0)break;//最关键的只标记一次 
		}	
	}
	for(int i=1;i<=n;i++) //你想查询的个数 
	{int m;
		cin>>m;//在100001里面输入你想查询的数
		if(a[m]==0)//如果没有被标记,就是质数,直接输出。 
		{
			cout<<m<<' ';
		}		
	}	
 } 

欧拉筛法和埃氏筛法一样,围绕{素数的倍数不是素数}筛选,但是欧拉筛为避免重复筛选,只会通过:最小素因子来消除。

对讲解:这时候不妨通过另一种视角,将变量在循环的内层和外层作用是不一样的,在外层:很好理解,就是循环查看某个数是不是素数。在内存:将理解成一个新的变量,它的作用是与相乘,从而筛选掉合数,关键是为什么会呢?如果,表示曾经被筛掉的,得赶紧退出,以防后面再被筛掉一次。

if(i%b[j]==0)break;
i
j
i
b[j]
break
i%b[j]==0
i
b[j]

这里i%b[j]要跳出循环了,要注意这里的b[j]代表的是第j个素数,注意我们这里的标记是素数的是:i*b[j] 。是第j个素数的i倍,如果不跳出,在后面某一个素数的i倍可能与现在的第j个素数的i倍重复,即后面某一个素数的i倍可能是第j个素数的i倍的倍数,导致重复。
举个例子,假如现在第j个素数是3,i=33,后面某一个素数是11。那么i是素数3的倍数,也是素数11的倍数,如果在时不退出的话,后面到了时它又要在计算一次,重复

这里i%b[j]要跳出循环了,要注意这里的b[j]代表的是第j个素数,注意我们这里的标记是素数的是:i*b[j] 。是第j个素数的i倍,如果不跳出,在后面某一个素数的i倍可能与现在的第j个素数的i倍重复,即后面某一个素数的i倍可能是第j个素数的i倍的倍数,导致重复。
举个例子,假如现在第j个素数是3,i=33,后面某一个素数是11。那么i是素数3的倍数,也是素数11的倍数,如果在时不退出的话,后面到了时它又要在计算一次,重复

33%3==0
33%11==0

欢迎指正!

参考

https://blog.csdn.net/m0_57071296/article/details/119873446

https://blog.csdn.net/gaoqiandr/article/details/126871298

acwing