质数质数筛

1.试除法判定质数–O(sqrt(N))

bool is_prime(int x)
{if (x < 2) return false;for (int i = 2; i <= x / i; i ++ )if (x % i == 0)return false;return true;
}

2.试除法分解质因数–O(logN)~O(sqrt(N))

void divide(int x)
{for (int i = 2; i <= x / i; i ++ )if (x % i == 0){int s = 0;while (x % i == 0) x /= i, s ++ ;cout << i << ' ' << s << endl;}if (x > 1) cout << x << ' ' << 1 << endl;cout << endl;
}

3.埃氏筛法求质数–O(NloglogN)

int primes[N],cnt;
bool st[N];//筛选出所有数的倍数
void get_primes(int n)
{for (int i = 2; i <= n; i++){if (st[i]) continue;primes[cnt++] = i;for (int j = i + i; j <= n; j += i) st[j] = true;//筛选出i的倍数}
}

4.欧拉筛法O(N)

int i, j, num=1;
memset(u, true, sizeof(u));
for (i=2; i<=n; i++){            //顺序分析整数区间的每个数if (u[i]) su[num++]=i;          //将筛中最小数送入素数表for (j=1; j<num; j++)       {          //搜索素数表的每个数if (i*su[j]>n) break;  //若i与当前素数的乘积超出范围，则分析下一个整数iu[i*su[j]]=false;            //将i与当前素数的乘积从筛子中筛去if (i%su[j]==0) break;   //若当前素数为i的最小素因子，则分析下一个整数i,这样可避免重复，降低时间复杂度}}

洛谷P3383 【模板】线性筛素数

题目描述
如题，给定一个范围 $n$，有 $q$ 个询问，每次输出第 $k$ 小的素数。

输入格式
第一行包含两个正整数 $n,q$，分别表示查询的范围和查询的个数。
接下来 $q$ 行每行一个正整数 $k$，表示查询第 $k$ 小的素数。

输出格式
输出 $q$ 行，每行一个正整数表示答案。

输入输出样例 #1
输入 #1

100 5
1
2
3
4
5

输出 #1

2
3
5
7
11

说明/提示
【数据范围】
对于 $100\%$ 的数据，$n=10^8$，$1\le q\le 10^6$，保证查询的素数不大于 $n$。

#include<bits/stdc++.h>
int n, m;
const int N =1e8+1;
int a[N], primes[N];
void prime_sieve()
{int i, j, t = 0;for (i = 2; i <= n; i++){if (a[i] == 0){primes[++t] = i;}for (j = 1; j <= n / i&&i*primes[j]<=n; j++){a[primes[j] * i] = 1;if (i % primes[j] == 0){break;}}}
}
int main()
{scanf("%d%d",&n,&m);prime_sieve();int i;for (i = 1; i <= m; i++){int x;scanf("%d",&x);printf("%d\n",primes[x]);}return 0;
}