如果 除以 的余数为 ，我们就说 能整除 （用 表示）， 能被 整除。
此时也会说 是 的约数（因子、因数）， 是 的倍数。
输入 个数，以每行 个数的顺序输出。
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
{
cout << a[i] << " ";
if (a[i] % 5 == 0)
cout << "\n";
}
bool is_prime(int x)
{
if (x < 2)
return false;
for (int i = 2; i <= x - 1; i++)
if (x % i == 0)
return false;
return true;
}
如果 ，那么必然有 。
证明：若 且 ，那么 。
因此如果 在 范围内存在因子，则必然在 范围内存在因子。
反之亦然，如果 在 范围内没有因子，则必然在 范围内也没有因子。
由此，我们可以只检查更小的范围，得到时间复杂度为 的算法
bool is_prime(int x)
{
if (x < 2)
return false;
for (int i = 2; i * i <= x; i++)
if (x % i == 0)
return false;
return true;
}
基于 的优化可以进一步推出：只需要检查 范围里的所有质数是否是 的因子即可（证明略）。
此时有两个优化思路：
%6 的余数分为六类 ，这六类中，只有 与 可能是质数，因此只需要检查 内满足这个性质的数即可。时间复杂度仍然是 ，但是常数是原来的 。米勒罗宾素性检测：需要更多数论知识，后续再讲。有兴趣的同学可以自行阅读 OI-Wiki 上的介绍
适用于需要多次判断某个数是否为质数的场景，可以一次性预处理出来某个范围内的数分别是否为质数。
思想非常简单，初始认为大于 的自然数都是质数，然后依次把 的倍数、 的倍数、 的倍数、 标记为非质数即可。即筛掉所有的质数的倍数，就留下了质数。
具体的实现上，会从 开始枚举每个数，如果这个数没有被筛掉，就认为它是质数，可以用它筛掉它的倍数。因为如果这个数没有被筛掉，说明比它小的数都没有筛掉它，它不存在除了 和本身之外的因子。
bool p[MAXN + 1];
//筛出 1~n 中的每个数是否为质数
void get_primes(int n)
{
//初始化
p[0] = p[1] = false;
for (int i = 2; i <= n; i++)
p[i] = true;
//筛
for (int i = 2; i <= n; i++)
if (p[i])
for (int j = i + i; j <= n; j += i)
p[j] = false;
}
时间复杂度为：。
后续会学习的欧拉筛法可达到 的时间复杂度，也叫线性筛。
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
设正整数 ，那么必有表示：，其中 是素数。
并且在不计次序的意义下，该表示唯一。
标准素因数分解式：
将上述表示中，相同的素数合并，可得：
称为正整数 的标准素因数分解式。
算术基本定理和算术基本引理，两个定理是等价的。
若 ，其中 是互不相等的质数。
那么考虑因子中每个质数用了多少个可得：
的因子个数为
证明见：http://wiki.33dai.cn/math/number-theory/gcd/#_5
// a^b (mod p)
long long quick_pow(long long a, long long b, long long p)
{
long long res = 1;
while (b > 0)
{
if (b % 2 == 1)
res = (res * a) % p;
b = b / 2;
a = (a * a) % p;
}
return res;
}
// a^b (mod p)
long long quick_pow(long long a, long long b, long long p)
{
long long res = 1;
while (b)
{
if (b & 1)
res = (res * a) % p;
b = b >> 1;
a = (a * a) % p;
}
return res;
}
// a^b (mod p)
long long quick_pow(long long a, long long b, long long p)
{
long long res = 1;
while (b)
{
if (b & 1)
res = (res * a) % p;
b = b >> 1;
a = (a * a) % p;
}
return res;
}
//求 x 在模 p 意义下的逆元（要求 p 是一个质数）
long long inv(long long x, long long p)
{
return quick_pow(x, p - 2, p);
}
inv[1] = 1;
for (int i = 2; i <= n; i++)
inv[i] = (- p / i + p) * inv[p % i] % p;