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

Две простые программы поиска разложения целых чисел на простые множители. Диапазон 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 программа)

Undefined

Комментарии

Не быстрее ли заранее посчитать квадратный корень из N и в цикле сравнивать I с уже заранее вычисленной верхней границей?

Да, можно. Да, спасибо. Сейчас попробую.

По поводу медленного счета (обсуждали в "8 ферзей" вроде), глянув в инструкцию пришла идея попробовать переключить в графический режим в начале вычислений.

А как туда перейти? ClrGrph?

Точно не скажу. Вот тут инструкция на русском.

Я попробовал так:

Input N;
If(N==1)Then{Goto 1};
For(P=2;NRmdr2==0;N=N/2){Print P};
If(N==1)Then{Goto 2};
S=Int(Sqrt(N))
For(P=3;P<=S;P=P+2)
{
    If(NRmdrP==0)Then
    {
       Print P;
       N=N/P;
       P=P-2;
       S=Int(Sqrt(N))
    }
};
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};
S=Int((Sqrt(N)+1)/6))
For(I=1;I<=S;I++)
{
    For(P=6I-1;NRmdrP==0;S=Int((Sqrt(N)+1)/6))){Print P;N=N/P};
    For(P=6I+1;NRmdrP==0;S=Int((Sqrt(N)+1)/6))){Print P;N=N/P};
};
If(N==1)Then{Goto 2};
Label 1:;
Print N;
Label 2:;
End

Время работы на прежних тестовых примерах (кроме 1111111121) не изменилось (с точностью, которую дает мой измеритель времени). На первой программе 1111111121 новым вариантом обсчитывается 28 мин. 46 сек. против 29 мин. 20 сек. на старом варианте. На второй программе выигрыш во времени более заметен: 20 мин. 50 сек. против 24 мин. 7 сек.

Во второй программе цикл по P (с шагом 6) не даст ускорение? Теоретически, мы тогда вынесем из цикла два умножения на константу. Заодно и границу делить на 6 не придётся.

Цикл по P и не цикл совсем (в некотором роде). Например, если N - простое, то его тело ни разу не выполняется, а если оно раскладывается на K множителей, то тело цикла в сумме выполняется K раз.

Вроде понял, что вы имеете в виду. А компилятор не соптимизирует? ;)
Это должно немного ускорить программу. Как-нибудь попробую. А что говорят обладатели МК-152. Быстрее он по таким алгоритмам разложение найдет? Я ведь всю затею с SRP-400G начал, чтобы сравнить его с МК-152.

Вот результат:

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};
Int(Sqrt(N)+1)
For(K=6;K<=S;K=K+6)
{
    For(P=K-1;NRmdrP==0;S=Int(Sqrt(N)+1)){Print P;N=N/P};
    For(P=K+1;NRmdrP==0;S=Int(Sqrt(N)+1)){Print P;N=N/P};
};
If(N==1)Then{Goto 2};
Label 1:;
Print N;
Label 2:;
End

1111111=239*4649 10 сек.
11111111=11*73*101*137 5 сек.
111111111=3*3*37*333667 22 сек.
1111111111=11*41*271*9091 11 сек.
1111111121=простое 19 мин. 28 сек.

Спасибо за советы!

Не за что.

1111111121 проверяется (ISPRIME?) и факторизуется (FACTOR) встроенными функциями на HP 50g меньше, чем за пару секунд. Вот квадрат этого числа (обозначим его N) уже не факторизуется. Вычисление занимает пару минут и заканчивается ничем. Проверка N с помощью ISPRIME? занимает секунды три и даёт правильный результат.

Подробнее см. моё исследование факторизации на HP 50g.

Наверное, для проверки простоты в HP50g используется алгоритм Миллера-Рабина (вероятностный тест). Я его хотел на SRP400G реализовать (для чисел < 10^10), но бросил эту затею из-за багов в языке программирования. Вообще, в этом странном калькуляторе я полностью разочаровался.