PDA

View Full Version : Bài tập C | Xuất số nguyên tố



server1988
02-02-2007, 04:19 PM
em cần nhập 1 mãng vào và xuất số nguyên tố ra


#include<iostream.h>
#include<conio.h>
void nhap(int a[],int &n);
int snt(int a[],int n);
void xuat(int a[],int n);
void main()
{
clrscr();
int a[100],n;
nhap(a,n);
xuat(a,n);
getch();
}
void nhap(int a[],int &n)
{
cout<<"Nhap n:";
cin>>n;
for(int i=0;i<n;i++)
{
cout<<"Nhap a["<<i<<"]";
cin>>a[i];
}
}
int snt(int a[],int n)
{
int d=0;
for(int i=0;i<n;i++)
for(int j=1;j<a[i];j++)
{
if(a[i]%j)
d++;
if(d==2)
return d==2;
}
}
void xuat(int a[],int n)
{
for(int i=0;i<n;i++)
if(snt(a[i]))
cout<<"So nguyen to la:"<<a[i];
}
sao em sửa hoài mà nó ko xuất ra các số nguyên tố các bạn xem cách giải của mình có gì xài sót ko

huynguyen
02-02-2007, 10:41 PM
Tôi thấy code bạn viết khá rối, tôi phân tích bài toán bạn đưa ra rồi bạn làm lại thử xem sao nhé:
Nhập 1 mảng số nguyên
Xây dựng hàm kiểm tra số nguyên tố trên 1 con số
Cho vòng lặp đi hết mảng, ứng với mỗi điểm thì chạy hàm kiểm tra số nguyên tố và xuất ra nếu đúng
Bạn xây dựng 1 hàm kiểm tra số nguyên tố của cả 1 mảng là đã sai về ý tưởng giải quyết bài toán, chưa kể hàm snt của bạn sai giải thuật.

Nhuan_Trang_Only_Love
02-02-2007, 11:25 PM
Tôi thấy code bạn viết khá rối, tôi phân tích bài toán bạn đưa ra rồi bạn làm lại thử xem sao nhé:
Nhập 1 mảng số nguyên
Xây dựng hàm kiểm tra số nguyên tố trên 1 con số
Cho vòng lặp đi hết mảng, ứng với mỗi điểm thì chạy hàm kiểm tra số nguyên tố và xuất ra nếu đúng
Bạn xây dựng 1 hàm kiểm tra số nguyên tố của cả 1 mảng là đã sai về ý tưởng giải quyết bài toán, chưa kể hàm snt của bạn sai giải thuật.
đồng ý như vậy, tuy nhiên là khi nhập vào sao chúng ta không kiểm tra luôn xem số đó có là số nguyên tố không. nếu là nguyên tố thì save vào mảng khác , và biến đếm có bao nhiêu so nguyên tố . Lúc sau chỉ dựa vào điều kiện 0<biến đếm || < 0 để xuất ra màn hình luôn.Theo cách của bác thì lần sau phải chạy lại từ đầu để kiểm tra từng số một, có dài quá không?
Cách của em thì có lẽ sẽ tốn bộ nhớ nhiều?
Chỉ giùm em nhá

huynguyen
03-02-2007, 12:34 AM
đồng ý như vậy, tuy nhiên là khi nhập vào sao chúng ta không kiểm tra luôn xem số đó có là số nguyên tố không. nếu là nguyên tố thì save vào mảng khác , và biến đếm có bao nhiêu so nguyên tố . Lúc sau chỉ dựa vào điều kiện 0<biến đếm || < 0 để xuất ra màn hình luôn.Theo cách của bác thì lần sau phải chạy lại từ đầu để kiểm tra từng số một, có dài quá không?
Cách của em thì có lẽ sẽ tốn bộ nhớ nhiều?
Thế thì cách của you chỉ dùng được cho câu hỏi này thôi, giả sử đây chỉ là 1 câu hỏi trong 1 bài tập thì sao nào? Dĩ nhiên you vẫn phải nhập 1 mảng vào và làm giống tôi nói thôi. Cách làm thì có nhiều cách, lựa cách nào để cho mình ko gặp rắc rối về sau là được rồi. Nói đơn giản hơn là thiết kế chương trình sao cho có khả năng mở rộng bài toán, đó mới là thiết kế :D

neverland87
03-02-2007, 09:24 AM
int SNT(int n)
{
int count=0;
for(int i=1;i<n;i++)
if (n%i==0) count++;
if (count==1) return 1 //TRUE
else return 0; //FALSE
}
void main()
{
nhập mảng;
for(int i=0;i<n;i++)
if (SNT(a[i]==1) cout<<a[i]<<"\t";
}

Trên đây là ý tưởng của mình, không biết có hợp với câu hỏi của bạn không nữa?

Nhuan_Trang_Only_Love
03-02-2007, 10:56 AM
int SNT(int n)
{
int count=0;
for(int i=1;i<n;i++)
if (n%i==0) count++;
if (count==1) return 1 //TRUE
else return 0; //FALSE
}
void main()
{
nhập mảng;
for(int i=0;i<n;i++)
if (SNT(a[i]==1) cout<<a[i]<<"\t";
}

Trên đây là ý tưởng của mình, không biết có hợp với câu hỏi của bạn không nữa?

Tất nhiên là như vậy rồi,nguyên lý vẫn phải sử dụng biến đếm.tuy nhiên hàm
int SNT(int n)..... này chúng ta có thể chuyển dang BOOL (trả lại giá trị TRUE OR FALSE) có lẽ sẽ tiết kiệm bộ nhớ hơn (tôi nghĩ vậy). và (int n) co thể truyền tham số kiểu tham trị như vậy tốc độ nhanh hơn.
Có gì sai xin chỉ giùm

Nhuan_Trang_Only_Love
03-02-2007, 11:06 AM
Thế thì cách của you chỉ dùng được cho câu hỏi này thôi, giả sử đây chỉ là 1 câu hỏi trong 1 bài tập thì sao nào? Dĩ nhiên you vẫn phải nhập 1 mảng vào và làm giống tôi nói thôi. Cách làm thì có nhiều cách, lựa cách nào để cho mình ko gặp rắc rối về sau là được rồi. Nói đơn giản hơn là thiết kế chương trình sao cho có khả năng mở rộng bài toán, đó mới là thiết kế :D

Bác huynguyen này, cách này * lại ko có tính kế thừa vậy?
kiểm tra luôn chứ có làm gì thay đổi mảng nhập vào đâu?
Đồng ý với bác là mỗi bài có nhiều cách làm khác nhau rùi,lựa chọn cách nào hợp lý là được.Đây em chỉ đưa ra cách của mình để tham khảo.Và hoàn toàn sử dụng nếu nó là câu hỏi trong bài tập nhiều phần khác chứ.
Nếu có gì giải thích giùm em kỹ hơn nhé , thanks>>>>>>>>>

huynguyen
03-02-2007, 11:46 AM
Bác huynguyen này, cách này * lại ko có tính kế thừa vậy?
kiểm tra luôn chứ có làm gì thay đổi mảng nhập vào đâu?
Đồng ý với bác là mỗi bài có nhiều cách làm khác nhau rùi,lựa chọn cách nào hợp lý là được.Đây em chỉ đưa ra cách của mình để tham khảo.Và hoàn toàn sử dụng nếu nó là câu hỏi trong bài tập nhiều phần khác chứ.
Nếu có gì giải thích giùm em kỹ hơn nhé , thanks>>>>>>>>>

1 bài tập yêu cầu nhập vào 1 mảng rồi đếm số phần tử của mảng, sắp xếp bảng, kiểm tra xem có bao nhiêu snt, kiểm tra xem có bao nhêu số chẵn, lẻ ...
Bạn bảo là khi nhập thì cho 1 bước kiểm tra rồi lọc mấy phần tử snt sang 1 bên thì mất tiêu cái mảng của người ta rồi, lấy đâu mà làm được nữa?

tuy nhiên là khi nhập vào sao chúng ta không kiểm tra luôn xem số đó có là số nguyên tố không. nếu là nguyên tố thì save vào mảng khác , và biến đếm có bao nhiêu so nguyên tố .
Tôi nói có phải ko?

int SNT(int n)
{
int count=0;
for(int i=1;i<n;i++)
if (n%i==0) count++;
if (count==1) return 1 //TRUE
else return 0; //FALSE
}

Lần sau bỏ vào tag code nhé
Giải thuật tốt nhưng chưa tối ưu, có khá nhiều giải thuật về snt tối ưu hơn rất nhiều.
Giới thiệu cho bạn 1 phương pháp tối ưu mà tôi vừa tìm được:

Bài toán này đã trở nên rất đỗi quen thuộc với chúng ta, trong bài này chúng ta sẽ bàn đến cách kiểm tra 1 số nguyên N cho trước có nguyên tố hay không trong phạm vi kiến thức số học sơ cấp.

Có rất nhiều cách, các cách thông thường là:
+ Xét các số từ 1 đến N xem có bao nhiêu số là ước của N rồi so sánh với 2. Cách này chạy rất chậm!
+ Xét các số từ 2 đến sqrt(N) rồi nếu là ước của N thì dừng lại, nhanh hơn 1 chút!

Ta sẽ bàn 1 cách nhanh hơn nữa:
Rõ ràng cái ta cần là làm sao giảm bớt số lượng số phải đem ra thử có phải là ước của N hay không. Trong danh sách này, có thể thừa (như 2 cách trên thừa rất nhiều) nhưng tuyệt đối không được thiếu các số nguyên tố bé hơn hoặc bằng sqrt(N). Vậy thì ta sẽ duyệt các số này theo 1 quy luật nào đó. Quy luật đó là gì?

Nhận xét: 1 số nguyên tố chia cho 6 dư 1 hoặc 5 (dễ dàng chứng minh) suy ra tập các số nguyên chia 6 dư 1 hoặc 5 sẽ bao trùm tập các số nguyên tố.

Từ đây ta có thuật toán: ta chỉ xét các số bé hơn hoặc bằng sqrt(N) mà chia 6 dư 1 hoặc 5 mà thôi, nếu N chia hết cho bất cứ 1 số nào trong đó thì N là hợp số, trái lại N là nguyên tố.

không phải ngẩu nhiên mà tôi chọn hằng số k= 6 này. Bài toán trở thành tìm số k mà từ 1 tới k-1 có ít số nguyên tố cùng nhau với nó nhất. Khi đó tỉ lệ phải xét chính là tỉ số các số nguyên tố cùng nhau này với k

thực nghiệm thì thấy số k tổng quát là tích của vài số nguyên tố đầu tiên, tất nhiên càng nhiều thì tỉ lệ phải xét càng nhỏ nhưng cài đặt có phần phức tạp hơn

các bạn mới làm toán thì bỏ qua tìm số k này, giỏi lên một tí các bạn cho k=2 để loại các số chẳn
rồi k=6 để loại các số chia hai huặc ba
nếu k=2*3*5=30( tỉ lệ phải xét, 4/15) thì tốc độ đc cải thiện đáng để, bạn thử cài đặt nhé, chú ý cái đặt thế nào cho thông minh

khi nghịch mã nguồn của Maple thì thấy nó lấy k là tích các số nguyên tố <1000 cơ
Còn đây là cách mình thường dùng để xét snt

#include <iostream>//bt006
#include <cmath>
using namespace std;
int main(){
cout <<"Chuong trinh xac dinh so nguyen to\n";
int n;
do {cout <<"Nhap so nguyen (n >=2): "; cin >>n; }
while (n < 2);
int i = 2, m = sqrt(n);
while ((i <= m) && ((n % i) != 0)) i++;
if (i <= m) cout <<n <<" khong la so nguyen to";
else cout <<n <<" la so nguyen to";
cout <<endl; system("pause"); return 0;
}
Dưới đây là thuật toán tìm tất cả các snt nhỏ hơn n cho trước, còn gọi là sàng Eratosthene

#include <iostream>//bt010
#include <iomanip>
#include <cmath>
#define maxn 1000
using namespace std;
void eratosthene(bool a[], int n);
int main()
{
int n;
do {cout <<"Nhap n: "; cin >>n; }
while ((n < 0)||(n > 1000));
bool sang[maxn];
eratosthene(sang,n);
for (int i = 1; i <= n; i++)
if (sang[i]) { cout <<setw(3) <<i; }
cout <<endl; system("pause"); return 0;
}
void eratosthene(bool a[], int n)
{
a[0] = false; a[1] = false;
int i,j;
for (i = 2; i <= n; i++) a[i] = true;
for (i = 2; i <= int(sqrt(n)); i++)
if (a[i]) for (j = 2; j <= n/i; j++) a[i*j] = false;
}

Nhuan_Trang_Only_Love
03-02-2007, 01:07 PM
1 bài tập yêu cầu nhập vào 1 mảng rồi đếm số phần tử của mảng, sắp xếp bảng, kiểm tra xem có bao nhiêu snt, kiểm tra xem có bao nhêu số chẵn, lẻ ...
Bạn bảo là khi nhập thì cho 1 bước kiểm tra rồi lọc mấy phần tử snt sang 1 bên thì mất tiêu cái mảng của người ta rồi, lấy đâu mà làm được nữa?
Tôi nói có phải ko?

Ầy , vậy bác ko hiểu ý em rùi. em có bảo là loại nó vào một bên đâu.
Chỉ là nhớ nó vào một mảng khác thôi mờ.

1 bài tập yêu cầu nhập vào 1 mảng rồi đếm số phần tử của mảng, sắp xếp bảng, kiểm tra xem có bao nhiêu snt, kiểm tra xem có bao nhêu số chẵn, lẻ ...
bài này cũng làm tương tự được đó.
Ko hề làm thay đổi mảng nhập vào mà

huynguyen
03-02-2007, 07:36 PM
OK, hiểu lầm ý của you, ko sao, nhưng you sẽ tốn thêm 1 mảng nữa, vậy là tốn tài nguyên rồi :D

phamtuanic
15-02-2007, 04:09 PM
Thử sữa chỗ này thử:
int snt(int n)
{
int d=0;
for(int i=1;i<=n;i++)//kiểm tra số nguyên tố
if(n%i==0)
d++;
return (d==2);
}

Xcross87
16-02-2007, 11:11 AM
Anh huynguyen đưa thuật toán và lời giải đúng đó .
Pete có đóng góp thêm . Viết 1 class Nguyên Tố sau đó cho một loạt lớp kế thừa >> Như vậy thì có phải là giải quyết được các vấn đề về số nguyên tố kô ...:D
Chằng hạn :
1. Kiểm tra 1 số có nguyên tố hay kô ?
2. In ra danh sách số nguyên tố từ m -> n
3. Xuất ra từ mảng cho trước các số nguyên tố
4. Các phép tính trên số nguyên tố
......
Còn nhiều lắm ^.^!

ragonnet
01-04-2009, 11:33 PM
đây là code số nguyên tố mình tự làm



#include <iostream>

using namespace std;
void main ()


{
int i=1,n,s,kt;
char dk;
do{
cout<<" ""Kiem tra so nguyen to"<<endl;
cout<<"nhap so can kiem tra:";
do{
cin>>n;}
while(n<=0);
if (n==1 || n==2) cout<<"la so nguyen to"<<endl;
else{
while (i<(n-1)) {
i++;
s=n%i;

if (s==0) {kt=0;
break;

}



else
if(s!=0) kt=1;


}}
if (kt==0) cout<<"day khong phai la so nguyen to"<<endl;
else
if(kt==1) cout<<"day la so nguyen to"<<endl;
cout<<" "<<"ban co muon tiep tuc khong (c/k):";
cin>>dk;
system("pause");}
while (dk=='c');

}bài toán nhập 1 số và xuất ra thừa số nguyên tố của số đó:
( các bạn coi rồi góp ý cho mình)


#include<iostream>
void kiemtra (long so,long &kt);
void kiemtraxuatl (long so);
void kiemtraxuatcl (long so);
using namespace std;
void main()
{
long i,n,a,b,dem,c,kq;
char dk;
cout<<"phan tich 1 so ra thua so nguyen to"<<endl;
do
{
cout<<"nhap so can tinh:";
cin>>n;
cout<<" "<<"thua so nguyen to cua"<<" "<< n <<" "<<"la:";

kiemtra(n,kq);
if (kq==1) cout<<n<<endl;
else
{ i=2;
dem=0;
b=n%2;
if(b==0)
{
while (i<=n)
{
a=n%i;
n=n/i;
if(a==0)
{
if (a==0 && n!=1)
dem++;
else
if (a==0 && n==1)
{
dem++;
cout<<i<<"^"<<dem<<endl;
dem=0;
}

}
if (a!=0)
{ c=(n*i+a);
kiemtra(c,kq);
if (kq==1)
{
cout<<i<<"^"<<dem<<"*"<<c<<endl;
dem=0;
break;
}
else
{ cout<<i<<"^"<<dem<<"*";
kiemtraxuatcl(c);
dem=0;
break;
}
}

}

}
if (b!=0)
{ i=3;
while(i<=n)
{
a=n%i;
n=n/i;
if (a==0)
{
if (n!=1)
dem++;
else
if(n==1)
{
dem++;
cout<<i<<"^"<<dem<<endl;
dem=0;
}
}

if (a!=0)
{
c=(n*i+a);
kiemtra(c,kq);
if (kq==1)
{
cout<<i<<"^"<<dem<<"*"<<c<<endl;
break;
}
else
{
if (dem<1)
{
kiemtraxuatl(c);
dem=0;
break;
}
else
if (dem>=1)
{
cout<<i<<"^"<<dem<<"*";
kiemtraxuatl(c);
dem=0;
break;
}
}

}
}
}

}
cout<<"ban co muon tinh tiep khong (c/k):";
cin>>dk;
system("pause");
}
while(dk=='c');
}


void kiemtra (long so,long &kt)
{
long i=1,s;

if (so==1 || so==2) kt=1;
else
{
while (i<(so-1))
{
i++;
s=so%i;
if (s==0)
{
kt=0;
break;
}
else
if (s!=0)
kt=1;


}
}

}
void kiemtraxuatl (long so)
{
long i=3,e,a,dem=0,kq;
while(i<=so)
{
a=so%i;
so=so/i;
if (a==0)
{
if (a==0 && so!=1)
dem++;
else
if(a==0 && so==1)
{
dem++;
cout<<i<<"^"<<dem<<endl;
dem=0;
}
}

if (a!=0)
{
e=(so*i+a);
kiemtra(e,kq);
if (kq==1)
{
cout<<i<<"^"<<dem<<"*"<<e<<endl;
break;
}
else
{
if (dem>=1 && so!=1 )
{
cout<<i<<"^"<<dem<<"*";
so=e;
dem=0;
i=i+2;
}
if (dem<1)
{
so=e;
dem=0;
i=i+2;
}
}

}
}
}

void kiemtraxuatcl (long so)
{
long i,c,a,dem=0,kq;
i=3;
while(i<=so)
{
a=so%i;
so=so/i;
if (a==0)
{
if (so!=1)
dem++;
else
if(so==1)
{
dem++;
cout<<i<<"^"<<dem<<endl;
dem=0;
}
}

if (a!=0)
{
c=(so*i+a);
kiemtra(c,kq);
if (kq==1)
{
cout<<i<<"^"<<dem<<"*"<<c<<endl;
break;
}
else
{
if (dem<1)
{
kiemtraxuatl(c);
break;
}
else
if (dem>=1)
{
cout<<i<<"^"<<dem<<"*";
kiemtraxuatl(c);
break;
}
}

}
}
} (:))

đảm bảo chạy được không tin thì thử!