Công cụ bảo vệ mã nguồn .NET mạnh nhất, không thể unpack, miễn phí cho các khách hàng đầu tiên đăng ký.
Từ 1 tới 6 trên tổng số 6 kết quả

Đề tài: Cần giải thích chi tiết thuật toán tìm số nguyên tố?

  1. #1
    Ngày gia nhập
    09 2013
    Nơi ở
    Phòng VIP trong bệnh viện thần kinh trung ương II
    Bài viết
    66

    Mặc định Cần giải thích chi tiết thuật toán tìm số nguyên tố?

    Chào các bạn mình vừa mới tham gia forum luôn, bấy lâu nay học C++ mình vẫn mãi thăc mắc về thuật toán tìm số nguyên tố, hỏi nhiều nơi rồi nhưng vẫn ko hiểu được, có lẽ mình ngu thiệt. Chấp nhận số phận nhưng ko đồng hàng số phận, mình ko vì sỉ diện mà ko hỏi đến nơi đến chốn cho đến khi hiểu mới thôi. Sau đây là code của mình:
    Code:
    # include<stdio.h>
    # include<conio.h>
    # include<math.h>
    # include<string.h>
    # include<iostream>
    using namespace std;
    
    void checkSNT_1(int n)
    {
    	int i,temp=0;
    	for(i=0;i<n;i++)
    	{
    		if(i%n==0)
    			temp++;
    	}
    	if(temp==2)
    		cout<<"\nDay la so nguyen to.";
    	else
    		cout<<"\nDay KHONG la so nguyen to.";
    }
    
    void checkSNT_2(int n)
    {
    	if(n==2|n==3|n==5|n==7)
    		cout<<"\nDay la so nguyen to";
    	else if (n % 2!=0 && n % 3!=0 && n % 5!=0 && n % 7!=0 && n!=1)
    	{
    		cout<<"\nDay la so nguyen to";
    	}
    	else
    		cout<<"\nDay KHONG phai la so nguyen to!!!";
    }
    
    void checkSNT_3(int n)
    {
    	bool check= true;
    	for(int i=0;i<sqrt(n);i++)
    	{
    		if(i%n==0)
    			check= false;
    	}
    	if(check)
    		cout<<"\nDay la so nguyen to.";
    	else
    		cout<<"\nDay KHONG la so nguyen to!";
    }
    
    void main()
    {
    	int snt;
    	char x[1];
    flag: 
    	cout<<"Nhap vao so can kiem tra: ";
    	cin>>snt;
    	checkSNT_3(snt);
    	cout<<"\nBan co muon tiep tuc ko, Y/N?";
    	cin>>x;
    	if(stricmp(x,"y")==0)
    		goto flag;
    	else
    		exit(1);
    	getch();
    }
    Cụ thể mình muốn hỏi như sau:
    Ở 3 thuật toán trên(theo đúng thứ tự mình đặt tên luôn rồi) thì thuật toán thứ 2 là cơ bản và dễ hiểu nhất nên mình tự làm và tự hiểu, còn thuật toán thứ 1 và thứ 3 thì copy trên mạng nhưng ko thể nào hiểu nổi.
    Cụ thể ở checkSNT_1 tại sao khi biến temp==2 thì số n lại là số nguyên tố(SNT)? và trong vòng for tăng biến temp++ để là gì?
    Còn ở checkSNT_3 tại sao chúng ta ko kiểm tra đến n mà chỉ là sqrt(n)? và tại sao khi check==true thì n là SNT?
    À mà còn nữa thuật toán thứ 3 ko đúng với số 0, nó báo số 0 là số nguyên tố như vậy là sai, mà sai như thế nào thì mình ko hiểu các bạn sửa dùm luôn!
    Mong mọi người ai giải thích cho mình chi tiết càng tốt, xem như giải thích cho đứa dốt toán hiểu vậy!
    Cảm ơn các bạn trước!
    Công cụ bảo vệ mã nguồn .NET mạnh nhất hiện tại, miễn phí cho các khách hàng đầu tiên đăng ký.
    Còn 22 năm nữa ta sẽ tự tại thả cần.

  2. #2
    Ngày gia nhập
    01 2013
    Bài viết
    1,479

    Hàm số 2 sai bét. (11*13=143)
    Hàm số 1 thì làm theo định nghĩa SNT, nhưng quá chậm.
    Hàm số 3 mới đúng.
    - Chỉ cần không có ước nào (khác 1) <= sqrt(n) là c/m được đó là SNT rồi.
    Vì nếu ta có d1,d2 khác 1 và n để d1*d2==n thì d1<=sqrt(n) => d2>=sqrt(n).
    Còn zero thì phai có thêm điều kiện ban đầu.

  3. #3
    Ngày gia nhập
    09 2013
    Nơi ở
    Phòng VIP trong bệnh viện thần kinh trung ương II
    Bài viết
    66

    Trích dẫn Nguyên bản được gửi bởi prog10 Xem bài viết
    Hàm số 2 sai bét. (11*13=143)
    Hàm số 1 thì làm theo định nghĩa SNT, nhưng quá chậm.
    Hàm số 3 mới đúng.
    - Chỉ cần không có ước nào (khác 1) <= sqrt(n) là c/m được đó là SNT rồi.
    Vì nếu ta có d1,d2 khác 1 và n để d1*d2==n thì d1<=sqrt(n) => d2>=sqrt(n).
    Còn zero thì phai có thêm điều kiện ban đầu.
    Bạn à có thể nói chi tiết hơn nữa ko? cậu cứ xem như giải thích cho 1 đứa học sinh cấp 2 hiểu đi!
    Bạn đọc kỹ topic của mình hỏi gì để trả lời nhé!
    Thanks vì đã trả lời!
    Còn 22 năm nữa ta sẽ tự tại thả cần.

  4. #4
    Ngày gia nhập
    01 2013
    Bài viết
    1,479

    Trích dẫn Nguyên bản được gửi bởi dangngocgiabao Xem bài viết
    Bạn à có thể nói chi tiết hơn nữa ko? cậu cứ xem như giải thích cho 1 đứa học sinh cấp 2 hiểu đi!
    Bạn đọc kỹ topic của mình hỏi gì để trả lời nhé!
    Thanks vì đã trả lời!
    Đừng dùng hàm số 1 nữa, có vậy thôi ah`
    Hàm 3 thì c/m ở đây:
    Giả sử n, p, q là số tự nhiên lớn hơn 1 thỏa n=pq => p, q là 2 ước của n.
    Mà tồn tại p<=căn n sao cho p là ước của n <=> tồn tại q=n/p>=n/căn n=căn n sao cho q là ước của n.
    Với số nguyên tố, không tồn tại p <=> không tồn tại q => chỉ cần vét từ 2 đến căn n là đã xác định được tính nguyên tố của n.

  5. #5
    Ngày gia nhập
    05 2013
    Nơi ở
    Quảng Ninh-Bình Trị Thiên-Việt Nam
    Bài viết
    37

    Hàm số 1 sai. Check kiểu gì cũng ra ko phải là số nguyên tố. Lý do: Trong khoảng từ 0 tới n-1 ko có quá 1 số chia hết cho n, temp bao giờ cũng =1. Đã sai thì quan tâm làm gì nhỉ
    Cuộc sống mất dạy nuôi ta lớn
    Dòng đời khốn nạn dạy ta khôn
    Không đâm không chém đời không nể
    Không tiền bạc không bạc gái không theo

  6. #6
    Ngày gia nhập
    10 2012
    Nơi ở
    Hồ Chí Minh city
    Bài viết
    9

    Mặc định mình nói cái hàm số 3

    nếu n(n > 1) không phải là số nguyên tố thì có thể viết n = k1 * k2 mà 2 <= k1 <= k2 <= n -1. mà k1 * k1 <= k1 * k2(=n) nên k1 <= can(n). vì vậy nên chỉ kiểm tra trong đoạn [2, can(n)]

    C Code:
    1. bool is_prime(int n)
    2. {
    3.     if(n == 1 || n == 0)
    4.         return false;
    5.     for(int i = 2; i <= sqrt(n); i++)
    6.     {
    7.         if(n % i == 0)
    8.             return false;
    9.     }
    10.     return true;
    11. }
    Công cụ bảo vệ mã nguồn .NET mạnh nhất hiện tại, miễn phí cho các khách hàng đầu tiên đăng ký.
    Đã được chỉnh sửa lần cuối bởi hnhuy : 15-09-2013 lúc 09:30 AM.

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

  1. Bài tập C giải thuật nhập vào số nguyên n in ra n số nguyên tố đầu tiên?
    Gửi bởi LTC trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 48
    Bài viết cuối: 25-04-2013, 07:40 PM
  2. Trả lời: 11
    Bài viết cuối: 17-06-2011, 12:25 AM
  3. Lập trình C++ Giải thuật nhân 2 số nguyên lớn trên C++?
    Gửi bởi kaka_nsk_91 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: 03-04-2010, 10:29 PM
  4. Cho hỏi kĩ hơn về thuật giải bài tìm số nguyên tố
    Gửi bởi chocolate1 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 19
    Bài viết cuối: 13-02-2008, 03:43 PM
  5. Thuật giải đếm số nguyên tố
    Gửi bởi LPS86 trong diễn đàn Nhập môn lập trình C#, ASP.NET
    Trả lời: 4
    Bài viết cuối: 28-12-2007, 06:53 AM

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