素数&素数筛法

数论基础

素数&素数筛法

我们先回顾一下素数的定意：素数（Prime number，又称质数），指在大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的数（也可定义为只有1与该数本身两个正因数的数）。

素数的判断

CPP

if(n==1)
{
    return false;
}
else
{
     for(int i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            return false;
        }
    }
    return true;
}

可得判断依据：如果2~ sqrt(n)中有n的约数，则n是合数，否则n是素数。

素数筛法

1.Eratosthenes筛法

• 简称埃氏筛，也称素数筛。简单且历史悠久的筛法，用来找出一定范围内所有的素数。

• 算法思想：从2开始，将每个素数的各个倍数，标记成合数。

• 一个素数的各个倍数，是一个差为此素数本身的等差数列。

• 此为这个筛法和试除法不同的关键之处，后者是以素数来测试每个待测数能否被整除。

• 这样被标记为true的数就是素数

代码实现

CPP

bool vis[1145145];
void Eratosthenes(int n)
{
	int i,j;
	vis[0]=vis[1]=false;
	for(i=2;i<=n;i++)
	{
		vis[i]=true;
	}
	for(i=2;i*i<=n;i++)
	{
		if(vis[i])
		{
			for(j=i*i;j<=n;j+=i)
			{
				vis[j]=false;
			}
		}
	}
}

2.欧拉筛法(线性筛)

在埃式筛法中，很多数明显被标记了多次，怎么优化呢？

• 枚举2~n中的每一个数i

• 如果i是素数就保存到素数表中

• 利用i和素数表中的素数pr[j]去筛除i * pr[j]，为了确保i*pr[j]只被素数pr[j]筛除过一次，要确保pr[j]是i * pr[j]中的最小素因子，即i中不能有比pr[j]更小的素因子。

• 每次i++时筛掉部分质数倍数，而非一次性筛完所有倍数。

• 关键在于理解筛法过程中避免重复筛除，从而实现优化。

代码实现

CPP

bool vis[1145145]; 
int pr[1145145];
void getpr(int n)
{
	int i,j,cnt=0;
	for(i=2;i<=n;i++)
	{
		if(vis[i]==false)
		{
			pr[++cnt]=i;
		}
		for(j=1;j<=cnt&&i*pr[j]<=n;j++)
		{
			vis[i*pr[j]]=true;
			if(i%pr[j]==0)
			{
				break;
			}
			//当i能整除pr[j]，那么i*pr[j+1]这个合数肯定会被pr[j]乘意某个数筛掉。
			//因为i中含有pr[j]，pr[j]比pr[j+1]小 
		}
	}
}

下一次再写个模运算与同余……

讨论操作

回复

相关推荐

素数&素数筛法