Khả thi thực hiện chức năng đếm thủ công

Question

Có ai có thể cung cấp mã giả khả thi về mặt tính toán của việc thực hiện prime-counting function không? Ban đầu tôi đã cố gắng mã hóa Hardy-Wright algorithm, nhưng giai thừa của nó đã bắt đầu tạo ra tràn tràn khốn khổ và nhiều người khác dường như bị ràng buộc để mang lại các vấn đề tương tự. Tôi đã lùng sục Google cho các giải pháp thực tế, nhưng, tốt nhất, đã tìm thấy toán học rất bí truyền mà tôi chưa từng thấy trong các chương trình thông thường.

Answer 1

Hàm đếm nguyên tố pi (x) tính số lượng số nguyên tố không vượt quá x, và đã thu hút các nhà toán học trong nhiều thế kỷ. Vào đầu thế kỷ thứ mười tám, Adrien-Marie Legendre đã đưa ra một công thức bằng cách sử dụng một hàm phụ phi (x, a) đếm số không lớn hơn x mà không bị ảnh hưởng bởi việc sàng lọc với số nguyên tố đầu tiên; ví dụ, phi (50,3) = 14 cho các số 1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 và 49. Hàm phi có thể được tính là phi (x, a) = phi (x, a-1) - phi (x/P (a), a-1), trong đó phi (x, 1) là số nguyên lẻ không vượt quá x và P (a) là số nguyên tố thứ 1 (tính từ P (1) = 2).

function phi(x, a) 
    if (phi(x, a) is in cache) 
    return phi(x, a) from cache 
    if (a == 1) 
    return (x + 1) // 2 
    t := phi(x, a-1) - phi(x // p[a], a-1) 
    insert phi(x, a) = t in cache 
    return t 

Một mảng lưu trữ số nguyên tố thứ a cho số nhỏ, tính bằng sàng. Bộ đệm là quan trọng; không có nó, thời gian chạy sẽ là theo cấp số mũ. Với phi, công thức tính toán của Legendre là pi (x) = phi (x, a) + a - 1, trong đó a = pi (tầng (sqrt (x))). Legendre đã sử dụng công thức của mình để tính toán pi (10^6), nhưng ông báo cáo 78526 thay vì câu trả lời đúng của 78498, mặc dù sai, gần như đáng kinh ngạc cho một tính toán thủ công phức tạp.

Trong những năm 1950, Derrick H. Lehmer đưa ra một thuật toán cải tiến cho số nguyên tố đếm:

function pi(x) 
    if (x < limit) return count(primes(x)) 
    a := pi(root(x, 4)) # fourth root of x 
    b := pi(root(x, 2)) # square root of x 
    c := pi(root(x, 3)) # cube root of x 
    sum := phi(x,a) + (b+a-2) * (b-a+1)/2 
    for i from a+1 to b 
    w := n/p[i] 
    lim := pi(sqrt(w)) 
    sum := sum - pi(w) 
    if (i <= c) 
     for j from i to lim 
     sum := sum - pi(w/p[j]) + j - 1 
    return sum 

Ví dụ, pi (10^12) = 37607912018. Ngay cả với các thuật toán, và các biến thể hiện đại của họ, và máy tính rất nhanh, nó vẫn còn tẻ nhạt tẻ nhạt để tính toán các giá trị lớn của pi; tại văn bản này, giá trị được biết lớn nhất là pi (10^24) = 18435599767349200867866.

Để sử dụng thuật toán này để tính toán nguyên tố thứ n, một hệ luỵ đối với Định lý số nguyên ràng buộc n-th nguyên tố P (n) giữa n log n và n (log n + log log n) cho n> 5, do đó tính toán pi tại các giới hạn và sử dụng bisection để xác định nguyên tố thứ n, chuyển sang sàng khi các giới hạn đóng.

Tôi thảo luận các số nguyên tố trong một số mục nhập tại my blog.

Answer 2

Wikipedia cũng có thể hữu ích. Bài viết trên prime counting chứa một vài gợi ý. Đối với người mới bắt đầu, tôi muốn giới thiệu thuật toán của Meissel trong phần "Thuật toán để đánh giá π (x)", là một trong những thuật toán đơn giản nhất mà không tạo ra tất cả các số nguyên tố.

Tôi cũng tìm thấy sách của Pomerance và Crandall "Prime numbers a computational perspective" hữu ích. Cuốn sách này có mô tả chi tiết và dễ tiếp cận về các phương pháp đếm chính. Nhưng hãy nhớ rằng chủ đề bởi bản chất của nó hơi quá cao đối với hầu hết người đọc ở đây.