Math-数学基础知识素数 Prime

老马啸西风2017年8月23日大约 10 分钟

素数

质数又称素数。

一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数。

特性

1. 素数的个数无限多（不存在最大的素数）

证明：反证法，假设存在最大的素数P，那么我们可以构造一个新的数2 * 3 * 5 * 7 * … * P + 1（所有的素数乘起来加1）。

显然这个数不能被任一素数整除（所有素数除它都余1），这说明我们找到了一个更大的素数。

2. 存在任意长的一段连续数，其中的所有数都是合数（相邻素数之间的间隔任意大）

证明：当 0 m，则p可以整除a(n-m)。但p是素数，那么a和n-m中至少有一个含有因子p。这显然是不可能的，因为a和n-m都比p小。

简单解法的三种方式

最基本的方式

最直观的方法，根据定义，因为质数除了1和本身之外没有其他约数，所以判断n是否为质数，根据定义直接判断从2到n-1是否存在n的约数即可。

C++代码如下：

bool isPrime_1( int num )
{
    int tmp =num- 1;
    for(int i= 2; i  1;
    }
    //6x+1 6x+5
    if (num % 6 != 1 && num % 6 != 5) {
        return false;
    }

    int tmp = (int) Math.sqrt(num);
    //在6的倍数两侧的也可能不是质数
    for (int i = 5; i  primeList(final int limit) {
    if (limit  resultList = new ArrayList<>();
    // 初始化是否为素数列表
    List isPrimeList = new ArrayList<>(limit);
    for(int i = 0; i  primeList(final int limit) {
        if (limit  resultList = new ArrayList<>();
        // 初始化是否为素数列表
        List isPrimeList = CollectionUtils.fill(limit, true);
        for (int i = 0; i < limit; i++) {
            isPrimeList.add(true);
        }

        for (int i = 2; i < limit; i++) {
            if (isPrimeList.get(i)) {
                // 加入素数列表
                resultList.add(i);
            }

            final int pos = resultList.size();
            for (int j = 0; j < pos && i * resultList.get(j) < limit; j++) {
                int notPrimeIndex = i * resultList.get(j);
                isPrimeList.set(notPrimeIndex, false);
                //标注一
                if (i % resultList.get(j) == 0) {
                    break;
                }
            }
        }

        return resultList;
    }