Vấn đề
Kiểm tra số cho trước có thể biểu diễn như tổng hai số nguyên tố hay không.
Cho số nguyên dương N, kiểm tra N có thể biểu diễn như tổng hai số nguyên tố.
Giải pháp
Ví dụ: 20 = 3 + 17, 13 + 7.
Thuật toán
Thuật toán biểu diễn số như tổng hai số nguyên tố:
Bước 1 - Nhập số cần kiểm tra tại runtime.
Bước 2 - Lặp i từ 2 đến (num/2).
Bước 3 - Kiểm tra i là số nguyên tố.
Bước 4 - Nếu i nguyên tố, kiểm tra (n - i) có nguyên tố không.
Bước 5 - Nếu cả hai đều nguyên tố, số đó = tổng i và (n - i).
Ví dụ
Chương trình C biểu diễn số như tổng hai số nguyên tố:
#include <stdio.h>
int Sum(int n);
int main(){
int num, i;
printf("Nhap so: ");
scanf("%d", &num);
int flag = 0;
for(i = 2; i <= num/2; ++i){
if (sum(i) == 1){
if (sum(num-i) == 1){
printf("\nSo %d = tong %d va %d\n\n", num, i, num - i);
flag = 1;
}
}
}
if (flag == 0)
printf("So %d khong the bieu dien la tong hai so nguyen to\n", num);
return 0;
}
// Kiem tra so nguyen to
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
Kết quả chạy chương trình:
Lan 1: Nhap so: 34 34 = 3 + 31 34 = 5 + 29 34 = 11 + 23 34 = 17 + 17 Lan 2: Nhap so: 11 11 khong the bieu dien la tong hai so nguyen to