Простейший алгоритм разложения на множители

Algorithm for factoring integers, so simple, that it may be realized even on an abacus.

Алгоритм разложения целых чисел на множители, настолько простой, что его можно реализовать
даже на конторских счетах.

void start()
{ 
   int a=4252361;    //  integer to factorize
   int b=1,  c,  d=a-1;  

   while ((a > b) && (d != b))
  {
    if (d > b)
     {
       c=c+b;
       a=a-1;
       d=a-c-1;
     }
    if (d < b)
     {
       c=b-d;
       b=b+1;
       a=a-1;
       d=a-c-1;
     }         
  }
    if ((d == b)&&(a > b)) 
  Alert ("a = ",  a-1,  " * ", b+1); 

    if ((d < b)&&(a <= b)) 
  Alert ("a  is a prime");

  return;
}

The algorithm is composed by me, Miliaev Viktor Konstantinovich, born 26, July, 1950.
It is written in MQL4 15.12. 2017. E-mail: tenfacet27@gmail.com

Алгоритм сочинил я, Миляев Виктор Константинович, дата и место рождения: 26 июля 1950 года,
г. Борисоглебск Воронежской обл.
Он написан 15 декабря 2017 года на языке MQL4. E-mail: tenfacet27@gmail.com

Комментарии

— ВасВас (25/12/2017 15:52)
Интересно... Чем-то похож на мой годичной давности)))
В вашем алгоритме для факторизации числа 341 надо сделать 309 сравнений "d и b" а в моём всего 32 раза некоторго "х" с нулём))) И у меня всего 3 действия в каждом из условий)))
А вообще по факту алгоритмически быстрее тупо последовательно перебирать множители от 2 до N.
Добавте в ваш код функцию вывода c,a,d,b в каждое сравнение d и b после всех вычислений, и всё будет понятно.

— nonseriousman (27/12/2017 00:04)
Нельзя ли прислать ваш алгоритм?

— ВасВас (27/12/2017 12:22, исправлен 27/12/2017 12:28)

\код на Python 3:\
x=15 # факторизуемое число print("Начальные квадраты:") z=x/2 #здесь целочисленное деление факторизуемого числа на 2 z=int(z) #отбрасывает все цифры после запятой print(z+1) print(z) #z больше нигде не используется t=0 k=1 c=0 r=1 while x!=0: if x>0: x=x-k t=t+1 k=k+2 elif x<0: x=x+r c=c+1 r=r+2 print("Квадраты:") print(t) print(c) print("Множители:") print(t-c) print(t+c) input()

Интересно что чётность начальных квадратов совпадает с чётностью квадратов из ответа. Также совпадают остатки чётных квадратов при делении на 4.

— nonseriousman (28/12/2017 22:45)
Уважаемый ВасВас,

Нет смысла сравнивать время работы этих двух программ на нескольких конкретных числах. Ни вы, ни я не знаем, какова их асимптотическая сложность. Я просто еще этим не занимался. Но дело совсем не в этом, а в том, что ваша программа – реализация «метода Ферма», который известен уже триста лет
Мой же алгоритм основан на совершенно другой идее, которая, насколько я на настоящий момент в курсе, является новой, не появлявшейся еще в теме «факторизация». Мне кажется, что пока я не должен описывать эту идею, хотя, конечно, когда-нибудь я это сделаю. Однако, очень может быть, что кто-то, глядя на программу, и сам догадается, на какой идее она основана, и тогда для него сразу отпадет вопрос о корректности моего алгоритма.

— ВасВас (29/12/2017 12:07)
Вопрос стоит не о корректности а о целесообразности. не мой не ваш для факторизации использовать не целесообразно, но они хорошо подходят для понимания сути того что происходит с числами. А это понимание может хорошо помочь в поиске эффективного алгоритма.

— ВасВас (29/12/2017 13:13)
Сейчас я занимаюсь проверкой своих идей, надеюсь я их пройду за выходные, о результатах возможно напишу сюда.

openPGP в России

Простейший алгоритм разложения на множители