Выразите любое число как сумму четырех простых чисел

Вы можете сократить диапазон поиска, заметив простой факт: когда вы суммируете два числа, последняя цифра суммы будет последней цифрой суммы последних цифр двух чисел. Например 2345 + 24323 = 26668 и 5 + 3 = 8; Если сумма последних цифр составляет 2-значное число, используйте его последнюю цифру, например. 2345 + 5436 = 7781 5 + 6 = 11, последняя цифра которых равна 1.

Итак, следуя алгоритму, предложенному ранее:

1. Вычислите все простые числа меньше N, используя Решето Эратосфена.
2. Составьте список сумм двух простых чисел.
3. сгруппируйте в 10 блоков std :: set на основе последней цифры
4. Посмотрите на последнюю цифру вашего числа, найдите комбинаций, которые могут его составить (включая перенос). Используйте их, чтобы ограничить диапазон поиска

Например,

1. Для такого числа, как 34565, последняя цифра - 5, компоненты берутся из (0,5), (1,4), (2,3 ), (3,2), (4,1), (5,0), (6,9), (7,8), (8,7), (9,6). Исключая дубликаты, мы остаемся с (0,5), (1,4), (2,3), (6,9), (7,8). (Предварительно вычислите их для всех последних цифр и жестко запрограммируйте в вашу программу).

2. Если N - исходное число, выберите каждое число M из поля «0», проверьте, входит ли (N-M) в поле «5» и т. Д., Для всех возможных комбинаций. Если да, то вы нашли свой ответ!

   • Sreenadh

Любое число также включает дробные числа, так что вы также не можете выразить их как простые числа. Есть другие числа, такие как 9, которые вы не можете использовать. Без 1 в качестве простого числа вы не сможете его точно контролировать.

Я полагаю, что у проблемы нет решения.

Вот реализация PHP , которая выполняется менее чем за 2 секунды для 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) . ')');
    }
}

Конечно, это не сработает с числами ниже 8, если вы (ошибочно) не считаете 1 простым числом.

Что касается сита, вот что я считаю неоптимизированной, «глупой» реализацией:

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;
}

У меня она работает (с n = 100000 ) за малую долю секунды.

Если не было ограничения на размер числа (100 000 или меньше), то решение вашей проблемы не гарантировано: см. слабая гипотеза Гольдбаха .

Однако, скорее всего, это правда, по крайней мере, для чисел из диапазона результатов вычислений ...вы уверены, что ваша проблема не в том, чтобы выразить какое-либо число, являющееся суммой самых четырех простых чисел?

Поскольку 2,3,5,7,11,13,17,19,23 предлагают множество Возможности, я бы вычислил числа, которые выражаются как сумма 3 из этих чисел. (например, 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.)

Затем возьмите произвольное число N, найдите ближайшее простое число ниже того, которое отличается от N одним из предварительно вычисленные суммы трех маленьких простых чисел. Если вы не нашли решения, попробуйте следующее простое число до N-59. Если это все еще не работает, начните добавлять другие маленькие простые числа.

Используйте знания о промежутках между простыми числами , чтобы ограничить ваше решение ... наибольший промежуток между простыми числами для простых чисел меньше 155921 (больше 100000) составляет 86.

п.с. ваше Сито Эратосфена не должно занимать 2 секунды для N = 100000. Вам нужно только проверить делители до квадратного корня из 100 000 = 316.

Вот рекомендация, данная вопросом, на который ссылается в моих комментариях:

• Вычислить все простые числа меньше N, используя Сито Эратосфена.
• Табличная таблица список сумм двух простых чисел.
• Сортировать список.
• Проверьте, есть ли два номера в списке, который суммируется до N.
• Если да, распечатайте соответствующие четыре простые числа.

Если у вас есть список простых чисел и конкретное число, разве это не задача о рюкзаке ?

N - ваша вместимость а простые числа - это ваши предметы. У вас есть ограничение на количество предметов - 4. Я бы решил решить эту проблему с помощью динамического программирования, которое должно быть довольно быстрым.

Есть какая-то серьезная проблема с вашей реализацией сита. Я только что реализовал его в Delphi, и на моем процессоре Intel Core i7 с тактовой частотой 2,93 ГГц требуемое время составило менее одной миллисекунды (0,37 мс)!

Я использовал следующий код:

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.