@[toc]

零、写在前面

  这是《算法零基础100讲》 专栏打卡学习的第七天了，很多基础的循环用法，在前面的章节都已经学过了，接下来我们需要接触一些数论相关的知识， 学习数学，最重要的是 「 耐心 」，通过一些已有的知识来分析问题。
  刷题的时候遇到不会的数论题，真的是很揪心，从头学起吧，内容实在是太多了，每个知识点都要证明吃透，不然下次遇到还是不会；不学吧，又不甘心，就是单纯的想把这个题过了，真是进退两难！
  如果你也和我有一样的困扰，那接下来就让我们一起来专攻一下 「 数论 」 的知识吧！当然，既然是零基础，肯定先学简单的，但是今天的两道题可不是那么简单的，做好心理准备哦，开始吧！

一、概念定义

1、整除性

  若 $a$ 和 $b$ 都为整数， $a$ 整除 $b$ 是指 $b$ 是 $a$ 的倍数， $a$ 是 $b$ 的约数（因数、因子），记为 $a|b$。整除的大部分性质都是显而易见的，为了阐述方便，我给这些性质都起了个名字。
  i) 任意性：若 $a|b$，则对于任意非零整数 $m$，有 $am|bm$
  ii) 传递性：若 $a|b$ 且 $b|c$ ，则 $a|c$
  iii) 可消性：若 $a|bc$且 $a$ 和 $c$ 互素(互素即两个数的最大公约数为1)，则 $a|b$
  iv) 组合性：若 $c|a$且 $c|b$，则对于任意整数 $m、n$，有 $c|(ma+nb)$

  【例题1】(公元1987年初二数学竞赛题) $x，y，z$ 均为整数，若 $11|(7x+2y-5z)$，求证： $11|(3x-7y+12z)$。

  为了描述方便，令：

$$a = (7x+2y-5z), b = (3x-7y+12z)$$

  通过构造，可以得到一个等式：

$$3a + 4b = 11*(3x-2y+3z)$$

  根据任意性+组合性，得出：

$$11|(11*(3x-2y+3z) - 3a) = 11|4b$$

  然后根据可消性，由于 $11$ 和 $4$ 互素，得出 $11|b$，证明完毕。

2、素数与合数

  素数又称质数，素数首先满足条件是要大于等于 2，并且除了 1 和它本身外，不能被其它任何自然数整除。
  其它的数称为合数；
  而 1 既非素数也非合数；
  特殊的，2 是唯一的偶素数。

3、素数判定

  如何判定一个数是否为素数？
  对 $n$ 做 $[2, n)$ 范围内的余数判定（c/c++中 的 '%'运算符），如果有至少一个数用 $n$ 取余后为 0，则表明 $n$ 为合数；如果所有数都不能整除 $n$，则 $n$ 为素数，算法复杂度 $O(n)$。

1）优化1

  这样做的时间复杂度太高了，所以我们需要进行一定的优化。
  考虑到一个数 $x$ 如果是 $n$ 的因子，则 $x$ 整除 $n$，那么必然 $n/x$ 是一个整数，且 $n/x$ 也一定是 $n$ 的因子。其中， $x$ 和 $n/x$ 一定有一个大小关系，不妨设：

$$x \le \frac n x$$

则不等式两边同时乘上 $x$，得到：

$$x^2 \le n$$

再对两边进行开方，得到：

$$x \le \sqrt n$$

于是我们在枚举 $x$ 的时候只需要枚举 $[2, \sqrt n]$ 范围内的数即可，这样一来，时间复杂度就变成了 $O(\sqrt n)$。

2）优化2

  如果 $n$ 是合数，那么它必然有一个小于等于 $\sqrt n$ 的素因子，只需要对 $\sqrt n$ 内的素数进行测试即可，需要预处理求出 $\sqrt n$ 中的素数，假设该范围内素数的个数为 $s$，那么复杂度降为 $O(s)$。

二、题目描述

  给定一个数 $n (n \le 10^9)$，判断它是否是素数，返回它是否是素数。

三、算法详解

  由于 $n$ 的范围太大，所以必然不能用 $O(n)$ 的算法，但是 $O(\sqrt n)$ 的时间复杂度是可以接受的，所以可以直接计算。

四、源码剖析

int isPrime(int n) {              // (1)
    int i, sqrtn = sqrt(n + 1e-6);
    if(n <= 1) {
        return 0;                 // (2)
    }
    for(i = 2; i <= sqrtn; ++i) {
        if(n % i == 0) {          // (3)
            return 0;
        }
    }
    return 1;                     // (4)
}

• $(1)$ 定义一个函数，函数传入参数n，如果n为素数返回 1；否则返回 0；
• $(2)$ 当n <= 1时，必然不是素数，直接返回 0；
• $(3)$ 如果找到一个数，是 $n$ 的因子，且值不为 1，则 n必然不是素数，返回 0；
• $(4)$ 找不到除 $n$ 和 $1$ 以外的因子，代表它是素数没跑了，直接返回 1；

五、推荐专栏

六、习题练习

请参考原文