526互联

[数论]素数筛和整数分块

发布时间 2023-06-17 09:08:10作者: nannan4128

Prime sieving and Integer blocking

一、Prime number sieve method

1.埃氏筛O(nloglogn)

从 2 开始，2是质数，那么2的倍数：4、6、8、10、12、14、16... 肯定不是质数
3是质数，那么3的倍数：6、9、12、15、18、21..... 肯定不是质数
4已经被筛去了（即被置为false），不是质数，那么4的倍数肯定被它的因子筛过，所以4不用看，跳过
... ...
没有被筛去的一定是质数，因为它没有被比它小的任何一个数筛去，说明它不是任何一个数的倍数，所以一定是质数。

#include <iostream>
using namespace std;
#include <cstring>      
 
const int N = 1e5;		
bool isPrime[N + 5];	
int primes[N + 5];		
int cnt = 0;	

void aiPrime()
{
	memset(isPrime,true,sizeof(isPrime));		
 
	for (int i = 2;i <= N / i;i++)//注意这里 i <= N / i就可以
	{
		if (isPrime[i])		//如果当前数是质数，那么将它的倍数都标记为 false
		{			
			for (int j = i * i; j <= N; j += i)
			{
				isPrime[j] = false;
			}
		}
	}
 
	for (int i = 2; i <= N; i++)		//将质数放入primes数组
	{
		if(isPrime[i])
			primes[cnt++] = i;
	}
}
 
int main()
{
	aiPrime();
	cout << cnt << endl;
	return 0;
}

2.线性筛

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn =1000010;
bool is_pri[maxn];
int pri[maxn];
int cnt;

void init(int n)
{
	memset(is_pri, true, sizeof(is_pri));
	is_pri[1] = false;
	cnt = 0;
	for (int i = 2; i <= n; i++)
	{
		if (is_pri[i])
			pri[++cnt] = i;
		for (int j = 1; j <= cnt && i * pri[j] <= n; j++)
		{
			is_pri[i * pri[j]] = false;
			if (i % pri[j] == 0)break;            
		}
	}
}

3.区间筛

给两个数字\(l,r\)，求\(l~r\)中的所有素数\(p\)。
为了防止输出过大和防止打表，
给定\(a\),\(b\)，输出这些素数\((a*p+b)\bmod 2^{32}\)的异或和。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned int u64;
const int N =10000100;
bool is_pri[N];
int pri[N/5];
int cnt;
ll l,r;
bool vis[N];
u64 ans = 0,a,b;
void init(int n)
{
	memset(is_pri, true, sizeof(is_pri));
	is_pri[1] = false;
	cnt = 0;
	for (int i = 2; i <= n; i++)
	{
		if (is_pri[i])
			pri[++cnt] = i;
		for (int j = 1; j <= cnt && i * pri[j] <= n; j++)
		{
			is_pri[i * pri[j]] = false;
			if (i % pri[j] == 0)break;            
		}
	}
}



int main()
{
	init(N);
	cin>>l>>r>>a>>b;
	for(int i = 1;i<=cnt;i++)
	{
		int p = pri[i];
		//cout<<p<<endl;
		//筛掉l~r里面p的倍数
		//从<=r的第一个p的倍数开始筛
		for(ll x = r/p*p;x>=l&&x>p;x-=p)
			vis[x-l] = 1;

	}
	
	for(ll i = max(2ll,l);i<=r;i++)
	{
		if(!vis[i-l])
		{
			ans = ans^(a*(u64)i+b);
		}
	}
	cout<<ans<<endl;
	return 0;
}

二、Integer_block

整数分块核心代码

for(ll l = 1;l<=n;l++)
{
	ll d = n/l,r = n/d;
	//l ... r这一段n/x都==d
	l = r;
}

eg1.\(\sum_{i = 1}^{n}(n \bmod i)\)

// 给定一个数字n，求∑(i=1~n)(n mod i)。
// 答案可能很大，输出对2^60取模的结果。
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long u64;
//n mod i = n-n/i*i
//对于l,r这一段,它的n/i都是d
//那这一段值等于n-d*i,是等差数列
u64 n,sum;

int main()
{
	cin>>n;
	for(u64 l = 1;l<=n;l++)
	{
		u64 d = n/l,r = n/d;
		sum += (n-l*d+n-r*d)*(r-l+1)/2;
		l = r;
	}
	cout<<sum%(1ull<<60)<<endl;
	return 0;
}