Từ 1 tới 5 trên tổng số 5 kết quả

Đề tài: Số nguyên tố | Xét số nguyên tố vô cùng lớn

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

    Mặc định Số nguyên tố | Xét số nguyên tố vô cùng lớn

    Tháng 8-2002, 1 êkip 3 nhà nghiên cứu Ấn Độ ở Viện công nghệ Kanpur là nhà Tin học Maninda Agrawal và 2 SV Neeraj Kayal, Nitin Saxena, đã hoàn thiện 1 thuật toán, chỉ có 13 dòng, cho phép xác định chắc chắn tính nguyên tố của những số rất lớn có tới hàng trăm chữ số:
    Code:
    input: integer n > 1
    1. if (n is of the form a^b, b > 1) output COMPOSITE;
    2. r = 2;
    3. while (r < n) {
    4.     if (gcd(n, r) != 1) output COMPOSITE;
    5.     if (r is prime)
    6.         let q be the largest prime factor of r-1;
    7.         if (q >= 4 * sqrt(r) * log(n)) and ((n^((r-1)/q) - 1) % r != 0)
    8.             break;
    9.     r++;
    10. }
    11. for a=1 to 2 * sqrt(r) * log(n)
    12.     if (x - a)^n - x^n + a) % (x^r - 1) != 0 output COMPOSITE;
    13. output PRIME
    Đây là mã giả, ko phải code đâu nhé
    Giải thích:
    + form: dạng
    + composite: hợp số
    + gcd: UCLN
    + prime: nguyên tố
    + factor: ước số

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

    Cái này hồi học phổ thông mình có đọc được trên báo TH&TT thì phải :-??

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

    Mình cũng mới biết à, vô tình lụm được bí kíp nên share cho bà con đọc chơi ấy mà.

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

    Mặc định Liệu có đúng ko?

    Giải thuật này tuy rất ngắn gọn và được nhiều nhà khoa học trên thế giới quan tâm (cả toán và tin học ) nhưng vẫn chưa được chứng minh tính đúng đắn bằng toán học đâu. Hay bạn nào chứng minh đi vậy

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

    Để ý cái mod ở dòng 12 là mod đa thức nên cũng ko phải dễ ăn của quại.

    Thực ra thuật toán này hay ở chỗ với mọi số N thuật toán luôn đạt cỡ O(n^6) với n là số chữ số, chứ nó chay chậm rì giờ người ta dùng elliptic curve (ECPP) kỉ lục là 34093 chữ số.

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

  1. Tìm số bộ 4 số nguyên tố cùng nhau
    Gửi bởi stucremon trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 13
    Bài viết cuối: 20-03-2013, 12:46 AM
  2. Liệt kê các cặp số nguyên tố cùng nhau.
    Gửi bởi romwanbi trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 2
    Bài viết cuối: 23-11-2012, 10:25 PM
  3. Hàm trong C Bác nào giúp em bài tập về hai số nguyên tố cùng nhau với
    Gửi bởi hungmittq trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 12
    Bài viết cuối: 20-07-2012, 04:23 PM
  4. đảo trật tự 4 số thu đc số nguyên tố cùng nhau số đã cho
    Gửi bởi thanhdieu trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 0
    Bài viết cuối: 13-12-2010, 08:42 PM
  5. Vẽ hình trái tim bằng ký tự '*', đề tài anh em cùng nguyên cứu
    Gửi bởi sieutanbinh1711 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 23
    Bài viết cuối: 30-03-2009, 08:02 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