最简单的就是从 2 ~ n-1 都去与 n 取余，看是否能整除。
bool prime(int n){
for(int i = 2; i < n; i ++)
if(n % i == 0)
return true;
return false;
}
思考一下：其实没有必要枚举所有的比 n 小的数，n % i == 0，那么必定有一个 j 使得 i * j = n。所以只需要枚举 i * i ≤ n 的 i 就可以了。
bool prime(int n){
for(int i = 2; i * i <= n; i ++)
if(n % i == 0)
return true;
return false;
}
如果需要对许多整数进行素数判断，上面得方法时间复杂度就较高了，这就需要更高效的算法，如埃式筛法。
一个数如果是素数，那么它的倍数就一定是合数，这就筛去了它的所有倍数。
操作：将 2 ~ n-1 个整数列出来，从 2 开始把它的倍数都筛去，然后将 3 的倍数筛去……遍历所有的素数，把它的倍数都筛去。
我们设置一个标记数组，依次遍历过去（同时标记它的倍数），若 i 没有被标记就代表 i 不会被 2 ~ i-1 的任何一个整数整除，就说明它是素数。
bool flag[maxx];
int prime[maxx], p;//记录素数
void primes(int n){
flag[1] = true;
for(int i = 2; i <= n; i ++){
if(!flag[i]){//找到一个素数
prime[p ++] = i;//记录素数
}
for(int j = 0; prime[j] * i <= n; j ++)//遍历素数数组，将全部素数的i倍进行标记
flag[prime[j] * i] = true;
}
}
时间复杂度：O(n * log log n)
n = 12的埃式筛法流程
| i | prime | 本轮筛去的整数 |
|---|---|---|
| 2 | 2 | 4 |
| 3 | 2、3 | 6、9 |
| 4 | 2、3 | 8、12 |
| 5 | 2、3、5 | 10 |
| 6 | 2、3、5 | 12 |
| 7 | 2、3、5、7 | |
| 8 | 2、3、5、7 | |
| 9 | 2、3、5、7 | |
| 10 | 2、3、5、7 | |
| 11 | 2、3、5、7、11 | |
| 12 | 2、3、5、7、11 |
仔细思考一下：埃式筛法也有冗余，同一个合数有可能会被两个素数筛。例如，12：12 % 2 = 0、12 % 3 = 0，那么 12 就被 2、3 都筛了一次，这样就导致了重复。
线性筛法保证每个合数只会被它的最小质因数筛去，因此每个数只会被标记一次，时间复杂度是O(n)。
bool flag[maxx];
int prime[maxx], p;//记录素数
void primes(int n){
flag[1] = true;
for(int i = 2; i <= n; i ++){
if(!flag[i]){//找到一个素数
prime[p ++] = i;//记录素数
}
for(int j = 0; prime[j] * i <= n; j ++){
flag[i * prime[j]] = true;
if(i % prime[j] == 0)
break;
}
}
}
这与埃式筛法的区别就在于：
if(i % prime[j] == 0)
break;
这样就保证了同一个合数，只会被他最小的质因子筛去。
证明： 如果 i % prime[j] = 0，记 k = i / prime[j]，则 i * prime[j + 1] = k * prime[j] * prime[j + 1]，而 prime[j] < prime[j + 1]，则代表 prime[j + 1] 不是 i * prime[j + 1] 的最小质因子。
我看一下上面举的例子：12
| i | prime | 本轮筛去的整数 |
|---|---|---|
| 2 | 2 | 4 |
| 3 | 2、3 | 6、9 |
| 4 | 2、3 | 8（4 % 2 = 0） |
| 5 | 2、3、5 | 10 |
| 6 | 2、3、5 | 12（6 % 2 = 0） |
| 7 | 2、3、5、7 | |
| 8 | 2、3、5、7 | |
| 9 | 2、3、5、7 | |
| 10 | 2、3、5、7 | |
| 11 | 2、3、5、7、11 | |
| 12 | 2、3、5、7、11 |
问题：给定整数 a 和 b，请问区间 [a, b) 内有多少个素数？
思路：b 以内的合数的最小质因数一定不超过 sqrt(b)。如果有 sqrt(b) 以内的素数表的话，就可以把埃氏筛法运用在 [a, b) 上了。也就是说，先分别做好 [2, sqrt(b)) 的表和 [a, b) 的表，然后从 [2, sqrt(b)) 的表中筛得素数的同时，也将其倍数从 [a, b) 的表中划去，最后剩下的就是 [a, b) 内的素数了。
bool flag[maxx], flag_section[maxx];
int primes(int a, int b){
flag[1] = true;
for(int i = 2; i * i < b; i ++){
if(!flag[i]){//找到一个素数
for(int j = 2 * i; j * j < b; j += i)//筛选[2, sqrt(b))
flag[j] = true;
for(int j = max(2, (a + i - 1) / i) * i; j < b; j += i)//(a+i-1)/i得到最接近a的i的倍数，最低是i的2倍，然后筛选
flag_section[j - a] = true;
}
}
int cnt = 0;
for(int i = 0; i < b - a; i ++)
if(!flag_section[i])
cnt ++;
return cnt;
}
基本定理：任何一个大于 1 的正整数都能唯一分解为有限个质数的乘积，可写作：
N
=
p
1
c
1
p
2
c
2
p
3
c
3
…
p
m
c
m
N=p_{1}^{c_{1}}p_{2}^{c_{2}}p_{3}^{c_{3}}\ldots p_{m}^{c_{m}}
N=p1c1p2c2p3c3…pmcm其中 ci 都是正整数，pi 都是质数，且满足 p1<p2<……<pm。
采用：试除法。
结合质数判定的“试除法”和质数筛选的“埃式筛法”，我们可以扫描 2~⌊ √N ⌋ 的每个数 d，若 d 能整除 N，则从 N 中除掉所有的因子 d，同时累计除去的 d 的个数。
因为一个合数的因子一定在扫描到这个合数之前就从 N 中被除掉了，所以在上述过程中能整除 N 的一定是质数。最终就得到了质因数分解的结果，易知时间复杂度为 O(√N)。
特别地，若 N 没有被任何 2~√N 地数整除，则 N 是质数，无需分解。
void divide(int n){
int m = 0;
for(int i = 2; i <= sqrt(n); i ++)
if(n % i == 0){//i是质数
p[++m] = i, c[m] = 0;
while(n % i == 0)
n /= i, c[m] ++;
}
if(n > 1)//n是质数
p[++m] = n, c[m] = 1;
for(int i = 1; i <= m; i ++)
printf("%d^%d\n", p[i], c[i]);
}
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1000010;
int primes[N], cnt;
bool st[N];
void getPrimes(int n){
memset(st, false, sizeof(st));
cnt = 0;
for(int i = 2; i <= n; i ++){
if(!st[i])
primes[cnt ++] = i;
for(int j = 0; primes[j] * i <= n; j ++){
st[primes[j] * i] = true;
if(i % primes[j] == 0)
break;
}
}
}
int main(){
long long l, r;
while(~scanf("%lld %lld", &l, &r)){
getPrimes(50000);
memset(st, false, sizeof(st));
for(int i = 0; i < cnt; i ++){
int p = primes[i];
for(long long j = max((l + p - 1) / p * p, 2ll * p); j <= r; j += p)// 把[l, r]中所有p的倍数筛掉
st[j - l] = true;
}
cnt = 0;
for(int i = 0; i <= r - l; i ++)
if(!st[i] && i + l > 1)
primes[cnt ++] = i + l;
if(cnt < 2)
printf("There are no adjacent primes.\n");
else{
int minp = 0, maxp = 0;
for(int i = 0; i + 1 < cnt; i ++){
int d = primes[i + 1] - primes[i];
if(d < primes[minp + 1] - primes[minp])
minp = i;
if(d > primes[maxp + 1] - primes[maxp])
maxp = i;
}
printf("%d,%d are closest, %d,%d are most distant.\n", primes[minp], primes[minp + 1], primes[maxp], primes[maxp + 1]);
}
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1000010;
int primes[N], cnt;
bool st[N];
void getPrimes(int n){
memset(st, false, sizeof(st));
cnt = 0;
for(int i = 2; i <= n; i ++){
if(!st[i])
primes[cnt ++] = i;
for(int j = 0; primes[j] * i <= n; j ++){
st[primes[j] * i] = true;
if(i % primes[j] == 0)
break;
}
}
}
int main(){
int n;
scanf("%d", &n);
getPrimes(n);
for(int i = 0; i < cnt; i ++){
int p = primes[i];
int s = 0;
for(int j = p; j <= n; j *= p){
s += n / j;
if(j > n / p)
break;
}
printf("%d %d\n", p, s);
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1000010;
int primes[N], cnt;
bool st[N];
void getPrimes(int n){
memset(st, false, sizeof(st));
cnt = 0;
for(int i = 2; i <= n; i ++){
if(!st[i])
primes[cnt ++] = i;
for(int j = 0; primes[j] * i <= n; j ++){
st[primes[j] * i] = true;
if(i % primes[j] == 0)
break;
}
}
}
int main()
{
// 请在此输入您的代码
getPrimes(2019);
long long dp[2020] = {1};
for(int i = 0; i < cnt; i ++)
for(int j = 2019; j >= primes[i]; j --)
dp[j] += dp[j - primes[i]];
printf("%lld", dp[2019]);
return 0;
}