Tìm và in ra các số nguyên tố trong mảng C++
#include <iostream>
#include <math.h>
using namespace std;
void nhap(int a[], int &n);
void xuat(int a[], int n);
int ktnt(int x);
int lietkent(int a[], int n);
int main()
{
int a[100], n, m;
cout<<"Nhap slpt n= "; cin>>n;
nhap(a,n);
cout<<"cac phan tu mang A la:\n";
xuat(a,n);
cout<<endl;
cout<<"Cac so nguyen to trong mang: ";
lietkent(a,n);
}
void nhap(int a[], int &n)
{
for (int i=0; i<n; i++)
{
cout<<"A["<<i<<"]= "; cin>>a[i];
}
}
void xuat(int a[], int n)
{
for (int i=0; i<n; i++)
{
cout<<a[i]<<" ";
}
}
int ktnt(int x)
{
if (x<2)
return 0;
for (int i=2; i<=sqrt(x); i++)
if (x%i==0)
return 0;
return 1;
}
int lietkent(int a[], int n)
{
for (int i=0; i<n; i++)
if (ktnt(a[i])) cout<<a[i]<<" ";
}
Giải thích 1 chút về Hàm kiểm tra Số nguyên tố:
int ktnt(int x)
{
if (x<2)
return 0;
for (int i=2; i<=sqrt(x); i++)
if (x%i==0)
return 0;
return 1;
}
//i<=sqrt(x) vì số nguyên tố chắc chắn dương và lớn hơn 1 (điều kiện), ví dụ căn 2=1.41 thỏa mãn dương và lớn hơn 1.
Ví dụ: lấy x=5 – là số nguyên tố. Mà chúng ta không lấy căn, thì chương trình chỗ vòng lặp for là:
for (int i=2; i<=5; i++)
if (5%2==0)
return 0;
return 1;
- Lần 1: Điều này không làm thỏa mã điều kiện 5 chia hết cho 2 ( 5%2==0 ) thì nó return 1; – là trả về giá trị cho hàm là số nguyên tố.
Mỗi lần i tăng lên 1 đơn vị nếu điều kiện i<=x còn thỏa mãn.
- Lần 2: Nó kiểm tra 5%3==0 => Không thỏa mãn => return 1;
- Lần 3: 5%4==0 => Không thỏa mãn => return 1;
- Lần 4: 5%5==0 > Thỏa mãn => return 0; Lúc này, hàm sẽ lấy giá trị cuối cùng này và chương trình sẽ không liệt kê/ in ra số 5 mặc dù nó là số nguyên tố.
Trường hợp chúng ta lấy căn bậc 2 của 5 = 2.23: thì vòng lặp sẽ như này:
for (int i=2; i<=2.23; i++)
if (5%2==0)
return 0;
return 1;
- Lần 1: Nó lấy 5%2==0 => Không thỏa mãn => return 1 – trả về giá trị là số nguyên tố. Đúng như định nghĩa số nguyên tố là nó chỉ chia hết cho 1 và chính nó chứ không chia hết cho bất kỳ số nào khác.
- Lần 2: i=2 và <=2.23 nên nó tăng lên 1 đơn vị (i++). Rồi lại so sánh 5%3==0 => Không thỏa mãn => return 1 – là số nguyên tố.
- Lần 3: Sau khi i tăng lên 1 đơn vị nữa là i=4 thì lại không <=2.23 nên chương trình dừng tại đây và lấy kết quả của lần 2, chính là return 1 – là số nguyên tố.
Bấm để ghi chú