Số chẵn biểu diễn thành tổng hai số nguyên tố (Even Number With Prime Sum)

Giới thiệu

Tất cả các số chẵn từ 4 trở đi đều có thể biểu diễn dưới dạng tổng của hai số nguyên tố. Đôi khi một số có thể có nhiều hơn một tổ hợp tổng số nguyên tố.

Ví dụ số 10 = (5 + 5) và (7 + 3)

Thuật toán này sẽ tìm tất cả các tổ hợp tổng số nguyên tố cho một số cho trước. Khi một số x là số nguyên tố, ta chỉ kiểm tra xem (number - x) có phải số nguyên tố hay không, nếu có, tổng của x và (number – x) biểu diễn số chẵn đó.

Đầu vào và Đầu ra

Đầu vào: Số chẵn: 70
Đầu ra: Các tổng số nguyên tố
70 = 3 + 67
70 = 11 + 59
70 = 17 + 53
70 = 23 + 47
70 = 29 + 41

Thuật toán

dispPrimeSum(num)
Đầu vào: Số chẵn.
Đầu ra: Hiển thị số bằng tổng của một số số nguyên tố.

Begin
    if num là lẻ, then
        exit
    for i := 3 to num/2, do
        if i là số nguyên tố, then
            if (num - i) là số nguyên tố, then
                hiển thị "num = i + (num – i)"
    done
End

Ví dụ (C++)

#include <iostream>
using namespace std;

int isPrime(int number) {
    // kiểm tra số có phải nguyên tố hay không
    int lim;
    lim = number/2;
    for(int i = 2; i <= lim; i++) {
        if(number % i == 0)
            return 0;  // Số không phải nguyên tố
    }
    return 1;  // Số là nguyên tố
}

void displayPrimeSum(int num) {
    string res;
    if(num % 2 != 0) {  // khi số là số lẻ
        cout << "Invalid Number";
        exit(1);
    }
    for(int i = 3; i <= num/2; i++) {
        if(isPrime(i)) {  // nếu i là số nguyên tố
            if(isPrime(num-i)) {  // num - i cũng là nguyên tố
                cout << num << "= " << i << " + " << (num-i) << endl;
            }
        }
    }
}

main() {
    int num;
    cout << "Enter an even number: "; cin >> num;
    displayPrimeSum(num);
}

Kết quả

Enter an even number: 70
70 = 3 + 67
70 = 11 + 59
70 = 17 + 53
70 = 23 + 47
70 = 29 + 41