【筛法】第十万零二个素数

Java基础

浏览数:105

2019-10-8

AD:资源代下载服务

素数定理:给出从整数中抽到素数的概率。从不大于n的自然数随机选一个,它是素数的概率大约是1/ln n。也就是说在不大于n的自然数里,总共的素数为 n/lgn

筛法:

  用筛法求素数的基本思想是(本质上也能算是一种预处理):把从1开始的、某一范围内的正整数从小到大顺序排列, 1不是素数,首先把它筛掉。剩下的数中选择最小的数是素数,然后去掉它的倍数。依次类推,直到筛子为空时结束。如有: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。   1不是素数,去掉。剩下的数中2最小,是素数,去掉2的倍数,余下的数是:3 5 7 9 11 13 15 17 19 21 23 25 27 29 。剩下的数中3最小,是素数,去掉3的倍数,如此下去直到所有的数都被筛完,求出的素数为:2 3 5 7 11 13 17 19 23 29。
题目:第十万零二个素数   请问,第100002(十万零二)个素数是多少?   请注意:“2” 是第一素数,“3” 是第二个素数,依此类推。   
代码:

 1 public class 第十万零二个素数 {
 2 
 3     public static void main(String[] args) {
 4         long now = System.currentTimeMillis();
 5         // nlognlogn
 6         f(100002);
 7         System.out.println("耗时:" + (System.currentTimeMillis() - now) + "ms");
 8         
 9         /*============Java自带的api==========*/
10         now = System.currentTimeMillis();
11         BigInteger bigInteger = new BigInteger("1");
12         for (int i = 1; i <= 100002; i++) {
13             bigInteger = bigInteger.nextProbablePrime();
14         }
15         System.out.println(bigInteger);
16         System.out.println("耗时:" + (System.currentTimeMillis() - now) + "ms");
17         
18         /*==========朴素解法=========*/
19         now = System.currentTimeMillis();
20         int count = 0;
21         long x = 2;
22         while(count<100002){
23             if (isPrime(x)) {
24                 count++;
25             }
26             x++;
27         }
28         System.out.println(x-1);
29         System.out.println("耗时:" + (System.currentTimeMillis() - now) + "ms");
30     }
31     public static boolean isPrime(long num){
32         for (int i = 2; i*i <= num; i++) {
33             if (num%i==0) {
34                 return false;
35             }
36         }
37         return true;
38     }
39     /**
40      * 
41      * @param N 第N个素
42      */
43     private static void f(int N){
44         int n = 2;
45         // 自然数n之内的素数个数n/ln(n)
46         // 得到整数范围
47         while(n/Math.log(n)<N){
48             n++;
49         }
50         int []arr = new int[n];
51         int x = 2;
52         while(x<n){
53             if (arr[x]!=0) {
54                 x++;
55                 continue;
56             }
57             int k=2;
58              //对每个x,我们从2倍开始,对x的k倍,全部标记为-1
59             while(x*k<n){
60                 arr[x*k] = -1;
61                 k++;
62             }
63             x++;
64         }
65         // System.out.println(arr);
66         // 筛完之后,这个很长的数组里面非素数下标对应的值都是-1
67         int sum = 0;
68         for (int i = 2; i < arr.length; i++) {
69             // 是素数,计数+1
70             if (arr[i] == 0) {
71                 // System.out.println(i);
72                 sum++;
73             }
74             if (sum == N) {
75                 System.out.println(i);
76                 return;
77             }
78         }
79     }
80 
81 }

  结果:

    

 

作者:|旧市拾荒|