关于质数,你所应该知道的

2,822 阅读7分钟

概述

写这篇文章完全是有感而发,很小的时候就知道有质数这么一个东西,它不能被分解,做数学题计算的时候也是最怕遇到这个东西,遇到了证明它除不尽了,得出来的答案很可能就不是正确答案了。但是最近在 Project Euler 上面做了几道质数相关的编程题,感觉自己知道的还是太少,今天就简单介绍一些质数的基本性质,然后结合几道编程题来看看吧。


质数的基本性质

维基百科上面给出的质数的定义是 “除了 1 和自身外,无法被其他自然数整数的自然数”,这个定义你可能很早很早的时候就理解了,但是我要往深了问,你可能一下子不能马上反应过来,比如问题 “如何快速判断给定的一个数是不是质数?”,还有 “质数在所有的数中分布是怎样的,我们怎么通过算法高效地找到他们?”,这些问题其实某些时候很有用,比如如果我们知道一个数是质数,我们就知道它不能被更小的数整除,我们就会对我们写的程序计算更有把握,另外有一点很重要的就是所有大于 1 的自然数都可以写成质数的乘积,比如 4 = 2 * 2, 15 = 3 * 5, 20 = 2 * 2 * 5 ...,你会发现一个数我们可以用一个质数的集合(允许有重复的元素)来表示,换句话说只要我们找到了一个范围内的所有质数,那么这个范围的所有数都可以通过这些质数来求得,现在看来质数是自然数的基石。

接下来我们看一下质数的一些基本的性质,对于你理解质数会更有帮助:

  • 除了 2 以外,所有的质数都是奇数
  • 所有大于 3 的质数都可以写成 6k +/- 1 的形式
  • 任意一个大于 1 的自然数 n,最多只能有一个,除其本身外,大于 \sqrt{n} 的质数因子

这些东西不难,但是很有意思,我们一条一条看,首先第一条,这个不难理解,除了奇数就是偶数,偶数都会被 2 整除,那么大于 2 的偶数就会有 2 这个质数因子,因此偶数一定不是质数,奇数不一定是质数

看到第二条,你可能会打个问号,真的吗?注意这里 6k +/- 1 只是 “一个数是质数” 的必要条件,并不是充分条件,也就是说只要是质数就必须满足 6k +/- 1,但是满足这个条件的数不一定是质数,比如 25 就不是质数。你可能会问为什么是这样,其实证明也非常的简单,一个数不能被写成 6k +/- 1,那它肯定能被写成 6k +/- 2, 6k +/- 3, 6k +/- 4,一看看过去,你发现这三个表达式都是有质数因子 2 或者 3 的,因此他们表示的数肯定不是质数。

最后一条可以帮助我们缩小我们寻找一个数的质数因子的范围,比如你判断 101 这个数是不是质数,你只需要考虑这个数能不能整除 2 ~ 10 这个范围内的数,是不是一下子把搜索的时间降下来了?为什么这个性质成立呢?我们知道一个数可以写成几个或者多个数的乘积,比如 a = b * c = \sqrt{a} * \sqrt{a},假如 b > \sqrt{a}, 那么 c 肯定是要比 \sqrt{a} 小的,不然等式不成立,这样我们只需要在 2 ~ \sqrt{a} 的范围内寻找质数因子 c 即可,注意我这里说的是质数,不是 2 ~ \sqrt{a} 内所有的数。接下来,我们来看几道实际的编程题来理解一下这些性质具体有啥用。


实际问题

题目一

题目描述:
给定一个数,求这个数的最大质数因子,比如 100 的最大质数因子是 5。

思路和代码分析:
很直接的一道题,最暴力的解法就是找到给定数范围内的所有质数,然后从大到小去看这些质数是不是给定数的因子,如果是就直接返回。这种解法既耗空间又耗时间,而且题目并没有要求我们找出所有的质数,更好一点的解法是根据性质来看,任何数都可以表示成质数乘积的形式,比如给定一个数 a,可以分解为 b c d e 三种质数,a = b * c * d * b * c * e,这样我们就从小到大一个个排除就行了,废话不多说,先上代码

public int largestPrime(int n) {
    int largestPrime = 2;

    while (n % 2 == 0) {
        n >>= 1;
    }

    for (int i = 3; i <= Math.sqrt(n); i += 2) {
        while (n % i == 0 && n != i) {
            n /= i;
        }
    }

    if (n > 2) {
        largestPrime = n;
    }

    return largestPrime;
}

这里我应用了两个之前提到的性质,就是所有的偶数都不是质数,你可以看到第二个 for 循环从 3 开始,逐次加 2,这样可以保证跳过偶数,当然写的极致一些的话,你可以考虑应用上面提到的 “所有的质数都可以表示成 6k +/- 1” 这个性质,这里应用的另外一个性质就是,一个数大于 \sqrt{n} 的质数因子最多只可能有一个,这样我们只需要考虑去整除小于或等于 \sqrt{n} 的质数,如果有大于 \sqrt{n} 的质数因子的话,那么除剩下来的就是,这样又节省了不少时间。有些人可能会问,你怎么能保证你除的都是质数,如果不是质数怎么办?这个很好解释,之前提到过,所有的数都可表示成质数的乘积,从小到大,每次遇到的数如果不是质数,那么这个数可以拆成比自身小的质数,这些质数早在之前就约掉了,所以这里不需要过多的考虑。


题目二

题目描述:
找出第 100001th 个质数

思路和代码分析:
这次是真的要找质数了,这个是没辙的,从头到尾找,因为质数的分布其实是没有啥规律的(至少目前还没有发现),但是应用上面提到的一些性质能够让这个寻找的过程变得高效,我们一起来根据代码看看:

private static long findNthPrime(int n) {
    List<Long> primes = new ArrayList<>();

    primes.add(2L);

    long primeCandidate = 3;
    
    boolean isPrime = true;
    while (primes.size() != n) {
        int j = 0;
        isPrime = true;
        while ((primes.size() > j) && (primes.get(j) * primes.get(j) <= primeCandidate)) {
            if (primeCandidate % primes.get(j) == 0) {
                isPrime = false;
                break;
            }
            ++j;
        }

        if (isPrime) {
            primes.add(primeCandidate);
        }

        primeCandidate += 2L;
    }

    return primes.get(primes.size() - 1);
}

这里我一开始创建了一个 list 来存当前找到的质数。为什么要找之前所有的质数,其实这个不是必要的,但是所有的数都可以写成质数的乘积,如果你当前考虑的数没有任何一个质数因子,那么说明当前考虑的数是质数,注意这里我们只需要考虑质数因子,因此需要用 list 记录质数,不然又得回头去一个个看,重复考虑之前找到的数,这样就会浪费时间,所以记录还是很有必要的。另外第二层 while 循环还是应用了之前的性质去缩小考虑范围。


题目三

题目描述:
计算出 2 百万以下所有质数的和

思路和代码分析:
这题和上面一题没啥特别的地方,还是找,直接上代码:

private static long sumOfPrimes(int upperLimit) {
    long result = 0;

    List<Integer> primes = new ArrayList<>();

    result += 2L;
    primes.add(2);
    boolean isPrime = true;
    for (int i = 3; i < upperLimit; i += 2) {
        int j = 0;
        isPrime = true;
        
        while (primes.size() > j && primes.get(j) * primes.get(j) <= i) {
            if (i % primes.get(j) == 0) {
                isPrime = false;
                break;
            }

            ++j;
        }

        if (isPrime) {
            primes.add(i);
            result += (long)i;
        }
    }

    return result;
}

总结

以上就是这次分享的全部内容,是不是对质数的认识又加深了一点,感觉一些看似简单、普通的数学性质的的确确可以为程序运行效率带来质的飞跃。这里再次推荐 Project Euler 这个刷题网站,至于在这个上面做题对自身能力提升有何帮助,可以参考本期 ARTS 的 review 的部分的一篇文章

Consider Yourself a Developer? You Should Solve the Project Euler Problems

貌似 Project Euler 网站上面还是可以添加好友的,如果对刷这些逻辑数学题目感兴趣的朋友可以加我好友,我的 key 是 1525929_NEHOsVNpcMhyu9Ei1HoeklJz1xlnOaea,我们一起探讨,分享,打鸡血。