Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 13 kết quả

Đề tài: Bài tập C | Xuất số nguyên tố

  1. #1
    No Avatar
    server1988 Khách

    Mặc định Bài tập C | Xuất số nguyên tố

    em cần nhập 1 mãng vào và xuất số nguyên tố ra

    C++ Code:
    1. #include<iostream.h>
    2. #include<conio.h>
    3. void nhap(int a[],int &n);
    4. int snt(int a[],int n);
    5. void xuat(int a[],int n);
    6. void main()
    7. {
    8.     clrscr();
    9.    int a[100],n;
    10.    nhap(a,n);
    11.    xuat(a,n);
    12.    getch();
    13. }
    14. void nhap(int a[],int &n)
    15. {
    16.     cout<<"Nhap n:";
    17.    cin>>n;
    18.    for(int i=0;i<n;i++)
    19.    {
    20.     cout<<"Nhap a["<<i<<"]";
    21.       cin>>a[i];
    22.    }
    23. }
    24. int snt(int a[],int n)
    25. {
    26.     int d=0;
    27.    for(int i=0;i<n;i++)
    28.     for(int j=1;j<a[i];j++)
    29.       {
    30.         if(a[i]%j)
    31.          d++;
    32.          if(d==2)
    33.          return d==2;
    34.       }
    35. }
    36. void xuat(int a[],int n)
    37. {
    38.     for(int i=0;i<n;i++)
    39.     if(snt(a[i]))
    40.       cout<<"So nguyen to la:"<<a[i];
    41. }
    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

  2. #2
    Ngày gia nhập
    11 2006
    Bài viết
    633

    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.

  3. #3
    No Avatar
    Nhuan_Trang_Only_Love Khách

    Trích dẫn Nguyên bản được gửi bởi huynguyen
    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á

  4. #4
    Ngày gia nhập
    11 2006
    Bài viết
    633

    đồ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ế

  5. #5
    Ngày gia nhập
    01 2007
    Bài viết
    412

    C++ Code:
    1. int SNT(int n)
    2. {
    3.         int count=0;
    4.         for(int i=1;i<n;i++)
    5.              if (n%i==0)   count++;
    6.         if (count==1) return 1 //TRUE
    7.         else return 0; //FALSE
    8. }
    9. void main()
    10. {
    11. nhập mảng;
    12. for(int i=0;i<n;i++)
    13.   if (SNT(a[i]==1) cout<<a[i]<<"\t";
    14. }

    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?

  6. #6
    No Avatar
    Nhuan_Trang_Only_Love Khách

    Mặc định Bài tập C | Xuất số nguyên tố

    Trích dẫn Nguyên bản được gửi bởi neverland87 Xem bài viết
    C++ Code:
    1. int SNT(int n)
    2. {
    3.         int count=0;
    4.         for(int i=1;i<n;i++)
    5.              if (n%i==0)   count++;
    6.         if (count==1) return 1 //TRUE
    7.         else return 0; //FALSE
    8. }
    9. void main()
    10. {
    11. nhập mảng;
    12. for(int i=0;i<n;i++)
    13.   if (SNT(a[i]==1) cout<<a[i]<<"\t";
    14. }

    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

  7. #7
    No Avatar
    Nhuan_Trang_Only_Love Khách

    Trích dẫn Nguyên bản được gửi bởi huynguyen Xem bài viết
    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ế
    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>>>>>>>>>

  8. #8
    Ngày gia nhập
    11 2006
    Bài viết
    633

    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
    C++ Code:
    1. #include <iostream>//bt006
    2. #include <cmath>
    3. using namespace std;
    4. int main(){
    5.     cout <<"Chuong trinh xac dinh so nguyen to\n";
    6.     int n;
    7.     do {cout <<"Nhap so nguyen (n >=2): "; cin >>n; }
    8.     while (n < 2);
    9.     int i = 2, m = sqrt(n);
    10.     while ((i <= m) && ((n % i) != 0)) i++;
    11.     if (i <= m) cout <<n <<" khong la so nguyen to";
    12.     else cout <<n <<" la so nguyen to";
    13.     cout <<endl; system("pause"); return 0;
    14. }
    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
    C++ Code:
    1. #include <iostream>//bt010
    2. #include <iomanip>
    3. #include <cmath>
    4. #define maxn 1000
    5. using namespace std;
    6. void eratosthene(bool a[], int n);
    7. int main()
    8. {
    9.     int n;
    10.     do {cout <<"Nhap n: "; cin >>n; }
    11.     while ((n < 0)||(n > 1000));
    12.     bool sang[maxn];
    13.     eratosthene(sang,n);
    14.     for (int i = 1; i <= n; i++)
    15.          if (sang[i]) { cout <<setw(3) <<i; }
    16.     cout <<endl; system("pause"); return 0;
    17. }
    18. void eratosthene(bool a[], int n)
    19. {
    20.     a[0] = false; a[1] = false;
    21.     int i,j;
    22.     for (i = 2; i <= n; i++) a[i] = true;
    23.     for (i = 2; i <= int(sqrt(n)); i++)
    24.         if (a[i]) for (j = 2; j <= n/i; j++) a[i*j] = false;
    25. }

  9. #9
    No Avatar
    Nhuan_Trang_Only_Love Khách

    Trích dẫn Nguyên bản được gửi bởi huynguyen Xem bài viết
    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ờ.
    Trích dẫn Nguyên bản được gửi bởi huynguyen Xem bài viết
    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à

  10. #10
    Ngày gia nhập
    11 2006
    Bài viết
    633

    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

Các đề tài tương tự

  1. Bài tập C++ xuất ra số nguyên tố thứ n
    Gửi bởi minhngoc07 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 6
    Bài viết cuối: 04-04-2013, 10:55 PM
  2. Bài tập C Nhập vào một số nguyên N và xuất ra các số nguyên tố <N
    Gửi bởi xitrum5393 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 11
    Bài viết cuối: 17-10-2011, 02:21 PM
  3. Bài tập C++ Lồng hàm KT số nguyên tố trog hàm xuất nguyên tố
    Gửi bởi huy9810814 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 4
    Bài viết cuối: 17-01-2011, 08:00 PM
  4. Bài tập C++ nhập mảng gồm n (5<n<10) phần tử, xuất mảng và xuất ra các số nguyên tố của mảng
    Gửi bởi viettan trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 7
    Bài viết cuối: 08-01-2011, 10:23 PM
  5. Xuất số nguyên tố
    Gửi bởi sonas trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 3
    Bài viết cuối: 09-03-2009, 10:37 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn