素数筛
2024-07-13 10:05:00
发布于：浙江
110阅读
0回复
0点赞
埃氏筛
bool is_prime[4000005];
//O(nloglogn)
int ans = 0;
void sieve(int n){
for(int i = 2; i<= n; i++) is_prime[i] = true;
for (int i = 2; i * i <= n; i++) {
// j: 哪些数字不是质数
if (!is_prime[i]) continue;
for (int j = 2 * i; j <= n; j += i){
is_prime[j] = false;
}
}
}
int main(){
int n;
cin >> n;
sieve(n);
for (int i = 2; i <= n; i++) {
if (is_prime[i]) ans++;
}
cout << ans << endl;
}
线性筛
long long primes[100005];
bool is_prime[100005];
int cnt = 0;
// primes[i]: 第i个质数
// cnt: 质数的数量
void sieve(int n){
for (int i = 2; i <= n; i++) is_prime[i] = true;
for (int i = 2; i <= n; i++) {
if (is_prime[i]) {
primes[++cnt] = i;
}
for (int j = 1; j <= cnt; j++){
if (i * primes[j] > n) break;
is_prime[i * primes[j]] = false;
if (i % primes[j] == 0) break;
}
}
}
全部评论 14
#include #include using namespace std; void xians(int n) { bool prime[n+1]; memset(prime, true, sizeof(prime)); prime[0] = prime[1] = false; for (int p = 2; p*p <= n; p++) { if (prime[p] == true) { for (int i = p*p; i <= n; i += p) { prime[i] = false; } } } for (int p = 2; p <= n; p++) { if (prime[p]) { cout << p << " "; } } cout << endl; } int main() { int n; cin >> n; xians(n); return 0; }2024-07-13 来自 广东
2歪理顾得
我把线性主函数补全了#include<bits/stdc++.h> using namespace std; long long primes[100000005]; bool is_prime[100000005]; int cnt = 0; // primes[i]: 第i个质数 // cnt: 质数的数量 void sieve(int n){ for (int i = 2; i <= n; i++) is_prime[i] = true; for (int i = 2; i <= n; i++) { if (is_prime[i]) { primes[++cnt] = i; } for (int j = 1; j <= cnt; j++){ if (i * primes[j] > n) break; is_prime[i * primes[j]] = false; if (i % primes[j] == 0) break; } } } int main(){ long long n,sum=0;cin>>n; sieve(n); for(int i=1;i<=n;i++){ if(is_prime[i]){ sum++; } } cout<<sum; return 0; }2024-07-13 来自 浙江
1<!doctype html> <html> <head> <title>ABC</title> </head> <body> <h1>ABC</h1> <p>666</p> </body> </html>2024-07-13 来自 浙江
0暴力法
#include <iostream> #include <cmath> using namespace std; bool is_prime(int n) { if (n <= 1) return false; for (int i = 2; i <= sqrt(n); i++) { if (n % i == 0) return false; } return true; } int main() { int n; cin >> n; if (is_prime(n)) { cout << n << " is a prime number" << endl; } else { cout << n << " is not a prime number" << endl; } return 0; }2024-07-13 来自 广东
0类欧几里得算法
#include <iostream> #include <cmath> using namespace std; int mod_pow(int a, int b, int m) { int res = 1; a %= m; while (b > 0) { if (b & 1) res = res * a % m; a = a * a % m; b >>= 1; } return res; } bool is_prime(int n) { if (n <= 1) return false; if (n <= 3) return true; int d = n - 1; while (d % 2 == 0) d /= 2; for (int a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) { if (n == a) return true; if (mod_pow(a, d, n) == 1) continue; int r = d; while (r < n - 1 && mod_pow(a, r, n) != n - 1) r *= 2; if (r >= n - 1) return false; } return true; } int main() { int n; cin >> n; if (is_prime(n)) { cout << n << " is a prime number" << endl; } else { cout << n << " is not a prime number" << endl; } return 0; }2024-07-13 来自 广东
0
有帮助，赞一个