【模板】线性筛素数

【模板】线性筛素数

#include #include #include #include using namespace std; int n, m, vis[10000010], prime[5000010], tot; void init() { for (int i = 2; i <= n; i++) { if (!vis[i]) prime[++tot] = i; for (int j = 1; j <= tot; j++) { int t = i * prime[j]; if (t > n) break; vis[t] = 1; if (i % prime[j] == 0) break; } } } int main() { scanf("%d%d", &n, &m); init(); while (m--) { int t; scanf("%d", &t); if (!vis[t] && t != 1) puts("Yes"); else puts("No"); } return 0; }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。