筛素数

1.暴力筛

#include <cstdio> #include <iostream> using namespace std; int n, q; bool check (int); int main () { scanf ("%d %d", &n, &q); for (int i = 1; i <= q; i++) { int x; scanf ("%d", &x); if (check (x)) { printf ("Yes\n"); } else { printf ("No\n"); } } return 0; } bool check (int x) { if (x == 1) return 0; for (int i = 2; i <= x / i; i++) { if (x % i == 0) return 0; } return 1; }

2.埃筛

#include <cstdio> #include <iostream> using namespace std; const int MAXN = 100000005; int n, q, len; int prime[MAXN]; bool vis[MAXN]; void Make (); int main () { scanf ("%d %d", &n, &q); Make (); for (int i = 1; i <= q; i++) { int x; scanf ("%d", &x); if (vis[x] == 0) { printf ("Yes\n"); } else { printf ("No\n"); } } return 0; } void Make () { vis[1] = 1; for (int i = 2; i <= n; i++) { if (vis[i] == 0) { prime[++len] = i; for (int j = i; j <= n / i; j++) { vis[i * j] = 1; } } } }

3.线性筛(欧拉筛)

#include <cstdio> #include <iostream> using namespace std; const int MAXN = 100000005; int n, m, num; int prime[MAXN]; bool vis[MAXN]; void oulasai(); int main() { cin >> n >> m; oulasai(); for (int i = 1; i <= m; i++) { int tem; scanf("%d", &tem); if (vis[tem] == 0) printf("Yes\n"); else printf("No\n"); } return 0; } void oulasai() { vis[1] = 1; for (int i = 2; i <= n; i++) { if (vis[i] == 0) { //如果是质数 prime[++num] = i; } for (int j = 1; j <= num; j++) { if (prime[j] > n / i) break; vis[i * prime[j]] = 1; if (i % prime[j] == 0) break; } } }