质数筛和整数分块

Nannan Lv5
  2023-11-02 17:13 2023-11-02 17:13 Created   2024-09-30 19:25:37 2024-09-30 19:25:37 Updated      

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不用看，跳过
… …
没有被筛去的一定是质数，因为它没有被比它小的任何一个数筛去，说明它不是任何一个数的倍数，所以一定是质数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#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.线性筛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#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.区间筛

给两个数字，求中的所有素数。
为了防止输出过大和防止打表，
给定,，输出这些素数的异或和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#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;
}

4.大素数的判断miller_rabin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<iostream>
using namespace std;

typedef long long ll;
ll ksm(ll a,ll b,ll mod)
{
	ll ans = 1,base = a;
	while(b>0)
	{
		if(b&1)
		{
			ans *= base;
			ans %= mod;
		}
		base *= base;
		base%=mod;
		b>>=1;
	}
	return ans;
}

bool witness(ll a,ll n)
{
	ll u = n-1;
	int t = 0;
	//2^t*u
	while((u&1)==0)u>>=1,t++;
	ll x1,x2;
	x1 = ksm(a,u,n);//a^u mod n
	for(int i = 1;i<=t;i++)
	{
		x2 = ksm(x1,2,n);
		if(x2==1&&x1!=1&&x1!=n-1)return true;
		x1 = x2;
	}
	if(x1!=1)return true;
	return false;
}

int miller_rabin(ll n,ll s)
{
	if(n<2)return 0;
	if(n==2)return 1;
	if(n%2==0)return 0;
	for(int i = 0;i<s&&i<n;i++)
	{
		ll a = rand()%(n-1)+1;
		if(witness(a,n))return 0;
	}
	return 1;
}


int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int m;
	while(cin>>m)
	{
		int cnt = 0;
		for(int i = 1;i<=m;i++)
		{
			ll n;
			cin>>n;
			int s = 50;
			cnt += miller_rabin(n,s);
		}
		cout<<cnt<<"\n";
	}
	return 0;
}

补充1：单个素数判断

1.试除法 

1
2
3
4
5
6
7
8
inline bool is_prime(int x){
    if(x < 2)
        return false;
    for(register int i = 2; i * i <= x; ++ i)
        if(x % i == 0)
            return false;
    return true;
}

2.法 

1
2
3
4
5
6
7
bool isPrime(ll n){
    if(n == 2 || n == 3 || n == 5)return 1;
    if(n % 2 == 0 || n % 3 == 0 || n % 5 == 0 || n == 1) return 0;
    ll c = 7, a[8] = {4,2,4,2,4,6,2,6};
    while(c * c <= n) for(auto i : a){if(n % c == 0)return 0; c += i;}
    return 1;
}

3.预处理法

考虑预处理出以内的素数，其中为以内的素数个数。

4.Miller-Rabin 判定法

补充2：素数的性质

  1. 质数的个数为
  2. 范围内互质的数最多个。
  3. 若一个数是一个合数，必然存在个因子，,假设，则。因此对于任意一个合数，必然存在一个小于等于的质因子。
  4. 若,且是合数，则一定存在，使得能整除，其中。

例题：质数距离（筛素数）

题意：给定两个整数 L 和 U，你需要在闭区间 [L,U] 内找到距离最接近的两个相邻质数 C1 和 C2（即 C2−C1 是最小的），如果存在相同距离的其他相邻质数对，则输出第一对。
同时，你还需要找到距离最远的两个相邻质数 D1 和 D2（即 D1−D2 是最大的），如果存在相同距离的其他相邻质数对，则输出第一对。
思路：利用性质3,4。

步骤：

  1. 用筛法求出区间内的素数。
  2. 对于内的每一个素数，将区间内所有的倍数全部筛掉。经过了这样的筛选后，区间内剩下的数就都是质数了。
  3. 注意：要筛掉内所有的倍数，我们只需要找到的的最小倍数：，只后每次即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,INF=0x3f3f3f3f;
int prime[N],cnt;
bool st[N];
void init(int n)				//线筛求素数
{
    cnt=0;
    memset(st,0,sizeof st);
    for(int i=2;i<=n;i++)
    {
        if(!st[i]) prime[cnt++]=i;
        for(int j=0;prime[j]*i<=n;j++)
        {
            st[prime[j]*i]=true;
            if(i%prime[j]==0) break;
        }
    }
}
int main()
{
    int l,r;
    while(cin>>l>>r)				//有多组测试样例，因此要用while读入
    {
        init(50000);				//初始化
        memset(st,0,sizeof st);		//因为后面我们会复用st[]和prime[]数组，因此这里要重新清空st[]
        for(int i=0;i<cnt;i++)
        {
            LL p=prime[i];					//筛掉[l,r]区间内所有p的倍数（最小要从2开始）
            for(LL j=max(2*p,(l+p-1)/p*p);j<=r;j+=p)
                st[j-l]=true;
        }
        cnt=0;
        for(int i=0;i<=r-l;i++)				//将剩下的没被筛掉的数放入存入prime[]中（注意要把1特判掉）
            if(!st[i]&&i+l>1) prime[cnt++]=i+l;
        
        if(cnt<2) puts("There are no adjacent primes.");
        else {
            int maxp=1,minp=1;
            for(int i=2;i<cnt;i++)				//枚举区间内所有的素数，记录距离的最小值与最大值
            {
                int d=prime[i]-prime[i-1];
                if(prime[maxp]-prime[maxp-1]<d) maxp=i;
                if(prime[minp]-prime[minp-1]>d) minp=i;
            }
            printf("%d,%d are closest, %d,%d are most distant.\n",
                prime[minp-1],prime[minp],prime[maxp-1],prime[maxp]);
        }
    }
    return 0;
}

二、Integer_block

整数分块核心代码

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

eg1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// 给定一个数字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;
}
  • Title: 质数筛和整数分块
  • Author: Nannan
  • Created at : 2023-11-02 17:13:00
  • Updated at : 2024-09-30 19:25:37
  • Link: https://redefine.ohevan.com/2023/11/02/四、Prime sieving and integer blocking/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
质数筛和整数分块
  1. Prime sieving and Integer blocking
    1. 一、Prime number sieve method
      1. 1.埃氏筛O(nloglogn)
      2. 2.线性筛
      3. 3.区间筛
      4. 4.大素数的判断miller_rabin
    2. 补充1：单个素数判断
      1. 1.试除法
      2. 2.法
      3. 3.预处理法
      4. 4.Miller-Rabin 判定法
      5. 补充2：素数的性质
      6. 例题：质数距离（筛素数）
    3. 二、Integer_block
      1. 整数分块核心代码
        1. eg1.