Студент Университета Юга, что в Аргентине, просил меня помочь составить программу на Бейсике для решения задачи, которая в переводе на русский язык звучит так: Известно, что число 3141593 разлагается на пять простых множителей: x,y,z,k,t. Как их выявить? Ясно, что заданное число столь огромно, что пять вложенных циклов должны крутиться немало времени. И действительно, желанный результат появился лишь после двенадцати часов счета.
Буквально вчера я вернулся снова к данной задаче и нашел очень удачный способ ее решения. Он базируется на таблице простых чисел. Это последовательность A000040- OEIS. Ссылка:
https://oeis.org/A000040
Составляется текстовой файл "p.txt" с числами, что в иллюстрации. Далее ведется расчет по проге, которую составил буквально за полторы минуты:
dim p(58),pp(10)
open #1,"p.txt","r"
for i=1 to 25
input #1 p(i)
next i
print
n=3141593
for i=1 to 25
if n/p(i)=int(n/p(i)) then
v=v+1: pp(v)=p(i)
print p(i);
fi
next i
print
print "x*y*z*k*t = ";
print pp(1)*pp(2)*pp(3)*pp(4)*pp(5)
В результате секундного счета находим результат:
7 13 19 23 79
x*y*z*k*t = 3141593
Вторая строка - это проверка правильности результатов.
Данный подход можно эффективно применять при нахождении простых делителей произвольного целого числа. В приведенном примере студента я задал двадцать пять первых простых чисел. Если же проверка не дает задаваемого составного числа, то следует увеличить это количество (максимум до 58). Если и это не поможет, то в текстовом файле следует добавить члены последовательности A000040. В инете такая информация легко находится. Тут, правда, нужно заметить, что предложенный мной метод годится в том случае, если известно количество делителей и каждый - только в первой степени. Иначе необходимо программу немного изменить, что сделать не так уж и сложно. Над таким обобщением намереваюсь в дальнейшем поработать и написать продолжение.
12 октября 2023 г.