Tìm và in ra các số nguyên tố trong mảng C++

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ố.