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 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ố
    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ý.

  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,479

    Để ý 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ô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á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