求质数的方法_求第几个质数

作者：爱喝兽奶帝天荒 | 2024-07-05 20:43:57

踩

求第几个质数

求质数的方法

试除法判断质数
求第666个质数
求一个范围内的质数

试除法判断质数

判断n是否为质数，就是枚举[2,n-1]之间有没有能被n整除的。如果有，那么返回false，说明它不是质数；否则就是质数。

public static boolean isPrimeNum(int n){
    if (n <= 3) {
        return n > 1;
    }
    for(int i=2; i<Math.sqrt(n)+1; i++){
        if(n%i==0) return false;
    }
    return true;
}
1
2
3
4
5
6
7
8
9

如果一个数不是质数，那么必定是两个数的乘积，而这两个数通常一个大一个小，并且小的小于等于根号n，大的大于等于根号n，我们只需要枚举那个小范围的，看看是否能够被整除，就可以判断这个数是否为的可能啦。
例如：100=2x50=4x25=5x20=10x10 只需要找到10这个区间即可。右侧的一定有个对应的不需要管它。
这里之所以要小于根号n+1，就是要包含根号的情况，例如 3*3=9。要包含3。

求第666个质数

    public static void main(String[] args) {
        // 第五个质数是11
        int count = 5;
        int i = 11;
        while (true){
            i += 2;
            if (isPrimeNum(i)){
                count++;
            }
            if(count == 666){
                break;
            }
        }
        System.out.println(i);

    }

    public static boolean isPrimeNum(int n){
        if (n <= 3) {
            return n > 1;
        }
        for(int i=2; i<Math.sqrt(n)+1; i++){
            if(n%i==0) return false;
        }
        return true;
    }
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

求一个范围内的质数

一般来说，直接用上面的isPrimeNum判断就行。比如要找100以内的，就从1逐个判断直到100。。。

for(int i=1; i<101; i++){
    if(isPrimeNum(i)){
        System.out.print(i+", ");
    }
}
1
2
3
4
5

毕竟已经知道2和3是质数了，那直接去判断3之后的奇数，把步子迈成两步。

for(int i=1; i<101; i+=2){
    if(isPrimeNum(i)){
        System.out.print(i+", ");
    }
}
1
2
3
4
5

埃拉托斯特尼(Eratosthenes)筛法

埃拉托斯特尼筛法，简称埃氏筛或爱氏筛，是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。

删除型

原始的算法如下：（n取25）

列出从2到25的所有序列：
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
标出序列中的第一个素数，也就是2，序列变成：
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
将序列中，2的倍数都划掉，序列变成：
2 3 5 7 9 11 13 15 17 19 21 23 25
如果这个序列中最大数小于最后一个标出的素数的平方，那么剩下的序列中所有的数都是素数，否则回到第二步。
本例中，因为25大于2的平方，我们返回第二步：
剩下的序列中第一个素数是3，将主序列中3的倍数划掉，主序列变成：
2 3 5 7 11 13 17 19 23 25
我们得到的素数有：2，3
25仍然大于3的平方，所以我们还要返回第二步：
剩下的序列中第一个素数是5，同样将序列中5的倍数划掉，主序列成了：
2 3 5 7 11 13 17 19 23
我们得到的素数有：2，3，5
因为23小于5的平方，跳出循环.
结论：2到25之间的素数是：2 3 5 7 11 13 17 19 23。

# Python
def isPrimeNum(x):
    if x <= 3:
        return x>1
    for i in range(2,int(x**0.5+1)):
        if x%i==0:
            return False
    else:
        return True

def Eratosthenes(n):
    arr = [i for i in range(2,n+1)]
    arr_c = arr.copy()
    prime = []
    while True:
        firstNum = arr[0]
        if isPrimeNum(firstNum):
            prime.append(firstNum)	# 把这个质数添加到纯质数数组中
            arr.remove(firstNum)	# 将这个质数和他它的倍数都删除
            # 下标值比具体数值小2。比如arr[0]是2，arr[14]是16
            for j in range(firstNum*firstNum-2, len(arr_c), firstNum):
                # 比如6这个数，质数是2的时候删过一次。质数是3的时候再删就报错了
                # 加个一个count方法，有这个数才删，但是这个方法影响效率
                if arr.count(arr_c[j]) != 0:
                    arr.remove(arr_c[j])
            if firstNum ** 2 > arr[-1]:
                break
        else:
            arr.remove(firstNum)
    prime = prime + arr
    return prime

if __name__=='__main__':
    a = Eratosthenes(100)
    print(a)
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

在代码中建立了两个数组。两个数组内容是一样的，都存放着从1到n的N个连续数值。因为删除会导致数组发生动态变化，导致数组的下标不太好整。比如在删除2的倍数时，取arr[47]的值应该是48，但因为数组已经变了，arr[47]可能变成了77，或者下标为47的时候就直接算超界。。。

# 这种写法就不用顾虑下标的变化了
def Eratosthenes(n):
    arr = [i for i in range(1,n+1)]
    prime = []
    while True:
        firstNum = arr[0]
        if isPrimeNum(firstNum):
            num.append(firstNum)
            for j in arr:
                if j%firstNum==0:
                    arr.remove(j)
            if firstNum ** 2 > arr[-1]:
                break
        else:
            arr.remove(firstNum)
    prime = prime + arr
    return prime
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

标记型1

这是我最开始的写法，写完才发现与搜索到的不一样。详细列出代码中算法如下：（比如这个n是25）

列出从1到25的所有序列：
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
找第一个数，也就是1，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
找第二个数，也就是2，2是质数，将2的倍数都做标记。2的平方不大于25。下标加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
找第三个数，也就是3，3是质数，将3的倍数都做标记。3的平方不大于25。下标加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
找第四个数，也就是4，4不是质数，做标记。下标加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
找第五个数，也就是5，5是质数，将5的倍数都做标记。5的平方不大于25。下标加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
找第六个数，也就是6，6不是质数，做标记。下标加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
找第七个数，也就是7，7是质数，将7的倍速都做标记。7的平方大于25。循环结束。。。
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
结论：2到25之间的素数是： 2 3 5 7 11 13 17 19 23

标记型的缺点就是有很多重复的计算。
比如18，选到2是质数的时候，它被标记了一次，同样的，3是质数的时候它又被标记了一次。所以因数越多，被标记的次数也就越多。虽然我在下标的初始化时做了平方处理，但作用不是很大。
而且在代码中，我一直用当前质数的平方与数组中的最后一个数作比较，并没有关注数组中的最后一个数是否被标记过。这也是一个待优化的点。

package com.company;
import java.util.ArrayList;
import java.util.List;
public class test {
    public static void main(String args[]){
        System.out.println(Eratosthenes(100));
    }
    public static List<Integer>  Eratosthenes(int n) { //参数n代表范围
        // 创建标记数组，初始值全是0。标记为-1的都不是质数
        int[] is_prime = new int[n];
        for (int num = 1; num <= n; num++) {
            if (isPrimeNum(num)){
                // 若num是质数，将它的倍数全标记为-1
                // 被标记的数字比它的索引大1
                // 下标从平方开始，可以减少一部分数字的重复标记
                // 比如num=5，要标记5的倍数。可以直接从数字25开始。因为10和20被num=2标记过，15被num=3标记过
                for(int j=num*num-1; j < n; j=j+num){
                    is_prime[j] = -1;
                }
                if (num * num > n) break;
            }else {
                is_prime[num-1] = -1;
            }
        }
        List<Integer> list = new ArrayList<>();
        for(int i=0; i<n; i++){
            if (is_prime[i] == 0) list.add(i+1);
        }
        return list;
    }
    public static boolean isPrimeNum(int n){
        if (n <= 3) return n > 1;
        for(int i=2; i<Math.sqrt(n)+1; i++){
            if(n%i==0) return false;
        }
        return true;
    }
}
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

标记型2

详细列出代码中算法如下，那些用C/C++写的属于这种：（比如这个n是25）

列出从2到25的所有序列：
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
找第一个数，也就是2，2没被标记过。它就是质数。把2放入数组prime中。并把2的倍数都做标记，，，
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
找第二个数，也就是3，3没被标记过。它就是质数。把3放入数组prime中。并把3的倍数都做标记，，，
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
找第三个数，也就是4，4被标记过，把4的倍数都做标记，，，（待优化的点出来了）
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
找第四个数，也就是5，5没被标记过。它就是质数。把5放入数组prime中。并把5的倍数都做标记，，，
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
找第五个数，也就是6，6被标记过。把6的倍数都做标记，，，
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
一直循环n-1轮

这段算法的好处就是，不需要用试除法判断当前数字是不是质数，只看它是否被标记过。缺点就是最外层的for循环要进行到底
代码中用来存放标记情况的数组isprime。第一个元素直接忽略，所以在范围上加了1。好处是数字和它的下标不是错位的。比如4是2的倍数，做标记时，直接就 isprime[4]=true 这样赋值。

public static void main(String[] args) {
	int n = 100;                     // 范围
    int[] prime = new int[n];       // 记录第几个prime
    int index = 0;                  // 标记prime当前下标
    boolean[] isprime = new boolean [n+1];// 判断是否被标记过，初始值都是false。加1是为了使下标和数字对应起来，就不像上面是错位的
    for(int i=2; i<=n; i++)
    {
        if(!isprime[i])
        {
            prime[index] = i;
            index++;
        }
        for(int j=i+i; j<=n; j=j+i) //他的所有倍数都标记
        {
            isprime[j]=true;
        }
    }
    for(int i: prime){
        System.out.print(i+", ");
    }
    // 输出长这样。。。后面都是0
    // 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 0, 0, 0, 0, 0, 0,  0, 0, 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

下面是我改进后的算法
isPrime数组就是一个筛子，或者说是一个工具。只要把这个工具造出来，那么存放质数的数组就不需要创建

public static void main(String args[]){
    int n = 100;
    int[] isPrime = new int[n+1]; //判断是否被标记过，初始值都是0，不是质数的标记为-1
    for(int i=2; i*i<=n; i++){
        if(isPrime[i]==0){
            for(int j=i*i; j<=n; j=j+i) //将它的所有倍数都标记
            {
                isPrime[j]=-1;
            }
        }
    }

    for (int i = 2; i <= n; i++) {
        if (isPrime[i]==0) System.out.print(i+", ");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

欧拉筛

埃氏筛中的标记法，有重复的计算。
而欧拉筛在埃氏筛的基础上改进，有效的避免了这个重复计算。
具体是何种思路呢？就是埃氏筛是遇到一个质数将它的倍数计算到底，而欧拉筛则是只用它乘以已知晓的素数的乘积进行标记，如果素数能够被整除那就停止往后标记。

详细列出代码中算法如下：（比如这个n是25）

列出从2到25的所有序列：
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
找第一个数，2，2没被标记过。它就是质数。把2放入数组prime中。把2的倍数4做标记，，，
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
找第二个数，3，3没被标记过。它就是质数。把3放入数组prime中。把3的倍数6，9做标记，，，
2 3 4 5 6 7 8 910 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
找第三个数，4，4被标记过，把4的倍数都做标记，，，
2 3 4 5 6 7 8 910 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
找第四个数，5，5没被标记过。它就是质数。把5放入数组prime中。把3的倍数10，15，20做标记，，，
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
找第五个数，6，6被标记过。把6的倍数12做标记，，，
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
找第六个数，7，7没被标记过。它就是质数。把7放入数组prime中。把7的倍数14，21做标记，，，
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
一直循环n-1轮

public static void main(String[] args) {
    int n = 25;
    int[] prime = new int[n];
    int index = 0;
    boolean[] isprime = new boolean[n+1];
    for (int i = 2; i <= n; i++) {
        if (!isprime[i]) {
            prime[index] = i;
            index++;
        }
        for (int j = 0; j < index && i * prime[j] <= n; j++){//已知素数范围内枚举
            isprime[i * prime[j]] = true;// 标记乘积
            if (i % prime[j] == 0)
                break;
        }
    }
    for(int i: prime){
        System.out.print(i+", ");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

欧拉筛只会让一个数做一次标记。在已有质数表的基础上，标记那些离自己近的倍数。虽然没有像埃氏筛那样，有一个i方大于n时就跳出循环的条件，但效率确实比埃氏筛高。
欧拉的思路就是离我较近的我给它标记，比如i=6时，只标记12而不标记18，18留给i=9的时候标记。欧拉筛的时间复杂度为O(n)，因为每个数只标记一次。
你可能会问为啥if (i % prime[j] == 0)就要break。
如果i%prime[j]==0，那么就说明i=prime[j]*k，k为一个整数。
那么如果进行下一轮的话
i*prime[j+1]=(prime[j]*k)*prime[j+1]=prime[j]*(k*prime[j+1])。当i=k*prime[j+1]两个位置就产生冲突重复计算啦，所以一旦遇到能够被整除的就停止。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/爱喝兽奶帝天荒/article/detail/790964