Разложение на простые множители (Citizen SRP-400G)

| рубрика «Программы» | автор site_editor
Метки: ,

Две простые программы поиска разложения целых чисел на простые множители. Диапазон 1 <= n <= 999999999. В первой в качестве пробных делителей проверяются числа 2 и все нечетные. Во второй - 2,3 и все числа вида 6*I+1, 6*I-1.

1 программа:

Input N;
If(N==1)Then{Goto 1};
For(P=2;NRmdr2==0;N=N/2){Print P};
If(N==1)Then{Goto 2};
For(P=3;P^2<=N;P=P+2)
{
    If(NRmdrP==0)Then
    {
       Print P;
       N=N/P;
       P=P-2;
    }
};
Label 1:;
Print N;
Label 2:;
End

2 программа:

Input N;
If(N==1)Then{Goto 1};
For(P=2;NRmdrP==0;N=N/P){Print P};
For(P=3;NRmdrP==0;N=N/P){Print P};
If(N==1)Then{Goto 2};
For(I=1;(6I-1)^2<=N;I++)
{
    For(P=6I-1;NRmdrP==0;N=N/P){Print P};
    For(P=6I+1;NRmdrP==0;N=N/P){Print P};
};
Label 1:;
Print N;
Label 2:;
End

После приглашения нужно вести факторизуемое число. Программы будут искать простые делители и по мере их нахождения печатать их на дисплее.

Например,

  • 1111111 = 239*4649 - 12 сек. (1 программа), 11 сек. (2 программа)
  • 11111111 = 11*73*101*137 - 8 сек. (1 программа), 5 сек. (2 программа)
  • 111111111 = 3*3*37*333667 - 31 сек. (1 программа), 25 сек. (2 программа)
  • 1111111111 = 11*41*271*9091 - 15 сек. (1 программа), 13 сек. (2 программа)
  • 1111111121 = простое - 29 мин. 20 сек. (1 программа), около (меньше) 24 мин. 7 сек. (2 программа)