素数

试除法判断是否为素数

#include <bits/stdc++.h> using namespace std; typedef long long ll; int n; int main() { cin >> n; while (n--) { int m; cin >> m; if (m < 2) cout << "No" << endl; else { int f = 1; for (int i = 2; i <= m / i; i++) //此种方式是最合理的方式 //若写成开平方的形式则严重影响时间 //写成i*i<=n可能会导致 { if (m % i == 0) { f = 0; break; } } if (f == 1) cout << "Yes" << endl; else cout << "No" << endl; } } return 0; }

试除法分解质因数

#include <bits/stdc++.h> using namespace std; typedef long long ll; int n; void divide(int n); int main() { cin >> n; while (n--) { int m; cin >> m; divide(m); } return 0; } void divide(int n) { for (int i = 2; i <= n / i; i++) { if (n % i == 0) { int s = 0; while (n % i == 0) { n = n / i; s++; } cout << i << " " << s << endl; } } if (n > 1) cout << n << " " << "1" << endl; cout << endl; }

筛质数

#include <bits/stdc++.h> using namespace std; typedef long long ll; const long long N= 1e6 + 10; int prime[N], cnt; int x[N]; int get_prime(int n); int main() { int n; cin >> n; get_prime(n); cout << cnt << endl; return 0; } int get_prime(int n) //线性筛法 { for (int i = 2; i <= n; i++) { if (!x[i]) prime[cnt++] = i; for (int j = 0; prime[j] <= n / i; j++) //确保每个和数只被筛一遍 { x[prime[j] * i] = 1; if (i % prime[j] == 0) break; } } }