Trang 1 trên tổng số 7 123... Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 61 kết quả

Đề tài: Cách kiểm tra nhanh N có phải là số nguyên tố

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

    Mặc định Cách kiểm tra nhanh N có phải là số nguyên tố

    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ơ

  2. #2
    Ngày gia nhập
    08 2006
    Nơi ở
    Hải Phòng
    Bài viết
    218

    Trích dẫn Nguyên bản được gửi bởi huynguyen Xem bài viế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
    Em chưa hiểu lắm chỗ này, tại sao phải tìm số k để có ít số nguyên tố cùng nhau với nó nhất.

  3. #3
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    Hay lắm HuyNguyen . Những điều này học thì ko suy nghĩ ra , đọc một thấy thú vị .

    Em chưa hiểu lắm chỗ này, tại sao phải tìm số k để có ít số nguyên tố cùng nhau với nó nhất.
    VD như tớ xét số 19^2 có phải là số nguyên tó hay không thì thông thường phải duyệt đến số 19 . Trong quá trình đó ta có sự lặp lại giữa /2 rồi /4 đồng thời là /3 và /6 .
    Nhìn đây nè :
    rồi k=6 để loại các số chia hai huặc ba
    Chắc đến đây là hiểu rồi .

  4. #4
    Ngày gia nhập
    08 2006
    Nơi ở
    Hải Phòng
    Bài viết
    218

    * To kidkid: Dùng k=6 để loại các số chia hết cho 2, 3, 4, 6 thì em hiểu rồi nhưng tại sao phải chọn k là tích các số nguyên tố.

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

    Số là số chia hết cho chính nó và 1 vì thế nên ta có thể ko xét 1 mà chỉ xét từ sqrt của nó đến nó.Làm cách này tuy nó hơi khó hiểu chút nhưng rất nhanh đấy,cách này Thầy mình đã chấp nhận

  6. #6
    Ngày gia nhập
    12 2007
    Bài viết
    28

    Mặc định Cách kiểm tra nhanh N có phải là số nguyên tố

    Số là số chia hết cho chính nó và 1 vì thế nên ta có thể ko xét 1 mà chỉ xét từ sqrt của nó đến nó.Làm cách này tuy nó hơi khó hiểu chút nhưng rất nhanh đấy,cách này Thầy mình đã chấp nhận
    Ủa, sao không xét từ 2 đến sqrt(n), như vậy có lẽ nhanh 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ơ
    Theo em hiểu thì khi xét số chia dạng mk + r < sqrt(n), ta sẽ bỏ không xét các số có USCLN(r, k) > 1 phải không ạ? Nếu tính trước thì chắc là nhanh, nhưng nếu đến lúc chạy mới xét thì chắc tốc độ cũng giảm đáng kể.
    Có phải Maple dùng cách lưu sẵn các số này không ạ?
    Đã được chỉnh sửa lần cuối bởi blackpawn : 16-02-2008 lúc 09:40 AM. Lý do: gõ nhầm :)

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

    ko biết sao chứ mỗi khi làm toán mình hay bỏ cái gì liên quan tới số 1 đi vì có nó vào thấy thêm rối hơn

  8. #8
    Ngày gia nhập
    02 2008
    Bài viết
    4

    Trích dẫn Nguyên bản được gửi bởi huynguyen Xem bài viết

    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ố.
    thế 2 và 3 thì sao

    Định lý nhỏ Fecma áp dụng vào mà máy tính tính toán được kết quả lớn thì rất hay
    Đã được chỉnh sửa lần cuối bởi lag_nao : 16-02-2008 lúc 09:21 PM.

  9. #9
    Ngày gia nhập
    03 2008
    Bài viết
    2

    hình như chưa đc đâu anh ạ vì số 25 chia 6 dư 1 mà có phải snt đâu

  10. #10
    Ngày gia nhập
    03 2008
    Nơi ở
    TP HCM
    Bài viết
    30

    Uh nhỉ.Vì số 49 chia 6 dư 1 cũng đâu phải số nguyên tố

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

  1. Thu mua phế liệu giá cao, thanh toán nhanh/ mua phế liệu
    Gửi bởi taikhoan005 trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 5
    Bài viết cuối: 27-09-2012, 03:19 PM
  2. Bán nhanh 2 em sony F22, F23 i7 card 1GB nguyên seal kiếm tiền ăn Tết
    Gửi bởi gso.ecom trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 2
    Bài viết cuối: 19-01-2012, 11:25 AM
  3. Đề xuất Đem tag [PHP] để ở phần trả lời nhanh
    Gửi bởi nh0cbilly trong diễn đàn Ý kiến, đề xuất và khiếu nại
    Trả lời: 1
    Bài viết cuối: 08-01-2011, 09:33 PM
  4. Bài tập C++ kiêm tra số nguyên dương cho trước có phải toàn số nguyên tố
    Gửi bởi ngoctrungbmt trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 5
    Bài viết cuối: 01-01-2011, 09:57 AM
  5. Thuật toán tìm số nguyên tố nhanh nhất?
    Gửi bởi MYLOVEPHUCLAM trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 3
    Bài viết cuối: 16-10-2010, 05:29 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