蓝桥杯每日一题—-素数筛

Posted on by hackdl

素数筛

素数筛的作用是筛选出[2,N]范围内的所有素数，本次主要讲解两种方法，分别是埃氏筛和欧拉筛。证明时会提到唯一分解定理，如果不知道的小伙伴可以先去学一学，那我们开始啦！

1.埃氏筛

主要思想：当找到一个素数时，利用该素数把该素数的所有倍数筛掉。

时间复杂度：

O

(

n

l

o

g

(

l

o

g

(

n

)

)

)

O(nlog(log(n)))

O(nlog(log(n)))

上代码，

    //每个数的最小质因子
    //pre[i]表示i的最小质因子
    book[1] = 1;//记录是否为素数，1表示不是素数
    book[0] = 1;
    for(int i =2;ibook.length;i++) {
        if(book[i]==0) {// i是素数，筛掉素数的倍数 i=2 6 = 2+2+2
            for(int j = i+i;jbook.length&&j>0;j+=i) {
                book[j] = 1;
            } 
        }
    }

问题：

  1. 为什么遍历到i时，若i没有被标记为合数（也就是没有被i前面的数筛掉），则一定是素数？

  2. 为什么for循环遍历到sqrt(N)就可以了？

先自己想一想哦，提示是唯一分解定理。

答案：

  1. 还记得唯一分解定理吗？一个正整数可以用若干个质数表示，假设当前正整数是n，它可以用质数

    p

    1

    ,

    p

    2

    .

    .

    .

    p

    k

    p_1,p_2…p_k

    p1​,p2​…pk​表示，

    p

    1

    ,

    p

    2

    .

    .

    .

    p

    k

    p_1,p_2…p_k

    p1​,p2​…pk​一定比q小。假设q是合数，那么遍历到q，q一定会被

    p

    1

    ,

    p

    2

    .

    .

    .

    p

    k

    p_1,p_2…p_k

    p1​,p2​…pk​筛掉。如果q是质数呢？他只能写出1*q的形式，它会被自己筛掉。

  2. 其实也就是证明sqrt(N)后面的合数一定会被小于sqrt(N)的数筛掉。设

    N

    N

    ​nN且

    a

    ∗

    b

    =

    n

    a*b=n

    a∗b=n,若a

    a

    an

    ​N

    ​，若a是素数，则n会被a筛掉，若a是合数，则a可以继续分解为更小的素数，而a和n都会被这个更小的素数筛掉，所以即便

    N

    N

    ​n，但是仅用小于

    N

    sqrt{N}

    N

    ​的数就可以把n筛掉，所以可以遍历到sqrt(N)。

2.欧拉筛

主要思想：埃氏筛的一部分时间耗在了重复的筛某些合数，比如18会被2和3筛掉。欧拉筛保证每个合数只被筛一次，因此也保证了

O

(

n

)

O(n)

O(n)的时间复杂度。

时间复杂度：
服务器托管网

O

(

n

)

O(n)

O(n)

上代码，

 int count = 0;
 for (int i = 2; i  20000005; i++) {//线性
 if (!visit[i]) {//如果i是一个质数
     prime[count++] = i;//记录当前已经找出来的所有的质数
 }
 for (int j = 0; j  count && i * prime[j]  20000005; j++) {
     visit[i * prime[j]] = true;//用prime[j]筛掉了i * prime[j]。
     if (i % prime[j] == 0) break;//保证每个合数只被最小的质因子筛掉
  }
 }

问题：

  1. 为什么if语句满足后可以提前退出循环？
  2. 两个for循环嵌套如何实现的线性复杂度？

先自己想一想哦，提示是prime[j]是i的因子，你可以把式子写出来看看。

再讲答案之前先来捋一捋欧拉筛的结构，因为它不像埃氏筛那么直接。

首先一个for循环，接着如果当前的i是素数，则用另一个数组prime存一下，这个数组只存素数。

再来一个for循环，这个for循环就是用来筛合数的，遍历之前找到的所有素数，然后筛掉

p

r

i

m

e

[

j

]

∗

i

prime[j]*i

prime[j]∗i。当满足if语句时，这一轮的筛合数可以提前退出了。

答案：

  1. 若此时if语句条件满足了，则prime[j]是i的因子，因此有

    i

    =

    k

    ∗

    p

    r

    i

    m

    e

    [

    j

    ]

    i=k*prime[j]

    i=k∗prime[j]。如果此时没有退出for循环，会有

    p

    r

    i

    m

    e

    [

    j

    +

    1

    ]

    ∗

    i

    prime[j+1]*i

    prime[j+1]∗i被prime[j+1]筛掉。

    p

    r

    i

    m

    e

    [

    j

    +

    1

    ]

    ∗

    i

    =

    p

    r

    i

    m

    e

    [

    j

    +

    1

    ]

    ∗

    k

    ∗

    p

    r

    i

    m

    e

    [

    j

    ]

    =

    k

    ‘

    ∗

    p

    r

    i
    服务器托管网

    m

    e

    [

    j

    ]

    prime[j+1]*i=prime[j+1]*k*prime[j]=k^`*prime[j]

    prime[j+1]∗i=prime[j+1]∗k∗prime[j]=k‘∗prime[j]，这说明了什么？说明被prime[j+1]筛掉的

    p

    r

    i

    m

    e

    [

    j

    +

    1

    ]

    ∗

    i

    prime[j+1]*i

    prime[j+1]∗i也会被prime[j]筛掉，这就重复筛了，怎么办？我们让每个数都被其最小的质因子筛掉，那么这里prime[j]就是

    p

    r

    i

    m

    e

    [

    j

    +

    1

    ]

    ∗

    i

    prime[j+1]*i

    prime[j+1]∗i最小的质因子，因此j就不继续增大了，直接退出该循环。

  2. 因为保证了每个数只被筛一次，第二个for循环总共被执行n次，所有的数被筛完代码也就结束了。

例题

埃氏筛——最小质因子之和

参考代码：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Scanner;

public class 最小质因子之和Easy {
public static void main(String[] args) throws IOException{
    //进行预处理
    f();//求2-n每个数对应的最小质因子
    sum();//求前缀和数组
    StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); 
    Scanner scanner = new Scanner(System.in);
    sc.nextToken();
    int t = (int)sc.nval;
    while(t-- >0) {
        sc.nextToken();
        int n = (int)sc.nval;
        System.out.println(res[n]);
    }
}
static int book[] = new int[4000000];
static int pre[] = new  int[4000000];
private static void f() {//埃氏筛模板
    //每个数的最小质因子
    //pre[i]表示i的最小质因子
    book[1] = 1;//记录是否为素数，1表示不是素数
    book[0] = 1;
    for(int i =2;ibook.length;i++) {
        if(book[i]==0) {// i是素数，筛掉素数的倍数 i=2 6 = 2+2+2
            pre[i] = i;//求的是质数的最小质因子
            for(int j = i+i;jbook.length&&j>0;j+=i) {
                if(book[j]==0) {
                    pre[j] =i;
                }
                book[j] = 1;
            }
            
        }
    }
    
}
static long res[] = new long[4000000];
private static void sum() {
    //一次求出i 2- n
    // 2-i的最小质因子之和，前缀和数组可以在O（n）
    for(int i=2;ires.length;i++) {
        res[i] = res[i-1]+pre[i];
    }
}
}

欧拉筛——最小质因子之和困难版

参考代码：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class 最小质因子之和Hard {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] prime = new int[20000005];
        int[] f = new int[20000005];
        boolean[] visit = new boolean[20000005];
        int count = 0;
        for (int i = 2; i  20000005; i++) {//线性
            if (!visit[i]) {//如果i是一个质数
                prime[count++] = i;
                f[i] = i;
            }
            for (int j = 0; j  count && i * prime[j]  20000005; j++) {
                visit[i * prime[j]] = true;
                f[i * prime[j]] = prime[j];
                if (i % prime[j] == 0) break;
            }
        }
        long[] sum = new long[20000005];//前缀和数组
        for (int i = 2; i  f.length; i++) {
        	//System.out.println(f[i]);
            sum[i] = sum[i - 1] + f[i];
        }
        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            int n = Integer.parseInt(br.readLine());
            System.out.println(sum[n]);
        }
    }
}

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

相关推荐: 微信小程序：发送小程序订阅消息

文档：小程序订阅消息（用户通过弹窗订阅）开发指南 目录 步骤一：获取模板 ID 步骤二：小程序端获取参数 2.1、获取消息下发权限 2.2、获取登录凭证（code） 步骤三：后端调用接口下发订阅消息 3.1、获取OPENID 3.2、获取ACCESS_TOKE…

服务器托管，北京服务器托管，服务器租用，机房机柜带宽租用

服务器托管

咨询：董先生

电话13051898268 QQ/微信93663045！

上一篇:
下一篇: