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

Question

У меня была проблема выразить любое число как сумму четырех простых чисел.

Условия:

• Не разрешается использовать любую базу данных.
• Максимальное время выполнения: 3 секунды
• Номера только до 100 000
• Если разделение НЕ возможно, вернуть -1

Что я сделал:

1. Используя сито Эратосфена, я вычислил все простые числа до указанного числа.

2. нашел концепцию под названием гипотеза Гольдбаха, которая выражает четное число как сумму двух простых чисел.

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

Сите Эратосфена требуется две секунды для подсчета простых чисел до 100 000.

Answer 1

Со временем все еще может быть хорошо. Из-за гипотезы Гольдбаха каждое четное число, большее или равное 8, может быть выражено как сумма 2,2 и двух других простых чисел. Каждое нечетное число, большее или равное 9, может быть выражено как сумма 2,3 и двух других простых чисел. Это не должно занять слишком много времени, чтобы выяснить простые числа.

Редактировать: На самом деле, вы могли бы значительно ускорить это: для любого четного числа N найдите наибольшее простое число, которое меньше или равно N-7, и выберите это простое число и 3, а затем найдите еще два простых числа, соответствующих вашей сумме. Для любого нечетного числа N найдите наибольшее простое число, большее или равное N-6, выберите его и два, затем снова выберите два простых числа.

Answer 2

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

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

1. Вычислите все простые числа меньше N, используя сито Эратосфена.
2. Сводный список сумм двух простых чисел.
3. сгруппировать в 10 стандартных полей: установить на основе последней цифры
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

Answer 3

Если не было ограничения на размер номера (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 одной из предварительно вычисленных сумм из 3 небольших простых чисел. Если вы не нашли решения, попробуйте следующий ближайший штрих до N-59. Если это все еще не работает, начните добавлять другие маленькие простые числа.

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

---

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

Answer 4

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

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

Answer 5

Существует серьезная проблема с вашей реализацией сита. Я только что реализовал это в 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.

Answer 6

Только что касается Сита, вот что я считаю неоптимизированной, "тупой" реализацией:

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) за небольшую долю секунды.

Answer 7

Вот реализация 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 простым числом.

Answer 8

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

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

Answer 9

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

Я ожидаю, что проблема не имеет решения.