Chào các anh chị/bạn trong forum, e là sinh viên năm nhất và có một bài tập về nhà là duyệt một mảng một chiều, hiển thị ra các phần tử của mảng là số nguyên tố.
e cũng đã đọc thuật toán trong giáo trình( là thuật toán đếm ước của A[i] từ 2-> căn A[i]), e cảm thấy nó chưa tôi ưu lắm nên đã tham khảo phương pháp sàng Eratosthenes. Nhưng các ví dụ của phương pháp này đều là tìm các số nguyên tố trong đoạn [2,n] liên tục, chứ không có nhiều ví dụ về việc ứng dụng nó trong sàng các phần tử của mảng. Nên e đã biến đổi nó một chút thành thuật toán:
Duyệt từ đầu đến cuối mảng, nếu nó là số nguyên tố thì tìm và xóa các phần tử còn lại là bội của nó, còn nếu tại vị trí đó không phải là số nguyên tố thì tìm các phần từ bằng nó còn lại trong mảng và xóa. Sau cùng thì được một mảng chứa toàn bộ là số nguyên tố.
Mong anh/chị hay các bạn nào có phương pháp tối ưu hơn thì có thể chia sẻ để e phát triển bài toán hay hơn ạ. hì hì
Dưới đây là code C của e.
#include <stdio.h>
#include <math.h>
//Define kieu du lieu bool
#define bool int
#define TRUE 1
#define FALSE 0
// Max cua mang A
#define MAX 200
void delete(int A[], int kichThuocMang, int viTriMuonXoa){
int i;
for(i = viTriMuonXoa; i < kichThuocMang -1; i++ ){
A[i] = A[i+1];
}
}
bool laSoNguyenTo(int n){
if(n <= 1){
return FALSE;
}
else if(n == 2){
return TRUE;
}
else if(n%2 == 0){
return FALSE;
}
else
{
int m = (int)sqrt(n);
for(int i = 3; i <= m; i+= 2){
if(n%i == 0){
return FALSE;
}
}
return TRUE;
}
}
void nhapMang(int A[], int n){
for(int i = 0; i < n; i++){
printf("Nhap A[%d] = ", i);
scanf("%d", &A[i]);
}
}
void xuatMang(int A[], int n){
for(int i = 0; i < n; i++){
printf("%4d", A[i]);
}
}
int main()
{
int A[MAX];
int n;
printf("Nhap kich thuoc mang: ");
scanf("%d", &n);
// Nhap mang A
nhapMang(A, n);
//Mang sau khi nhap
printf("\nMang sau khi nhap la: \n");
xuatMang(A, n);
// Thuc thi thuat toan
int dem = 0; // dem = so phan tu bi xoa
for(int i = 0; i < n; i++){
if( laSoNguyenTo(A[i]) ){ //Neu la so nguyen to thi tim va xoa cac phan tu khac la boi cua no
for(int j = i+1; j < n; j++){
if( A[j]%A[i] == 0 ){
delete(A, n, j);
dem++;
n--; // Moi lan xoa se tru di 1 phan tu
}
}
}
else // Khong la so nguyen to thi tim va xoa nhung phan tu trong mang = no
{
for(int j = i+1; j < n; j++){
if(A[j] == A[i]){
delete(A, n, j);
dem++;
n--; // Moi lan xoa se tru di mot phan tu
}
}
}
}
// Mang sau khi loc
printf("\nCac so nguyen to co trong mang la : \n");
xuatMang(A, n);
printf("\nSo Phan tu trong mang bi xoa la %d : \n", dem);
return 0;
}
). Ví dụ:
. Ví dụ:
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?