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ố 20 kết quả

Đề tài: Cho hỏi kĩ hơn về thuật giải bài tìm số nguyên tố

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

    Cool Cho hỏi kĩ hơn về thuật giải bài tìm số nguyên tố

    Kiểm tra 1 số bất kì có phải là số nguyên tố hay ko

    Code:
    #include "stdio.h"
    #include "conio.h"
    #include "math.h"
    
    int main()
    {
       int n;
       printf("\nHay nhap vao so can kiem tra: ");scanf("%d",&n);
       int bNguyenTo;
       if (n == 2) bNguyenTo = 1;
       else
        {
           bNguyenTo = 1;
           for (int i = 2; i <= sqrt(n); i++)
    	  if ((n % i) == 0)
    	    {
    	       bNguyenTo = 0;
    	       break;
    	    }
        }
        if (bNguyenTo) printf("n la so nguyen to");
        else printf("n la hop so");
    getch();
    return 0;
    
    }
    Để chỉ ra 1 số không phải là số nguyên tố chỉ cần chỉ ra nó có 1 ước số khác 1 và chính nó => theo:
    Code:
    Vì n là hợp số => tồn tại một số p(p#1, p#n) để n chia hết cho p.
    Đặt q= n/p => q#1, q#n.
    đặt r= min(p, q) => r<=p && r<=q
    => r^2 <= p*q = n
    => r <= sqrt(n) mà r là ước của n (do r =p hoặc r =q)
    => n tồn tại một ước số nhỏ hơn hoặc bằng căn bậc 2 của n và khác 1
    => đpcm
    P/S: kí hiệu "#" nghĩa là khác ^_^
    thì i<=sqrt(n) là đủ. VD: sqrt(21) = 4.582... thì 21 chia hết cho 3 => 21 không là số nguyên tố.
    Nhưng để chỉ ra 1 số không là số nguyên tố thì phải chỉ ra nó không có bất kì 1 ước số nào ( trừ 1 và chính nó ). Vậy sao có thể khẳng định sqrt(n)<i<n thì n không chia hết cho i ? Mong mọi người giải thích giúp ! Chỗ này mình không hiểu lắm !
    Đã được chỉnh sửa lần cuối bởi chocolate1 : 12-02-2008 lúc 02:58 PM. Lý do: thêm chỗ viết thiếu

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

    Bạn có lẽ cần đọc lại số học ^^!
    G/s n = i*j => ít nhất 1 trong 2 số phải nhỏ hơn sqrt(n).
    Bạn chỉ cần xét đến sqrt(n) là đủ tại vì phần còn lại là phần bù để đc n ^^!
    Is the moon rising...

  3. #3
    Ngày gia nhập
    09 2006
    Nơi ở
    /usr/share/.hack@
    Bài viết
    1,433

    Trích dẫn Nguyên bản được gửi bởi darkan Xem bài viết
    Bạn có lẽ cần đọc lại số học ^^!
    G/s n = i*j => ít nhất 1 trong 2 số phải nhỏ hơn sqrt(n).
    Bạn chỉ cần xét đến sqrt(n) là đủ tại vì phần còn lại là phần bù để đc n ^^!
    Bài toán quá đơn giản

    Đề bài: cho một số nguyên dương N được phân tích thành tích của 2 số nguyên dương bất kì. Chứng minh một trong hai thừa số đó không lớn hơn căn bậc 2 của N.

    Giả thiết : N > 0, N nguyên, N = i * j (với i, j là số nguyên dương)
    1) Nếu i = 1 -> j = N. Xong
    2) Nếu i < sqrt(N):
    theo giả thiết : N = i * j < sqrt(N) * j
    <=> sqrt(N) * sqrt(N) < sqrt(N) * j
    <=> <rút gọn sqrt(N) > 0) sqrt(N) < j => xong
    3) Nếu i = sqrt(N) => j = sqrt(N) . Xong
    Không mất tính tổng quát tương tự với j, vai trò không thay đổi.

    Bài toán đã được chứng minh.
    Đã được chỉnh sửa lần cuối bởi Xcross87 : 12-02-2008 lúc 03:52 PM.
    None!

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

    X ngẫn ^^!
    Cái đấy đâu cần chứng minh phức tạp thế ^^!
    G/S i&j đều lớn hơn sqrt(n) => i*j >n(trái gt)
    Is the moon rising...

  5. #5
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Oops !
    PHP Code:
    #include <stdio.h>

    bool IsPrime(int x){
      if(
    32)
        return (
    0xa08a28ac >> x)&1;
      if(!(
    1))
        return 
    0;
      if(!(
    3))
        return 
    0
      
      for(
    int _r 5_r*_r <= x_r += 6)
        if(!(
    _r)||!(% (_r 2)))
          return 
    0;
      return 
    1;
    }

    int main(){
      
    int x;
      
    scanf("%d", &x);
      
    printf("%d"IsPrime(x)); 
      return 
    0;


  6. #6
    Ngày gia nhập
    09 2006
    Nơi ở
    /usr/share/.hack@
    Bài viết
    1,433

    Mặc định Cho hỏi kĩ hơn về thuật giải bài tìm số nguyên tố

    Trích dẫn Nguyên bản được gửi bởi darkan Xem bài viết
    X ngẫn ^^!
    Cái đấy đâu cần chứng minh phức tạp thế ^^!
    G/S i&j đều lớn hơn sqrt(n) => i*j >n(trái gt)
    thiếu, nếu cùng nhỏ hơn và cùng bằng thì sao...

    lời giải đầy đủ xem ở trên nhé
    None!

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

    Hình như cách làm của anh rox_rook dựa vào 1 kết quả toán học khác : mọi số nguyên tố đều có dạng (6k + 1) hoặc (6k + 5) phải không ạ?
    Có điều đoạn này em không hiểu:
    Code:
      if(x < 32) 
        return (0xa08a28ac >> x)&1;
    Em không rõ số 0xa08a28ac có ý nghĩa gì?
    Đã được chỉnh sửa lần cuối bởi blackpawn : 12-02-2008 lúc 07:04 PM. Lý do: Em hiểu thêm 1 chút

  8. #8
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Cái đoạn code đó anh sưu tầm được thôi, làm sao viết nổi T_T. Đoạn đó từng win 1 giải nào đó lâu lắm rùi thì phải, toán tử >> là shift right one bit. Dùng mấy toán tử này thì phụ thuộc vào mã máy cái số đó chắc là mã máy của lão viết đoạn code này thui, còn thuật toán thì rõ ràng mà T_T.
    mọi số nguyên tố đều có dạng (6k + 1) hoặc (6k + 5) phải không ạ?
    Yup. ^_^

  9. #9
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Đây là 1 bài viết về giải thuật này của Kata bên diendantinhoc.com nhưng hình như không có đề tên tác giả, không rõ là có phải hắn viết không, giải thuật của Kata và bài này thực ra là rất tương đồng về nhiều mặt, chỉ khác cách trình bày thôi.


    Chào các bạn! 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ố.
    PHP Code:
    int check(int N) {
        if (
    2) return 0;
        if (
    == == 3) return 1;
        if (
    == == 0) return 0;
        
    int xyt;
        
    52;
        
    = (int)sqrt((double)N);
        while (
    <= t) {
            if (
    == 0) return 0;
            
    += y;
            
    y;
        }
        return 
    1;


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

    Có lẽ em hiểu số 0xa08a28ac để làm gì rồi. Nếu em không nhầm, nó có thể coi tương đương với bảng số nguyên tố.
    Số 0xa08a28ac là 1 số thập lục phân, ta đem biểu diễn dưới dạng số nhị phân. Tính từ phải sang, xét bit ở vị trí thứ x, nếu x là số nguyên tố thì đó là số 1, ngược lại đó là số 0.
    Lấy ví dụ 2 chữ ac ở bên phải.
    ac(hex) = 1 0 1 0 1 1 0 0 (viết cách ra cho dễ nhìn)
    ứng với: 7 6 5 4 3 2 1 0
    Vì 7, 5, 3, 2 là số nguyên tố, nên nó ứng với vị trí số 1. Đó là lí do: sau khi dịch phải số 0xa08a28ac đi x lần, phần tử vị trí x trong chuỗi nhị phân biểu diễn số 0xa08a28ac nằm ở ngay vị trí 1. Do đó động tác & 1 chỉ có tác dụng kiểm tra xem bit ở vị trí x là 0 hay 1.

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

  1. Cần giải thích chi tiết thuật toán tìm số nguyên tố?
    Gửi bởi dangngocgiabao trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 5
    Bài viết cuối: 13-09-2013, 06:10 PM
  2. 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
  3. Trả lời: 11
    Bài viết cuối: 17-06-2011, 12:25 AM
  4. 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
  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