12 行代码C++算法模板
质数判断
常用的判断质数方法,使用 flag 标记,判断数字 n 是否为质数。
int n;
cin >> n;
bool flag = true;
for (int i = 2; i <= n/i; i++)
if (n % i == 0) {
flag = false;#质数
常用的判断质数方法,使用 flag 标记,判断数字 n 是否为质数。
int n;
cin >> n;
bool flag = true;
for (int i = 2; i <= n/i; i++)
if (n % i == 0) {
flag = false;线性筛法,筛出 1 ~ N 中所有的质数,时间复杂度 O(N)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
bool f[N+5];
int prime[N], cnt = 0;
埃氏筛法,筛出 1 ~ N 中所有的质数,时间复杂度 O(N log log N)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
bool f[N+5];
int prime[N], cnt = 0;
简单的质数判定代码,时间复杂度 O(sqrt(x))
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;