Đang tải...

Chia sẻ Bài toán kiểm tra số nguyên tố

Thảo luận trong 'Tin học, máy vi tính' bắt đầu bởi dungtnut, 25/1/17.

View Users: View Users
  1. dungtnut

    dungtnut Administrator Thành viên BQT

    Tham gia ngày:
    26/12/16
    Bài viết:
    26
    Điểm thành tích:
    3
    Giới tính:
    Nam
    Đây là bài toán cơ bản mà tất cả những ai học lập trình đều phải biết.
    Input: Một số nguyên n
    Output: true or false
    Thuật toán:
    - Kiểm tra số n < 2:
    +Đúng: không phải số nguyên tố
    +Sai:
    PHP:
    for (int i 2<= sqrt((float)n); ++)
       {
           if (
    n%i==0)
           {
               return 
    0;//không phải số nguyên tố
           
    }
       }
    Sau đây là demo code bằng một số ngôn ngữ:
    C/C++:
    PHP:
    int soNguyenTo(int n)
    {
       if (
    n2)   
           return 
    0;

       for (
    int i 2<= sqrt((float)n); ++)
       {
           if (
    n%i==0)
           {
               return 
    0;
           }
       }
       return 
    1;
    }
    c#
    PHP:
     static bool  songuyento(int n)
    {
         
    bool co true;
         if (
    2)
         {
             
    Console.Write("Ban da nhap khong dung.");
             return !
    co;
          }
          else
          {
              for (
    int i 2<=Math.Sqrt(n) + 1i++)
              {
                  if (
    == 0)
                  {
                     
    co false;
                     break;
                  }
              }
          }
          return 
    co;
    }
     
  2. duycop

    duycop Thành viên chăm chỉ

    Tham gia ngày:
    20/1/17
    Bài viết:
    137
    Điểm thành tích:
    63
    Giới tính:
    Nam
    Bài toán kinh điển này bạn nào học lập trình chắc cũng đã thử qua
     
  3. duycop

    duycop Thành viên chăm chỉ

    Tham gia ngày:
    20/1/17
    Bài viết:
    137
    Điểm thành tích:
    63
    Giới tính:
    Nam
    Nói về bài toán kiểm tra một số nguyên dương có phải là số nguyên tố hay không?
    Đầu tiên cần nói thế nào là số nguyên tố?
    Một số nguyên dương được gọi là số nguyên tố khi số đó chỉ chia hết cho 1 và chính nó.
    Nhiều nhà toán học đã thống nhất không coi số 1 là số nguyên tố
    Số 2 là số nguyên dương chẵn duy nhất là số nguyên tố. Nó cũng là số nguyên tố nhỏ nhất.
    Thuận toán kiểm tra số nguyên dương N có phải số nguyên tố hay không?
    bước 1: kiểm tra N có lớn hơn ngưỡng tối thiểu 2 hay không? Nếu chưa đạt ngưỡng thì kết thúc, N ko phải snt
    bước 2: kiểm tra các số nguyên từ 2 đến N-1 xem có số nào mà N chia hết không? nếu có thì N không phải snt, nếu không có số nào bị N chia hết thì N là snt.

    Bước 2 phải kiểm tra N-2 phép chia, để kiểm tra tính chia hết, khi N tăng, số lần thử cũng tăng tuyến tính theo N.
    Để giảm số lần thử ở bước 2 này để ý tính chất
    Nếu N không phải là snt thì N sẽ là tích của hai số A và B thoả mãn 1<A<=B<N
    Khi Amax = B thì Amax * Amax = N
    nên suy ra A*A <= Amax * Amax <=N
    suy ra: A <= Amax <= SQRT(N)
    do đó chỉ cần thử các số nguyên từ 2 đến Amax, nếu không có số A nào trong khoảng này mà N chia hết, thì cũng ko có số B nào trong khoảng từ SQRT(N) đến N-1 mà N chia hết.

    khi đó ta sẽ có thuật toán như @dungtnut đã viết ở trên.
    Có thể viết lại đầy đủ trong C++ DEV với hàm kt_snt là hàm kiểm tra tính nguyên tố của số nguyên N như sau: upload_2017-1-25_16-39-10.png
     
  4. duycop

    duycop Thành viên chăm chỉ

    Tham gia ngày:
    20/1/17
    Bài viết:
    137
    Điểm thành tích:
    63
    Giới tính:
    Nam
    Trong sách giáo khoa Toán lớp 6 có nói về số nguyên tố, số hợp số
    và có đưa ra cách sàng các số nguyên tố mà nhà toán học cổ Hy Lạp là Eratosthenes đã "phát minh" ra.
    sách có viết :
    Đây là hình ảnh minh hoạ cách hoạt động của cái sàng với các số từ 2 đến 120:
    đầu tiên coi 2 là số nguyên tố, sau đó loại hết các bội của nó.
    tiếp đến số bé nhất chưa bị loại sẽ là số nguyên tố, sau đó loại các bội của số này.
    lặp lại đến khi nào ko loại được số nào nữa.
    còn lại các số nguyên tố, đây chính là cái sàng ^_^
    [​IMG]
     
  5. dungtnut

    dungtnut Administrator Thành viên BQT

    Tham gia ngày:
    26/12/16
    Bài viết:
    26
    Điểm thành tích:
    3
    Giới tính:
    Nam
    Phải hiểu rõ nó mới học tin học được. Vì sau này học lên mới thấy số nguyên tố là cốt lõi của bảo mật dữ liệu. Thầy @duycop đã giải thích rõ ràng cho các em học sinh rồi. Chúc các em học tốt
     
  6. On5Minh

    On5Minh Thành viên mới

    Tham gia ngày:
    29/1/17
    Bài viết:
    18
    Điểm thành tích:
    3
    Giới tính:
    Nam
    Hàm sqrt(n) tính căn bậc 2 của n theo công thức MacLaurin, vì thế thời gian tính là đáng kể. Do đó chỉ nên gọi hàm này 1 lần trước vòng lặp.
    Tốt hơn là không dùng hàm này, mà dùng một vòng lặp để tìm giá trị m nhỏ nhất sao cho m*m >= n:
    int m;
    for (m =2; m*m < n; m++);
    Giá trị m này sẽ thay cho hàm sqrt(n) trong vòng lặp, như thế sẽ cải thiện đáng kể thời gian tính toán.
    Lưu ý rằng, câu lệnh "ngắn" có khi lại tiêu tốn time hơn là câu lệnh "dài".
     
    Chỉnh sửa cuối: 29/1/17
  7. On5Minh

    On5Minh Thành viên mới

    Tham gia ngày:
    29/1/17
    Bài viết:
    18
    Điểm thành tích:
    3
    Giới tính:
    Nam
    Phát biểu này chưa chính xác: "Một số nguyên dương được gọi là số nguyên tố khi số đó chỉ chia hết cho 1 và chính nó".
    Thật vậy, 2 là số nguyên tố. Rõ ràng 2 chia hết cho 4 số là -2,-1, 1 và 2.
    Nên phát biểu như sau: "Một số tự nhiên được gọi là số nguyên tố nếu nó có đúng 2 ước số dương là 1 và chính nó". [A natural number (i.e. 1, 2, 3, 4, 5, 6, etc.) is called a prime number (or a prime) if it has exactly two positive divisors, 1 and the number itself]. Vì vậy, số 1 không phải là số nguyên tố một cách đương nhiên, chứ không phải do sự "thống nhất" của nhóm người nào.
     
    Chỉnh sửa cuối: 29/1/17
    duycop thích bài này.
  8. duycop

    duycop Thành viên chăm chỉ

    Tham gia ngày:
    20/1/17
    Bài viết:
    137
    Điểm thành tích:
    63
    Giới tính:
    Nam
    Trong định nghĩa có nói lớn hơn 1 chứ số 1 vẫn chia hết cho 1 và chính nó mà!
    An integer greater than one is called a prime number if its only positive divisors (factors) are one and itself.
    tham khảo theo: https://primes.utm.edu/notes/faq/one.html
     
  9. On5Minh

    On5Minh Thành viên mới

    Tham gia ngày:
    29/1/17
    Bài viết:
    18
    Điểm thành tích:
    3
    Giới tính:
    Nam
    Phải có "positive divisors" mới chính xác. Và "A integer greater than one" trong định nghĩa đã đương nhiên loại số 1 ra rồi, chứ không phải "Nhiều nhà toán học đã thống nhất không coi số 1 là số nguyên tố"
     
    trungcod3r and duycop like this.

Chia sẻ trang này