Hãy biểu thị bất kỳ số nào làm tổng của bốn số nguyên tố

Question

Tôi đã đưa ra một vấn đề để biểu thị bất kỳ số nào dưới dạng tổng của bốn số nguyên tố.

• Không được phép sử dụng bất kỳ loại cơ sở dữ liệu:

  điều kiện.

• thời gian thực hiện tối đa: 3 giây
• số chỉ đến 100.000
• Nếu tách là không thể, sau đó trở về -1

Những gì tôi đã làm:

1. sử dụng rây của Eratosthenes, tôi tính tất cả các số nguyên tố cho đến số được chỉ định.

2. tra cứu khái niệm gọi là giả thuyết Goldbach, biểu thị số ngay cả số dưới dạng tổng kết của hai số nguyên tố.

Tuy nhiên, tôi bị mắc kẹt ngoài điều đó. Có ai có thể giúp tôi về vấn đề này như cách tiếp cận bạn có thể thực hiện không?

Rây của Eratosthenes mất hai giây để đếm số nguyên tố lên tới 100.000.

Answer 1

Bạn vẫn có thể ổn với thời gian. Do giả thuyết Goldbach, Mỗi số thậm chí lớn hơn hoặc bằng 8 có thể được biểu thị bằng tổng của 2,2 và hai số nguyên tố nữa. Mọi số lẻ lớn hơn hoặc bằng 9 có thể được biểu diễn bằng tổng của 2,3 và hai số nguyên tố nữa. Không nên mất quá nhiều thời gian để tìm ra số nguyên tố.

Chỉnh sửa: Trên thực tế, bạn có thể tăng tốc độ này một cách đáng kể: Đối với bất kỳ số N nào, hãy tìm số nguyên tố lớn nhất bằng N-7 và chọn số nguyên tố đó và 3, sau đó tìm thêm hai số nguyên tố cho phù hợp với tổng của bạn . Đối với bất kỳ số lẻ N nào, tìm số nguyên tố lớn nhất hoặc bằng N-6 và chọn nó và hai, sau đó lại chọn hai số nguyên tố.

Answer 2

Bất kỳ số nào cũng bao gồm các phân số, vì vậy bạn không thể thể hiện chúng dưới dạng số nguyên tố. Có những con số khác như 9 mà bạn không thể làm. Nếu không có 1 như một nguyên tố, bạn không thể kiểm soát nó một cách tinh vi.

Tôi hy vọng rằng sự cố không có giải pháp.

Answer 3

Nếu không có giới hạn về kích thước số (100.000 hoặc ít hơn) thì sự cố của bạn không được đảm bảo để có giải pháp: xem weak Goldbach conjecture.

Tuy nhiên rất có thể đó là sự thật, ít nhất là đối với các số trong phạm vi kết quả tính toán ... bạn có chắc là vấn đề của bạn không thể hiện bất kỳ số nào tại số nhất bốn số nguyên tố?

Vì 2,3,5,7,11,13,17,19,23 cung cấp nhiều khả năng, tôi sẽ tính các con số được biểu thị bằng tổng của 3 số đó. (ví dụ: 2 + 3 + 5 = 10, 2 + 3 + 7 = 2 + 5 + 7 = 12, 3 + 5 + 7 = 15, 2 + 3 + 11 = 16, 2 + 5 + 11 = 18, 3+ 5 + 11 = 19, 2 + 7 + 11 = 20, ... 17 + 19 + 23 = 59.)

Sau đó lấy số tùy ý của bạn N, tìm số nguyên tố gần nhất bên dưới số khác với N theo một trong số tiền được tính trước của 3 số nguyên tố nhỏ.Nếu bạn không tìm thấy giải pháp, hãy thử nguyên tố gần nhất tiếp theo lên tới N-59. Nếu vẫn không hiệu quả, hãy bắt đầu thêm vào các số nguyên tố nhỏ khác.

Sử dụng kiến ​​thức về prime gaps để ràng buộc giải pháp của bạn ... khoảng cách nguyên tố lớn nhất cho số nguyên tố dưới 155.921 (lớn hơn 100.000) là 86.

---

tái bút: Sàng Eratosthenes của bạn không nên dùng 2 giây cho N = 100.000. Bạn chỉ cần phải kiểm tra ước lên đến căn bậc hai của 100.000 = 316.

Answer 4

Đây là recomendation được đưa ra bởi question referenced trong ý kiến ​​của tôi:

• Tính tất cả các số nguyên tố nhỏ hơn N sử dụng Sieve của Eratosthenes.
• Tab danh sách tổng của hai số nguyên tố.
• Sắp xếp danh sách .
• Kiểm tra xem có hai số trong danh sách tổng hợp là N.
• Nếu có, hãy in bốn số nguyên tương ứng .

Answer 5

Khi bạn có danh sách số nguyên tố có số bê tông không phải là số knapsack problem?

N là khả năng và số nguyên tố của bạn là các mặt hàng của bạn. Bạn có một giới hạn là 4 trên số mục. Tôi sẽ đi về giải quyết điều này với chương trình năng động, mà nên được khá nhanh.

Answer 6

Đây là một PHP thi chạy trong dưới 2 giây cho n = 99999:

function Eratosthenes($number) 
{ 
    static $primes = array(); 

    if (empty($primes[$number]) === true) 
    { 
     $sqrt = sqrt($number); 
     $primes[$number] = array_merge(array(2), range(3, $number, 2)); 

     for ($i = 2; $i <= $sqrt; ++$i) 
     { 
      foreach ($primes[$number] as $key => $value) 
      { 
       if (($value != $i) && ($value % $i == 0)) 
       { 
        unset($primes[$number][$key]); 
       } 
      } 
     } 
    } 

    return $primes[$number]; 
} 

$time = microtime(true); 
$number = 99995; 
$primes = array(); 

if ($number % 2 == 0) 
{ 
    $primes = array(2, 2); 
} 

else 
{ 
    $primes = array(2, 3); 
} 

$number -= array_sum($primes); 

foreach (Eratosthenes($number) as $prime) 
{ 
    if (in_array($number - $prime, Eratosthenes($number))) 
    { 
     $primes[] = $prime; 
     $primes[] = $number - $prime; 

     die(implode(' + ', $primes) . ' (' . (microtime(true) - $time) . ')'); 
    } 
} 

Tất nhiên nó sẽ không làm việc với những con số rống lên 8 trừ khi bạn (sai) xem xét 1 như là một số nguyên tố.

Answer 7

Bạn có thể giảm phạm vi tìm kiếm cần thiết bằng cách lưu ý một số thực tế: khi bạn tổng hợp hai số, chữ số cuối cùng của tổng sẽ là chữ số cuối cùng của tổng các chữ số cuối của hai số. Ví dụ: 2345 + 24323 = 26668 và 5 + 3 = 8; Nếu các chữ số cuối cùng cộng lại thành một số có 2 chữ số, hãy sử dụng số cuối cùng của nó, ví dụ: 2345 + 5436 = 7781 5 + 6 = 11 có chữ số cuối cùng là 1.

Vì vậy, sau khi thuật toán đề xuất trước đó:

1. Tính tất cả các số nguyên tố nhỏ hơn N sử dụng Sieve of Eratosthenes.
2. Lập bảng liệt kê các khoản tiền của hai số nguyên tố.
3. nhóm thành 10 std :: hộp đặt dựa trên chữ số cuối
4. Nhìn vào chữ số cuối cùng của số của bạn, tìm các kết hợp có thể làm cho điều này (bao gồm cả mang).Sử dụng những hạn chế phạm vi của việc tìm kiếm

Ví dụ,

1. Đối với một số mặt hàng như 34.565, chữ số cuối cùng là 5, các thành phần đến từ (0,5), (1, 4), (2,3), (3,2), (4,1), (5,0), (6,9), (7,8), (8,7), (9,6) . Loại trừ các bản sao, chúng tôi được để lại với (0,5), (1,4), (2,3), (6,9), (7,8). (Tính toán trước cho tất cả các chữ số cuối cùng và mã hóa vào chương trình của bạn).

2. Nếu N là số gốc, hãy chọn từng số M từ hộp "0", kiểm tra xem (N-M) có phải là thành viên của hộp "5", v.v. Nếu vậy, bạn đã tìm thấy câu trả lời của mình!

   • Sreenadh

Answer 8

Chỉ cần về chủ đề của Sieve, đây là những gì tôi xem xét một unoptimised, "câm" thực hiện:

std::vector<int> primes(int n) { 
    std::vector<int> s(n+1); 
    for (int i = 2; i * i <= n; ++i) { 
     if (s[i] == 0) { 
      for (int j = 2*i; j <= n; j += i) { 
       s[j] = 1; 
      } 
     } 
    } 

    std::vector<int> p; 
    for (int i = 2; i <= n; ++i) { 
     if (s[i] == 0) { 
      p.push_back(i); 
     } 
    } 
    // std::copy(p.begin(), p.end(), std::ostream_iterator<int>(std::cout, ", ")); 
    return p; 
} 

Đối với tôi nó chạy (với n = 100000) trong một phần nhỏ của một giây.

Answer 9

Có một số vấn đề nghiêm trọng với việc bạn thực hiện sàng. Tôi chỉ thực hiện nó trong Delphi, và trên CPU Intel Core i7 của tôi tốc độ 2,93 GHz, thời gian cần thiết là ít hơn một phần nghìn giây (0,37 ms)!

tôi đã sử dụng đoạn mã sau:

program Sieve; 

{$APPTYPE CONSOLE} 

uses 
    SysUtils, Windows; 

const 
    N = 100000; 

var 
    i, j: integer; 
    tc1, tc2, freq: Int64; 
    Arr: packed array[2..N] of boolean; 

begin 

    FillChar(Arr, length(Arr) * sizeof(boolean), 1); 

    QueryPerformanceFrequency(freq); 

    QueryPerformanceCounter(tc1); 
    for i := 2 to N div 2 do 
    if Arr[i] then 
    begin 
     j := 2*i; 
     while j <= N do 
     begin 
     Arr[j] := false; 
     inc(j, i); 
     end; 
    end; 

    QueryPerformanceCounter(tc2); 
    Writeln(FloatToStr((tc2 - tc1)/freq)); 

    Writeln; 

    for i := 2 to 100 do 
    Writeln(IntToStr(i) + ': ' + BoolToStr(arr[i], true)); 

    Writeln('...'); 

    Readln; 

end.