蓝桥杯JAVA-12.筛质数（JAVA实现）

本文最后更新于：February 25, 2022 pm

积土成山，风雨兴焉；积水成渊，蛟龙生焉；积善成德，而神明自得，圣心备焉。故不积跬步，无以至千里，不积小流无以成江海。齐骥一跃，不能十步，驽马十驾，功不在舍。面对悬崖峭壁，一百年也看不出一条裂缝来，但用斧凿，能进一寸进一寸，能进一尺进一尺，不断积累，飞跃必来，突破随之。

目录

朴素筛法

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
import java.io.*;
import java.math.BigInteger;
import java.util.*;


/**
 * @Author DragonOne
 * @Date 2021/12/5 21:27
 * @墨水记忆 www.tothefor.com
 */
public class Main {
    public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
    public static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
    public static Scanner sc = new Scanner(System.in);
    public static int monthes[]= {0,31,28,31,30,31,30,31,31,30,31,30,31};//一年中的12个月每月的天数
    public static int maxd = 5000000+7;
    public static int INF = 0x3f3f3f3f;
    public static int mod = 998244353;

    public static int cnt = 1;
    public static int[] primes = new int[maxd]; //存储所有素数
    public static boolean[] vis = new boolean[maxd]; //判断是否被筛掉


    public static void get_primes(int n){
        for(int i=2;i<=n;++i){
            if(vis[i]) continue;
            primes[cnt++]=i;
            for(int j=i+i;j<=n;j+=i){
                vis[j]=true;
            }
        }
    }

    public static void main(String[] args) throws Exception {

        int n = 30000;
        get_primes(n);
        System.out.println(primes[2019]);


        closeAll();
    }


    public static int gcd(int a,int b){ // 不需要判断a和b的大小
        while(b>0){
            a%=b;b^=a;a^=b;b^=a;
//           while(b^=a^=b^=a%=b);
        }
        return a;
//        return (a % b == 0) ? b : gcd(b, a%b);
    }

    public static int log(int x){ //log方法是以2为底,求x的对数.而java自带的log是以e为底的
        return (int) (Math.log(x)/Math.log(2));
    }

    public static void cinInit(){
        cin.wordChars('a', 'z');
        cin.wordChars('A', 'Z');
        cin.wordChars(128 + 32, 255);
        cin.whitespaceChars(0, ' ');
        cin.commentChar('/');
        cin.quoteChar('"');
        cin.quoteChar('\'');
        cin.parseNumbers(); //可单独使用还原数字
    }
    public static int nextInt() throws Exception {
        cin.nextToken();
        return (int) cin.nval;
    }
    public static long nextLong() throws Exception {
        cin.nextToken();
        return (long) cin.nval;
    }
    public static double nextDouble() throws Exception {
        cin.nextToken();
        return cin.nval;
    }
    public static String nextString() throws Exception {
        cin.nextToken();
        return cin.sval;
    }
    public static void closeAll() throws Exception {
        cout.close();
        in.close();
        out.close();
    }
}

线性筛法

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
import java.io.*;
import java.math.BigInteger;
import java.util.*;


/**
 * @Author DragonOne
 * @Date 2021/12/5 21:27
 * @墨水记忆 www.tothefor.com
 */
public class Main {
    public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
    public static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
    public static Scanner sc = new Scanner(System.in);
    public static int monthes[]= {0,31,28,31,30,31,30,31,31,30,31,30,31};//一年中的12个月每月的天数
    public static int maxd = 5000000+7;
    public static int INF = 0x3f3f3f3f;
    public static int mod = 998244353;

    public static int cnt = 1;
    public static int[] primes = new int[maxd]; //存储所有素数
    public static boolean[] vis = new boolean[maxd]; //判断是否被筛掉


    public static void get_primes(int n){
        for(int i=2;i<=n;++i){
            if(!vis[i]) primes[cnt++]=i;
            for(int j=1;primes[j]<=n/i;j++){
                vis[i*primes[j]]=true;
                if(i%primes[j]==0) break;
            }
        }
    }

    public static void main(String[] args) throws Exception {

        int n = 30000;
        get_primes(n);
        System.out.println(primes[2019]);


        closeAll();
    }


    public static int gcd(int a,int b){ // 不需要判断a和b的大小
        while(b>0){
            a%=b;b^=a;a^=b;b^=a;
//           while(b^=a^=b^=a%=b);
        }
        return a;
//        return (a % b == 0) ? b : gcd(b, a%b);
    }

    public static int log(int x){ //log方法是以2为底,求x的对数.而java自带的log是以e为底的
        return (int) (Math.log(x)/Math.log(2));
    }

    public static void cinInit(){
        cin.wordChars('a', 'z');
        cin.wordChars('A', 'Z');
        cin.wordChars(128 + 32, 255);
        cin.whitespaceChars(0, ' ');
        cin.commentChar('/');
        cin.quoteChar('"');
        cin.quoteChar('\'');
        cin.parseNumbers(); //可单独使用还原数字
    }
    public static int nextInt() throws Exception {
        cin.nextToken();
        return (int) cin.nval;
    }
    public static long nextLong() throws Exception {
        cin.nextToken();
        return (long) cin.nval;
    }
    public static double nextDouble() throws Exception {
        cin.nextToken();
        return cin.nval;
    }
    public static String nextString() throws Exception {
        cin.nextToken();
        return cin.sval;
    }
    public static void closeAll() throws Exception {
        cout.close();
        in.close();
        out.close();
    }
}