Vấn đề
Tìm hiểu xem một số đã cho có thể được biểu diễn dưới dạng tổng của hai số nguyên tố hay không.
Cho một số nguyên dương N, chúng ta cần kiểm tra xem số N có thể được biểu diễn dưới dạng tổng của hai số nguyên tố hay không.
Giải pháp
Hãy xem xét một ví dụ được đưa ra bên dưới -
20 có thể được biểu thị dưới dạng tổng của hai số nguyên tố 3 và 17, 13 và 7.
20 =3 + 7
20 =13 + 7
Thuật toán
Tham khảo thuật toán đưa ra dưới đây để biểu thị một số nhất định dưới dạng tổng của hai số nguyên tố.
Bước 1 - Nhập số sẽ được kiểm tra tại thời điểm chạy.
Bước 2 - Lặp lại từ i =2 đến (num / 2).
Bước 3 - Kiểm tra xem i có phải là số nguyên tố không.
Bước 4 - Nếu tôi là số nguyên tố, hãy kiểm tra xem (n - i) có phải là số nguyên tố hay không.
Bước 5 - Nếu cả (i) và (n - i) là số nguyên tố thì số đã cho có thể được biểu diễn dưới dạng tổng của các số nguyên tố i và (n - i).
Ví dụ
Sau đây là chương trình C để biểu diễn một số đã cho dưới dạng tổng của hai số nguyên tố -
#include <stdio.h>
int Sum(int n);
int main(){
int num, i;
printf("Enter number: ");
scanf("%d", &num);
int flag = 0;
for(i = 2; i <= num/2; ++i){
if (sum(i) == 1){
if (sum(num-i) == 1){
printf("\nThe given %d can be expressed as the sum of %d and %d\n\n", num, i, num - i);
flag = 1;
}
}
}
if (flag == 0)
printf("The given %d cannot be expressed as the sum of two prime numbers\n", num);
return 0;
}
//check if a number is prime or not
int sum(int n){
int i, isPrime = 1;
for(i = 2; i <= n/2; ++i){
if(n % i == 0){
isPrime = 0;
break;
}
}
return isPrime;
} Đầu ra
Khi chương trình trên được thực thi, nó tạo ra kết quả sau -
Run 1: Enter number: 34 The given 34 can be expressed as the sum of 3 and 31 The given 34 can be expressed as the sum of 5 and 29 The given 34 can be expressed as the sum of 11 and 23 The given 34 can be expressed as the sum of 17 and 17 Run 2: Enter number: 11 The given 11 cannot be expressed as the sum of two prime numbers