CTDL và giải thuật - In lần lượt các số nguyên tố
Bài tập.
Nhập vào một số nguyên dương n
, và n
số nguyên lần lượt là các phần tử trong dãy a
. Hãy in lần lượt các số nguyên tố có trong dãy a
ra màn hình, sau mỗi phần tử có đúng một khoảng trắng.
(Số nguyên tố là số nguyên dương có đúng 2
ước là 1
và chính nó. Số a
được gọi là ước của b
nếu b
chia hết cho a
). Biết rằng dãy sẽ có ít nhất một số nguyên tố.
Ví dụ:
- Test mẫu 1:
Input Output 4
1 2 3 42 3
Vớin = 4, a = [1, 2, 3, 4]
thì kết quả mong muốn là:"2 3 ".
- Test mẫu 2:
Input Output 3
7 2 37 2 3
Vớin = 3, a = [7, 2, 3]
thì kết quả mong muốn là:"7 2 3 "
.
Hướng dẫn bài tập.
Một trong nhữngcách kiểm tra số nguyên tố tốt nhất đó là:
Để kiểm tra một số n
có phải là số nguyên tố hay không ta làm như sau:
- Nếu
n < 2
thìn
không là số nguyên tố. - Nếu
n = 2
hoặcn = 3
thì n là số nguyên tố. - Nếu
n ≥ 2
:- Nếu
n
không có ước trong khoảng2
đến phần nguyên căn bậc2
củan
thì n là số nguyên tố, ngược lạin
không là số nguyên tố.
- Nếu
Code mẫu:
Ngôn ngữ C++:
#include<iostream>
#include<math.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;
}
int main(){
int a[100];
int n;
cin >> n;
for (int i = 0; i < n; i++){
cin >> a[i];
}
for (int i = 0; i < n; i++){
if (isPrime(a[i])){
cout << a[i] << " ";
}
}
return 0;
}