Một cách để tìm số nguyên tố gần nhất với số nguyên dài chưa được ký (rộng 32 bit) trong C?

Question

Tôi đang tìm cách tìm số nguyên tố gần nhất. Lớn hơn hoặc ít hơn, nó không quan trọng, chỉ đơn giản là gần nhất (không tràn, tốt nhất.) Đối với tốc độ, nếu nó có thể tính toán nó trong khoảng 50 mili giây trên một máy 1GHz (trong phần mềm, chạy bên trong Linux), tôi muốn ngây ngất.

Answer 1

CẬP NHẬT 2: Cố định (theo cách nặng) một số lỗi gây ra các câu trả lời sai cho n nhỏ. Cảm ơn Brett Hale vì đã chú ý! Cũng đã thêm một số khẳng định để ghi lại một số giả định.

CẬP NHẬT: Tôi được mã hóa này lên và có vẻ như rất nhiều đủ nhanh cho các yêu cầu của bạn (giải quyết 1.000 trường hợp ngẫu nhiên từ [2^29, 2^32-1] trong < 100ms, trên một máy 2.2GHz - không một thử nghiệm nghiêm ngặt nhưng vẫn thuyết phục).

Nó được viết bằng C++ vì đó là mã của tôi (mà tôi đã thích nghi), nhưng việc chuyển đổi thành C phải đơn giản. Việc sử dụng bộ nhớ cũng là (tương đối) nhỏ mà bạn có thể nhìn thấy bằng cách kiểm tra.

Bạn có thể thấy rằng do cách hàm được gọi, số được trả về là số nguyên gần nhất phù hợp với 32 bit, nhưng thực tế điều này giống với số nguyên tố xung quanh 2^32 là 4294967291 và 4294967311.

Tôi đã cố gắng đảm bảo sẽ không có bất kỳ lỗi nào do tràn số nguyên (vì chúng tôi đang xử lý các con số phải lên tới UINT_MAX); hy vọng tôi đã không phạm sai lầm ở đó. Mã có thể được đơn giản hóa nếu bạn muốn sử dụng các loại 64-bit (hoặc bạn biết số của bạn sẽ nhỏ hơn 2^32-256) vì bạn sẽ không phải lo lắng về việc quấn xung quanh trong các điều kiện vòng lặp. Ngoài ra, ý tưởng này cũng quy mô cho các số lớn hơn miễn là bạn sẵn sàng tính toán/lưu trữ các số nguyên tố nhỏ đến giới hạn cần thiết.Tôi cũng cần chú ý rằng cái rây nhỏ chạy khá nhanh cho những con số này (4-5 ms từ một phép đo thô) vì vậy nếu bạn đặc biệt bị thiếu bộ nhớ, hãy chạy nó mỗi lần thay vì lưu trữ các số nguyên tố nhỏ là doable (bạn có thể muốn làm cho dấu [] mảng nhiều không gian hiệu quả trong trường hợp này)

#include <iostream> 
#include <cmath> 
#include <climits> 
#include <cassert> 

using namespace std; 

typedef unsigned int UI; 

const UI MAX_SM_PRIME = 1 << 16; 
const UI MAX_N_SM_PRIMES = 7000; 
const UI WINDOW = 256; 

void getSMPrimes(UI primes[]) { 
    UI pos = 0; 
    primes[pos++] = 2; 

    bool mark[MAX_SM_PRIME/2] = {false}; 
    UI V_SM_LIM = UI(sqrt(MAX_SM_PRIME/2)); 
    for (UI i = 0, p = 3; i < MAX_SM_PRIME/2; ++i, p += 2) 
    if (!mark[i]) { 
     primes[pos++] = p; 
     if (i < V_SM_LIM) 
     for (UI j = p*i + p + i; j < MAX_SM_PRIME/2; j += p) 
      mark[j] = true; 
     } 
    } 

UI primeNear(UI n, UI min, UI max, const UI primes[]) { 
    bool mark[2*WINDOW + 1] = {false}; 

    if (min == 0) mark[0] = true; 
    if (min <= 1) mark[1-min] = true; 

    assert(min <= n); 
    assert(n <= max); 
    assert(max-min <= 2*WINDOW); 

    UI maxP = UI(sqrt(max)); 
    for (int i = 0; primes[i] <= maxP; ++i) { 
    UI p = primes[i], k = min/p; 
    if (k < p) k = p; 
    UI mult = p*k; 
    if (min <= mult) 
     mark[mult-min] = true; 
    while (mult <= max-p) { 
     mult += p; 
     mark[mult-min] = true; 
     } 
    } 

    for (UI s = 0; (s <= n-min) || (s <= max-n); ++s) 
    if ((s <= n-min) && !mark[n-s-min]) 
     return n-s; 
    else if ((s <= max-n) && !mark[n+s-min]) 
     return n+s; 

    return 0; 
    } 

int main() { 
    UI primes[MAX_N_SM_PRIMES]; 
    getSMPrimes(primes); 

    UI n; 
    while (cin >> n) { 
    UI win_min = (n >= WINDOW) ? (n-WINDOW) : 0; 
    UI win_max = (n <= UINT_MAX-WINDOW) ? (n+WINDOW) : UINT_MAX; 

    if (!win_min) 
     win_max = 2*WINDOW; 
    else if (win_max == UINT_MAX) 
     win_min = win_max-2*WINDOW; 

    UI p = primeNear(n, win_min, win_max, primes); 
    cout << "found nearby prime " << p << " from window " << win_min << ' ' << win_max << '\n'; 
    } 
    } 

---

bạn có thể rây khoảng trong phạm vi đó nếu bạn biết số nguyên tố lên đến 2^16 (có chỉ 6542 < = 2^16; bạn nên cao hơn một chút nếu bản thân số nguyên tố có thể lớn hơn 2^32 - 1). Không nhất thiết phải là cách nhanh nhất nhưng rất đơn giản và các kỹ thuật thử nghiệm chính hiệu quả thực sự phù hợp với các phạm vi lớn hơn nhiều.

Về cơ bản, hãy thực hiện sàng lọc thông thường của Eratosthenes để nhận các số nguyên tố "nhỏ" (ví dụ 7000 đầu tiên). Rõ ràng bạn chỉ cần làm điều này một lần vào lúc bắt đầu của chương trình, nhưng nó sẽ rất nhanh.

Sau đó, giả sử số "mục tiêu" của bạn là 'a', hãy xem xét khoảng [a-n/2, a + n/2) đối với một số giá trị n. Có lẽ n = 128 là một nơi hợp lý để bắt đầu; bạn có thể cần phải thử các khoảng liền kề nếu các số trong số đầu tiên là tất cả các kết hợp.

Đối với mỗi "nhỏ" nguyên tố p, vượt qua bội số của nó trong phạm vi, sử dụng phân chia để tìm nơi bắt đầu. Một tối ưu hóa là bạn chỉ cần bắt đầu vượt qua bội số bắt đầu từ p * p (có nghĩa là bạn có thể ngừng xem xét số nguyên tố một lần p * p là trên khoảng thời gian).

Hầu hết số nguyên tố trừ số nguyên tố đầu tiên sẽ có một hoặc nhiều bội số bên trong khoảng thời gian; để tận dụng điều này, bạn có thể bỏ qua bội số của vài số nguyên tố đầu tiên. Điều đơn giản nhất là bỏ qua tất cả các số chẵn, nhưng không phải là hiếm khi bỏ qua bội số của 2, 3 và 5; điều này để lại các số nguyên tương đồng với 1, 7, 11, 13, 17, 19, 23 và 29 mod 30 (có tám, ánh xạ độc đáo với các bit của một byte khi sàng một phạm vi rộng).

... Sắp xếp tắt trên đường tiếp tuyến ở đó; anyway một khi bạn đã xử lý tất cả các số nguyên tố nhỏ (lên đến p * p> a + n/2) bạn chỉ cần nhìn vào khoảng thời gian cho số bạn đã không vượt qua; vì bạn muốn gần nhất để bắt đầu tìm kiếm ở đó và tìm kiếm bên ngoài theo cả hai hướng.

Answer 2

largest prime gap trong phạm vi tối đa (2^32 - 1) là (335). Có (6542) số nguyên tố nhỏ hơn (2^16) có thể được lập bảng và được sử dụng để sàng các giá trị lẻ liên tiếp sau khi thiết lập một lần. Rõ ràng, chỉ có số nguyên tố < = tầng (sqrt (ứng cử viên)) cần được kiểm tra cho một giá trị ứng cử viên cụ thể.

Cách khác:deterministic variant of the Miller-Rabin test, với cơ sở SPRP: {2, 7, 61} đủ để chứng minh nguyên thủy cho giá trị 32 bit. Do sự phức tạp của bài kiểm tra (yêu cầu số mũ, vv), tôi nghi ngờ nó sẽ nhanh như vậy đối với các ứng cử viên nhỏ như vậy.

Chỉnh sửa: Trên thực tế, nếu nhân/giảm có thể được giữ đến 32 bit trong lũy ​​thừa (có thể cần hỗ trợ 64 bit), kiểm tra M-R có thể tốt hơn. Khoảng cách chính sẽ thường nhỏ hơn nhiều, khiến cho chi phí thiết lập rây quá cao. Nếu không có bảng tra cứu lớn, v.v., bạn cũng có thể nhận được tăng từ vùng nhớ cache tốt hơn.

Hơn nữa: Sản phẩm của số nguyên tố {2, 3, 5, 7, 11, 13, 17, 19, 23} = (223092870). Kiểm tra rõ ràng bất kỳ ứng cử viên nào trong [2, 23]. Tính ước số chung lớn nhất: g = gcd(u, 223092870UL). Nếu (g != 1), ứng cử viên là tổng hợp. Nếu (g == 1 && u < (29 * 29)), ứng cử viên (u > 23) chắc chắn là nguyên tố. Nếu không, hãy chuyển sang các bài kiểm tra đắt tiền hơn. Một thử nghiệm gcd duy nhất sử dụng số học 32 bit là rất rẻ, và theo định lý Mertens '(?), Điều này sẽ phát hiện ~ 68.4% của tất cả số phức lẻ.