Số phản nguyên tố

NỘI DUNG

Bài toán. SỐ PHẢN NGUYÊN TỐ

Một số tự nhiên n được gọi là số phản nguyên tố nếu nó ó nhiều ước số nhất trong n số tự nhiên đầu tiên

Yêu cầu: Cho số K (K<=10000) ghi ra số phản nguyên tố lớn nhất nhỏ hơn hoặc bằng K.

Dữ liệu vào: Đọc từ file văn bản OPNT.INP có cấu trúc như sau:

– Dòng đầu tiên là số M(1<M<=100): số các số cần tìm số phản nguyên tố lớn nhất của nó.

– M dòng tiếp theo là các số K1,K2,..KM

Dữ liệu ra: Ghi ra file văn bản SOPNT.OUT có cấu trúc như sau:

Gồm M dòng, Dòng thứ i (1<=i<=M) là số hản nguyên tố lớn nhất nhỏ hơn hoặc bằng Ki.

Thuật toán

Để giải bài toán này, ta có thể sử dụng thuật toán sàng Eratosthenes để tìm tất cả các số nguyên tố nhỏ hơn hoặc bằng K. Sau đó, ta có thể duyệt danh sách này từ phải sang trái để tìm số phản nguyên tố lớn nhất nhỏ hơn hoặc bằng K.

Ví dụ: để tìm các số nguyên tố nhỏ hơn hoặc bằng 30, ta sử dụng thuật toán sàng Eratosthenes như sau:

Đánh số các số từ 2 đến 30.
Chọn số đầu tiên là số 2 và xóa các bội số của số này (tức các số 4, 6, 8, …).
Chọn số tiếp theo là số 3 và xóa các bội số của số này (tức các số 9, 15, 21, …).
Chọn số tiếp theo là số 5 và xóa các bội số của số này (tức các số 25, …).
Tiếp tục cho đến khi chọn các số từ 2 đến 30.

Sau khi sàng Eratosthenes, ta thu được danh sách các số nguyên tố nhỏ hơn hoặc bằng 30 là: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Ta duyệt danh sách này từ phải sang trái để tìm số phản nguyên tố lớn nhất nhỏ hơn hoặc bằng K. Trong trường hợp này, số phản nguyên tố lớn nhất nhỏ hơn hoặc bằng 30 là 23.

Cài đặt bài toán với Python

def eratosthenes(n):
    # Tạo danh sách số từ 2 đến n
    numbers = list(range(2, n + 1))
    primes = []
    while len(numbers) > 0:
        # Lấy số đầu tiên trong danh sách là số nguyên tố
        prime = numbers[0]
        primes.append(prime)
        # Xóa các bội số của số nguyên tố này
        numbers = [n for n in numbers if n % prime != 0]
    return primes


with open('OPNT.INP', 'r') as f:
    m = int(f.readline())
    ks = [int(f.readline()) for _ in range(m)]

primes = eratosthenes(max(ks))
result = []
for k in ks:
    for p in reversed(primes):
        if p < k:
            result.append(p)
            break

with open('SOPNT.OUT', 'w') as f:
    for r in result:
        f.write(str(r) + '\n')

Cài đặt bài toán với C++

#include <bits/stdc++.h>
using namespace std;

bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) return false;
    }
    return true;
}

vector<int> eratosthenes(int n) {
    vector<int> primes;
    vector<bool> isComposite(n + 1, false);
    for (int i = 2; i <= n; i++) {
        if (!isComposite[i]) {
            primes.push_back(i);
            for (int j = i * i; j <= n; j += i) {
                isComposite[j] = true;
            }
        }
    }
    return primes;
}

int main() {
    int m, k;
    ifstream in("OPNT.INP");
    ofstream out("SOPNT.OUT");
    in >> m;
    vector<int> ks(m);
    for (int i = 0; i < m; i++) {
        in >> ks[i];
    }
    vector<int> primes = eratosthenes(*max_element(ks.begin(), ks.end()));
    for (int i = 0; i < m; i++) {
        for (int j = primes.size() - 1; j >= 0; j--) {
            if (primes[j] < ks[i]) {
                out << primes[j] << endl;
                break;
            }
        }
    }
    return 0;
}

Đánh giá độ phức tạp

Độ phức tạp của thuật toán trên có thể được phân tích như sau:

Tìm tất cả các số nguyên tố nhỏ hơn hoặc bằng K sử dụng thuật toán sàng Eratosthenes có độ phức tạp O(K log log K).
Duyệt danh sách các số nguyên tố từ phải sang trái để tìm số phản nguyên tố lớn nhất nhỏ hơn hoặc bằng từng số cần tìm, với mỗi số cần tìm, thao tác này có độ phức tạp O(K), vì trong trường hợp xấu nhất, ta cần phải duyệt qua toàn bộ danh sách các số nguyên tố.

Vì vậy, độ phức tạp tổng thể của thuật toán trên là O(MK log log K), với M là số lượng số cần tìm, và K là số lớn nhất trong các số đó.

Lập trình C/C++, Lập trình Python