задача с простыми числами

[Depolo]

Вводится положительное число N.Вывести различные простые числа сумма которых делится на N.числа не больше 10в 9 степени
Не могу понять как высчитать,по какому принципу должны складываться числа.

[Serge_Bliznykov]

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

p.s. решение методом перебора, боюсь, займёт непростительно большое вычислительное время для "плохих" больших N...

[Depolo]

да про перебор я тоже думал,но дело слишком долгое,можно попробовать закинуть все простые числа в массив, и оттуда плясать,но опять же,принцип по которому они должны складываться мне не понятен,может есть другой путь решения?

[Poma][a]

Забежал я на 5 минут, прочитал, задумался, перечитал, и опа, пост Сержа показался знакомым (где-то слышал про теорему).
Вспомнил что любое число может быть представлено в виде суммы простых чисел.(Это я где-то читал, слышал...)

Нагуглил только это : Вики


UPD1 Ладно, я что-то накропал...
Изначальный код взял из темы : тыц.
Потом чуть изменил и получилось :

var
    p : array [1..1000000] of LongInt;
    n, m, count : Int64;
    i, j : LongInt;
    flag : Boolean;

begin
    //reset (input, 'input.txt');
    //rewrite (output, 'output.txt');
    Read (m);

    // создаем массив простых числе от 2 до m
    p[1] := 2; // 1 простое число
    count := 2; // индекс 2 прост числ

    for i := 3 to m do begin
        j := 1;
        flag := TRUE;

        while p[j]*p[j] <= i do begin
            if i mod p[j] = 0 then begin
                flag := FALSE;
                break
            end;
            Inc (j)
        end;

        if flag then begin
            p[count] := i;
            Inc (count)
        end
   end;

   for i := count-2 downto 1 do
       if m >= p[i] then begin
           Write (p[i], ' + ');
           m := m - p[i]
       end
end.

Уж сорри, за вывод в таком виде, но у меня олимпиада идет, времени нет, а Вы такие интересные задачи выкладываете..

UPD2 Черт, у меня не сумма чисел делится на N, а ровна N. Господи, ну почему я не умею читать...

UPD3Так-с, давайте объявим наш массив простых чисел как глобальную переменную.
Дальше возьмем эффективный алгоритм нахождения делителей числа n. (на форуме точно есть хотя бы один пример (у нас там с TinMan'ом интересные дебаты получались))
Числа-делители N загоним в массив. И дальше переделаем часть моего кода в процедурку, которая будет работать для делителей числа N

[Poma][a]

const
    SIZE = 1000;

type
    TArr = array [1..10000] of Integer;
var
    p : array [1..SIZE] of Integer; // массив простых чисел

// инициализация массива простыми числами
procedure InitArrOfPrime (const m : Integer; var count : Integer);
var
    i, j : Integer;
    flag : Boolean;

begin
    p[1] := 2;
    count := 2;

    for i := 3 to m do begin
        j := 1;
        flag := TRUE;

        while p[j]*p[j] <= i do begin
            if i mod p[j] = 0 then begin
                flag := FALSE;
                break
            end;
            Inc (j)
        end;

        if flag then begin
            p[count] := i;
            Inc (count)
        end
   end

end;

procedure InitArrOfDiv (var a : TArr; const n : Integer; var count : Integer);
var
    sq, i : Integer;

begin
    sq := Round (Sqrt (n));
    a[1] := n;
    count := 2;

    for i := 2 to sq-1 do
           if n mod i = 0 then begin
                a[count] := i;
                a[count+1] := n div i;
                Inc (count, 2)
           end;
end;

procedure WriteResult (var n, m : Integer);
var
    i : Integer;

begin
    for i := n downto 1 do
        if m >= p[i] then begin
            Write (p[i], ' + ');
            m := m - p[i]
        end;
    WriteLn
end;
var
    a : TArr;
    n, i, j, count, cntpr : Integer;

begin
    ReadLn (n);
    InitArrOfPrime(n, cntpr);
    InitArrOfDiv (a, n, count);
    j := 1;

    for i := 1 to count do begin
        j := 1;
        while (p[j] < a[i]) and (j < cntpr) do
            Inc (j);
        WriteResult (j, a[i])
    end;
end.