Sắp xếp số nguyên tố tăng dần C++

Sắp xếp số nguyên tố tăng dần trong c++

Đề bài

Viết một chương trình thực hiện các yêu cầu sau:

– Viết hàm có tên là sort(int a[],int n)để sắp xếp các phần tử của mảng một chiều theo thứ tự tăng dần.

– Viết hàm có tên là ktsnt(int x) kiểm tra xem một số nguyên x có phải là số nguyên tố không.

– Viết hàm main() nhập 10 phần tử là các số nguyên từ bàn phím, sử dụng hàm sort()và hàm ktsnt()để in lên màn hình các số nguyên tố trong mảng theo thứ tự tăng dần.

Thuật toán

Định nghĩa số nguyên tố

“Số nguyên tố là số tự nhiên lớn hơn 1, chỉ có hai ước là 1 và chính nó”. (chỉ chia hết cho 1 và chính nó).

Tức là: một số tự nhiên lớn hơn 1, nếu như ngoài bản thân nó và 1 ra, nó không chia hết cho số nào khác nữa thì nó là số nguyên tố. Ví dụ như 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, …

Ví dụ:

• 1: => Không là số nguyên tố.
• 2: chỉ chia hết cho 1 và chính nó là 2 => là số nguyên tố.
• 3: chia hết cho 1 và 3 => là số nguyên tố.
• 4: chia hết cho 1, 2 và 4 => Không là số nguyên tố.
• …

Code bài toán

Viết hàm có tên là sort(int a[],int n)để sắp xếp các phần tử của mảng một chiều theo thứ tự tăng dần.

void sort (int a[], int n)
{
	int i,j,tg;
	for(i = 0; i < n - 1; i++)
    {
        for(j = i + 1; j < n; j++)
        {
            if(a[i] > a[j])
            {
                tg = a[i];
                a[i] = a[j];
                a[j] = tg;
            }
        }
    }
   for(int i=0;i<n;i++)
    {
       cout<<a[i]<<" ";
    }  
}

Viết hàm có tên là ktsnt(int x) kiểm tra xem một số nguyên x có phải là số nguyên tố không.

int ktnt(int x)
{
	int n=sqrt(x);		
	for (int i=2;i<=n;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]<<" ";
}

Viết hàm main() nhập 10 phần tử là các số nguyên từ bàn phím, sử dụng hàm sort()và hàm ktsnt()để in lên màn hình các số nguyên tố trong mảng theo thứ tự tăng dần.

#include <iostream>
#include <math.h>
using namespace std;
void sort (int a[], int n)
{
	int i,j,tg;
	for(i = 0; i < n - 1; i++)
    {
        for(j = i + 1; j < n; j++)
        {
            if(a[i] > a[j])
            {
                tg = a[i];
                a[i] = a[j];
                a[j] = tg;
            }
        }
    }
   for(int i=0;i<n;i++)
    {
       cout<<a[i]<<" ";
    }  
}
int ktnt(int x)
{
	int n=sqrt(x);		
	for (int i=2;i<=n;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]<<" ";
}
int main ()
{
	int i, n=10, a[10];
	cout<<"Moi ban nhap mang gom 10 phan tu:\n";
	for (i=0;i<n;i++)
	{
		cout<<"A["<<i<<"]= "; cin>>a[i];
	}
	cout<<"Sap xep mang tang dan";
	sort(a,n);
	cout<<"\nSap xep cac so nguyen to tang dan la: ";
	lietkent(a,n);
}