Bài toán Số nguyên tố tương đương

code c++ python

Bài toán – Số nguyên tố tương đương

Hai số tự nhiên được gọi là Nguyên tố tương đương nếu chúng có chung các ước số nguyên tố. Ví dụ các số 75 và 15 là nguyên tố tương đương vì cùng có các ước nguyên tố là 3 và 5. Cho trước hai số tự nhiên N, M. Hãy viết chương trình kiểm tra xem các số này có là nguyên tố tương đương với nhau hay không.

Thuật toán

Để kiểm tra hai số tự nhiên N và M có phải là nguyên tố tương đương hay không, ta cần kiểm tra xem chúng có chung các ước số nguyên tố hay không.

Đầu tiên, ta có thể tìm tất cả các ước số nguyên tố của N và M bằng cách sử dụng một hàm để liệt kê tất cả các ước số nguyên tố của một số tự nhiên.

Sau đó, ta sẽ so sánh hai tập hợp các ước số nguyên tố của N và M để kiểm tra xem chúng có phải là tập hợp con của nhau hay không. Nếu hai tập hợp này giống nhau thì N và M là nguyên tố tương đương, ngược lại thì chúng không phải là nguyên tố tương đương.

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

# Hàm kiểm tra số nguyên tố
def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

# Hàm liệt kê tất cả các ước số nguyên tố của một số tự nhiên
def prime_factors(n):
    factors = []
    for i in range(2, n + 1):
        if is_prime(i) and n % i == 0:
            factors.append(i)
    return factors

# Chương trình chính
n = int(input("Nhập số tự nhiên N: "))
m = int(input("Nhập số tự nhiên M: "))

if set(prime_factors(n)) == set(prime_factors(m)):
    print("{} và {} là nguyên tố tương đương.".format(n, m))
else:
    print("{} và {} không phải là nguyên tố tương đương.".format(n, m))

Trong chương trình này, hàm is_prime(n) được sử dụng để kiểm tra xem một số nào đó có phải là số nguyên tố hay không. Hàm prime_factors(n) sử dụng hàm is_prime(n) để tìm tất cả các ước số nguyên tố của số nào đó.

Sau đó, ta sử dụng hàm set() để biến đổi danh sách các ước số nguyên tố của N và M thành tập hợp. Nếu hai tập hợp này giống nhau, thì N và M là nguyên tố tương đương và chương trình sẽ in ra thông báo tương ứng. Ngược lại, nếu hai tập hợp không giống nhau, chương trình sẽ thông báo rằng N và M không phải là nguyên tố tương đương.

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

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Hàm kiểm tra số nguyên tố
bool is_prime(int n) {
    if (n < 2) {
        return false;
    }
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

// Hàm liệt kê tất cả các ước số nguyên tố của một số tự nhiên
vector<int> prime_factors(int n) {
    vector<int> factors;
    for (int i = 2; i <= n; i++) {
        if (is_prime(i) && n % i == 0) {
            factors.push_back(i);
        }
    }
    return factors;
}

int main() {
    int n, m;
    cout << "Nhap so tu nhien N: ";
    cin >> n;
    cout << "Nhap so tu nhien M: ";
    cin >> m;

    vector<int> factors_n = prime_factors(n);
    vector<int> factors_m = prime_factors(m);

    // Sắp xếp các ước số nguyên tố của N và M để so sánh
    sort(factors_n.begin(), factors_n.end());
    sort(factors_m.begin(), factors_m.end());

    // So sánh hai tập hợp các ước số nguyên tố
    if (factors_n == factors_m) {
        cout << n << " va " << m << " la nguyen to tuong duong." << endl;
    } else {
        cout << n << " va " << m << " khong phai la nguyen to tuong duong." << endl;
    }

    return 0;
}

Thuật toán tối ưu

Chúng ta có thể tối ưu thuật toán bằng cách sử dụng phép phân tích thừa số nguyên tố để tìm các ước số nguyên tố của mỗi số. Phương pháp này có độ phức tạp thời gian là O(sqrt(n)) với n là số cần phân tích. Vì vậy, ta chỉ cần phân tích thừa số nguyên tố của hai số đầu vào và so sánh các ước số nguyên tố của chúng để xác định xem chúng có nguyên tố tương đương hay không.

Python

def prime_factors(n):
    """
    Trả về một tập hợp chứa các ước số nguyên tố của n
    """
    factors = set()
    # Xử lý ước số nguyên tố 2
    while n % 2 == 0:
        factors.add(2)
        n //= 2
    # Xử lý các ước số nguyên tố lẻ
    for i in range(3, int(n**0.5)+1, 2):
        while n % i == 0:
            factors.add(i)
            n //= i
    # Nếu n còn lại sau khi xử lý các ước số nguyên tố thì nó cũng là một ước số nguyên tố
    if n > 2:
        factors.add(n)
    return factors

# Nhập vào 2 số tự nhiên
n = int(input("Nhap so tu nhien N: "))
m = int(input("Nhap so tu nhien M: "))

# Tìm các ước số nguyên tố của N và M
factors_n = prime_factors(n)
factors_m = prime_factors(m)

# So sánh hai tập hợp các ước số nguyên tố
if factors_n == factors_m:
    print(f"{n} va {m} la nguyen to tuong duong.")
else:
    print(f"{n} va {m} khong phai la nguyen to tuong duong.")

Ở đây, chúng ta định nghĩa hàm prime_factors(n) để tìm các ước số nguyên tố của một số bằng phép phân tích thừa số nguyên tố. Hàm này trả về một tập hợp các ước số nguyên tố của số đầu vào.

Sau đó, ta sử dụng tập hợp để lưu trữ các ước số nguyên tố của N và M. Cuối cùng, ta so sánh hai tập hợp các ước số nguyên tố của N và M bằng toán tử ==. Nếu hai tập hợp này giống nhau, thì N và M là nguyên tố tương đương.

C++

#include <iostream>
#include <unordered_set>
#include <vector>

using namespace std;

// Hàm phân tích thừa số nguyên tố của một số
unordered_set<int> prime_factors(int n) {
    unordered_set<int> factors;
    while (n % 2 == 0) {
        factors.insert(2);
        n /= 2;
    }
    for (int i = 3; i * i <= n; i += 2) {
        while (n % i == 0) {
            factors.insert(i);
            n /= i;
        }
    }
    if (n > 2) {
        factors.insert(n);
    }
    return factors;
}

int main() {
    int n, m;
    cout << "Nhap so tu nhien N: ";
    cin >> n;
    cout << "Nhap so tu nhien M: ";
    cin >> m;

    unordered_set<int> factors_n = prime_factors(n);
    unordered_set<int> factors_m = prime_factors(m);

    // So sánh hai tập hợp các ước số nguyên tố
    if (factors_n == factors_m) {
        cout << n << " va " << m << " la nguyen to tuong duong." << endl;
    } else {
        cout << n << " va " << m << " khong phai la nguyen to tuong duong." << endl;
    }

    return 0;
}

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *