let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

PNUMBER - Tìm số nguyên tố

Có 3 lời giải:

  • Chia thử: trial_division.cpp
  • Miller: miller.cpp
  • Sàng nguyên tố: sieve.cpp
trial_division.cpp
Open in Github Download
#include <iostream>
using namespace std;

bool is_prime(int a) {
    if (a < 2) return false;
    if (a == 2) return true;
    if (a % 2 == 0) return false;
    for (int i=3; i * i <= a; i += 1) if (a % i == 0) return false;
    return true;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int a, b; cin >> a >> b;
    for (; a <= b; a++) if (is_prime(a)) cout << a << '\n';
}
sieve.cpp
Open in Github Download
#include <iostream>
using namespace std;

bool is_not_prime[200001];

int main() {
    is_not_prime[0] = is_not_prime[1] = true;
    for (int i = 2; i * i <= 200000; i++) if (!is_not_prime[i]) {
        for (int j = i * i; j <= 200000; j += i) is_not_prime[j] = true;
    }
    ios::sync_with_stdio(false); cin.tie(0);
    int a, b; cin >> a >> b;
    for (; a <= b; a++) if (!is_not_prime[a]) cout << a << '\n';
}
miller.cpp
Open in Github Download
#include <iostream>
#include <tuple>
using namespace std;
typedef unsigned long long ll;

ll pow(ll a, ll n, ll m) {
    ll result = 1;
    a = a % m;
    while (n > 0) {
        if (n & 1) result = result * a % m;
        n >>= 1;
        a = a * a % m;
    }
    return result;
}

pair<ll, ll> factor(ll n) {
    ll s = 0;
    while ((n & 1) == 0) {
        s++;
        n >>= 1;
    }
    return {s, n};
}

bool witness_test(ll s, ll d, ll n, ll witness) {
    if (n == witness) return true;
    ll p = pow(witness, d, n);
    if (p == 1) return true;
    for (; s > 0; s--) {
        if (p == n-1) return true;
        p = p * p % n;
    }
    return false;
}

bool miller(ll n) {
    if (n < 2) return false;
    if ((n & 1) == 0) return n == 2;
    ll s, d;
    tie(s, d) = factor(n-1);
    return witness_test(s, d, n, 2) && witness_test(s, d, n, 3);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int m, n;
    cin >> m >> n;
    for (int i=m; i<=n; i++) if (miller(i)) {
        cout << i << '\n';
    }
}
Comments