Keli365

Appearance

数论入门 - 质数筛法 ​

一、课程目标 ​

  1. 质数查找问题
  2. 埃氏筛法
  3. 欧拉筛法

二、目标详解 ​

质数查找问题 ​

一般为求区间[L, R]里的质数个数。

素数：一个大于1的自然数，除了1和它本身以外不再有其他因数的数称为素数。 合数：一个大于1的自然数，除了1和它本身以外还有其他因数的数为合数。

1、枚举法 ​

朴素算法：枚举（暴力），判断是否为质数，复杂度为O(n * sqrt(n))。

c++
//自定义判断函数
bool isPrime(int x) {
  if(x < 2) return false;
  //int t = sqrt(x); //由于下面的sqrt(x)会多次计算，所以可以先计算一次，省略一丢丢时间
  for(int i=2; i<=sqrt(x); i++)
    if(x%i == 0)
      return false;
  return true;
}

//逐一判断
for(int i=2; i<=n; i++)
  if(isPrime(i))
    cnt++;

2、埃氏筛法 ​

埃氏筛法，全名埃拉托斯特尼筛法，是一种古老且简单的用来找出一定范围内所有的质数的算法，公元前250年由希腊数学家埃拉托斯特尼提出。

**核心思想：**质数的整数倍一定是合数，标记出所有的合数，剩下的就是质数

筛选过程：

从小到大遍历每个数x，如果x是质数，就把x的倍数都进行标记，剩下的就是质数。

模拟过程：

i：2345678910
2:23~~4~~5~~6~~7~~8~~9~~10~~
3:23-5-7-~~9~~-
...

此算法用到了双重循环，但由于内层循环的步长为i，时间复杂度可看成O(nloglogn)。

c++
//埃氏筛 
#include <bits/stdc++.h>
using namespace std;
bool isPrime[1000005];
int n;
int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    isPrime[i] = 1;
  }
  isPrime[0] = 0;
  isPrime[1] = 0;
  for (int i = 2; i <= n; i++) {
    if (isPrime[i]) {
      for (int j = i*2; j <= n; j+=i) { //标记质数的倍数 
        isPrime[j] = 0;
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    if (isPrime[i]) {
      cout << i << " ";
    }
  }
  return 0;
}


//使用vector代码1
for(int i=2; i<=n; i++) {
  if (isPrime[i]) {//不是合数，也就是质数
    primes.push_back(i);
    for(int j=2*i; j<=n ; j=j+i)
      isPrime[j] = false;
  }
}

//代码2,一丢丢优化
for(int i=2; i*i<=n; i++) { //i*i能减少计算量，比如i为3的时候，3*2 为 6，其实 6 已经被 2*3 标记了，所以i*i
  if (isPrime[i]) {//不是合数，也就是质数
    primes.push_back(i);
    for(int j=i*i; j<=n ; j=j+i)
      isPrime[j] = false;
  }
}

3、欧拉筛法 ​

在筛法模拟里会看到存在大量的重复筛，比如6即被2筛掉、也被3筛掉， 如果每个合数都只被一个数筛掉，那么这个算法显然就是O(n)的算法，即线性筛法。

前置知识：

整数唯一分解定理：

  • 任何大于1的正整数n都可以唯一分解为有限个质数的乘积；
  • 任何合数都有他对应的一个最小质因子（合数=最小质因数×另一个数）；

合数只通过这个最小质因子将其标记这样就避免了重复标记。

核心思想：

每个数都只被它的最小质因子筛掉。

筛选过程：

  • 1、对每个数 x，将小于等于 x 的质数乘以 x 标记为合数。
  • 2、如果某个质数是 x 的因子，则停止（后面的不要筛了）

算法解释：

  • 1、对于某个数 x，假设已经找到 m 个质数：p0、p1、...、pm<=x， 计划将 x 和 这些质数的乘积都筛掉。
  • 2、但如果 x 存在一个质因子，假设为 px，即 x=px∗k 那么对于 px 到 pm 之间的任何质数 p，都有 x∗p=px∗k∗p=px∗(k∗p) 也就是说后面肯定会有一个比 x 大的数 y = (k*p)，也会筛掉 y * px = x * p
  • 例子：6 以前的质数有 2,3,5 首先 6 * 2 = 12，那么 12 会进行合数标记，但是 6 * 3 = 18 并不会进行标记，因为还有更大的一个数，9 * 2 = 18，所以直接结束掉即可，同样的，如果是9,9之前的质数有2,3,5,7 筛选的 9*2=18,9*3=27之后便结束，因为9*4=36，但36可以由18来除，36=18*2

模拟过程：

i质数筛
224
32, 36, 9
42,38
52,3,510, 15, 25
62,3,512
72,3,5,714,21,35,49
82,3,5,716
92,3,5,718,27
...

由于每个数都只有其最小质因子乘以某个x筛掉，所以这个算法为O(n)。

c++
//写法1
for(int i=2; i<=n; i++) {
  if(isPrime[i]) primes.push_back(i);
  for(int j=0; j<primes.size(); j++) {
    int p = primes[j];
    if(i * p > n) break;
    isPrime[i * p] = false;
    if(i%p == 0) break;
  }
}

//写法2
for(int i=2; i<=n; i++) {
  if(isPrime[i]) primes.push_back(i);
  for(int j=0; j<primes.size() && i*primes[j] <= n; j++) { //这里的i刚好是充当了质数的不同倍数
    isPrime[i * primes[j]] = false;
    if(i % primes[j] == 0) break;
  }
}

练习-找质数(枚举) ​

一、实验目标 ​

输入n，找出<=n的所有质数。

输入格式：

  • 一个正整数n

输出格式：

  • 第一行一个数字，表示质数个数k
  • 第二行k个质数，从小到大，空格隔开

输入样例1：

text
10

输出样例1：

text
4
2 3 5 7

数据范围：

  • n<=10^7

二、分析 ​

1、思路 ​

首先实现一个函数isPrime，用来判断某个数是否是质数。

然后枚举2..n，调用isPrime函数进行判断，如果是质数就加到一个动态数组。

最后输出动态数组的长度，和每个元素。

2、动态数组-下标法 ​

可以用一个固定长度的数组和一个下标last来存储动态，如：

c++
int a[N], last;//N足够大

保存：

c++
a[++last] = i;

输出：

c++
cout<<last<<endl; //last是长度
for(int i=1; i<=last; i++)
  cout<<a[i]<<" ";

3、动态数组-vector ​

也可以使用 STL 里提供的 vector 类，如：

c++
vector<int> primes;

保存时用 push_back 方法：

c++
primes.push_back(i);

输出：

c++
cout << primes.size() << endl; //长度用size()方法
for (int i=0; i<primes.size(); i++) //下标从0开始
  cout << primes[i] << " ";

演示-找质数(埃氏筛法) ​

一、实验目标 ​

输入n，找出1~n的所有质数。

输入格式：

  • 一个正整数n

输出格式：

  • 第一行一个数字，表示质数个数k
  • 第二行k个质数，从小到大，空格隔开

输入样例1：

text
10

输出样例1：

text
4
2 3 5 7

数据范围：

  • n<=10^7

二、分析 ​

1、思路 ​

从2开始，每个质数往后筛自己的倍数，设置为合数。

筛完以后剩下的就是质数，将之存储到动态数组里，输出。

时间复杂度：O(n log logn)

2、桶数组 ​

bool isPrime[N] 是桶数组，用来标记 i 是否为质数。

3、动态数组 ​

用vector实现。

c++
#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;

const int N = 1e7+5;
int n;
bool isPrime[N];
vector<int> primes;

int main() {
  cin>>n;
  for(int i=1; i<=n; i++)//默认都是质数
    isPrime[i] = true;
  
  //埃氏筛法：每个数筛自己的倍数
  for(int i=2; i*i<=n; i++) {
    if (isPrime[i]) {//不是合数，也就是质数
      primes.push_back(i);
      for(int j=i*i; j<=n ; j=j+i)
            isPrime[j] = false;
    }
  }
    
  cout<<primes.size()<<endl;
  for(int i=0; i<primes.size(); i++)
    printf("%d ", primes[i]);
  cout<<endl;
  return 0;
}

演示-找质数(欧拉筛法) ​

一、实验目标 ​

输入n，找出<=n的所有质数。

输入格式：

  • 一个正整数n

输出格式：

  • 第一行一个数字，表示质数个数k
  • 第二行k个质数，从小到大，空格隔开

输入样例1：

text
10

输出样例1：

text
4
2 3 5 7

数据范围：

  • n<=10^7

二、分析 ​

1、思路 ​

从2开始，每个数被最小的质因子筛掉。

时间复杂度：O(n)

2、桶数组 ​

bool isPrime[N]是桶数组，用来标记i是否为质数。

3、动态数组 ​

用vector实现。

c++
#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;

const int N = 1e7+5;
int n;
bool isPrime[N];
vector<int> primes;

int main() {
  cin>>n;
  for(int i=1; i<=n; i++)//默认都是质数
    isPrime[i] = true;
  
  //欧拉筛法：每个数x筛去x * <=最小质因子的质数
  for(int i=2; i<=n; i++) {
    if(isPrime[i])
      primes.push_back(i);
    for(int j=0; j<primes.size(); j++) {
      int p = primes[j];
      if(i*p > n) break;
      isPrime[i * p] = false;
      if(i%p == 0) break;
    }
  }
  
  cout<<primes.size()<<endl;
  for(int i=0; i<primes.size(); i++)
    printf("%d ", primes[i]);
  cout<<endl;
  return 0;
}

练习-哥德巴赫猜想 ​

题目描述 ​

1742年6月7日哥德巴赫写信给当时的大数学家欧拉，正式提出了以下的猜想：任何一个大于9的奇数都可以表示成3个质数之和。

质数是指除了1和本身之外没有其他约数的数，如2和11都是质数，而6不是质数，因为6除了约数1和6之外还有约数2和3。需要特别说明的是1不是质数。这就是哥德巴赫猜想。

欧拉在回信中说，他相信这个猜想是正确的，但他不能证明。从此，这道数学难题引起了几乎所有数学家的注意。哥德巴赫猜想由此成为数学皇冠上一颗可望不可及的“明珠”。现在请你编一个程序验证哥德巴赫猜想。

输入输出格式 ​

输入格式：

  • 一行一个正奇数n

输出格式：

  • 一行空格隔开三个质数（最后一个质数后无空格），如果方案不唯一，输出第一个数最小的方案，如果第一个数最小的方案仍不唯一，输出第二个数最小的方案。

输入输出样例 ​

输入样例：

text
11

输出样例：

text
2 2 7

测试点 ​

测试点：5个测试点，每个测试点得20分。

测试限制：每个测试点时间限制1s，内存限制128M。

数据范围：

  • 40%的数据：9 < n < 10^5
  • 80%的数据：9 < n < 10^6
  • 100%的数据：9 < n < 10^7

习题 ​

1061

2462

2136

2071

1549

2007

1942

Copyright © 2024 Keli365