Даны два числа $%n$% и $%m$%. Подскажите, пожалуйста, с алгоритмом нахождения числа различных значений у выражения $%HOK(i, n)/i+HOK(j, m)/j$% для всех натуральных $%i, j$%.

задан 26 Дек '21 20:39

изменен 26 Дек '21 20:40

А что эксперимент говорит?

(26 Дек '21 21:33) mihailm
10|600 символов нужно символов осталось
0

Произведение НОД и НОК двух натуральных чисел равно произведению самих этих чисел. Поэтому первое слагаемое равно n/НОД(i,n). Это делители числа n, и любой такой делитель d|n получается при i=n/d. Второе слагаемое устроено аналогичным образом.

Таким образом, перед нами множество чисел, которые являются суммами некоторого делителя n и некоторого делителя m. Без разложения чисел m и n на простые множители, мы о таком множестве знаем недостаточно: только то, что там есть 1+1, n+1, m+1, m+n. Если m,n оба простые, то других значений нет, поэтому нужно как минимум уметь распознавать простоту чисел. Но этого мало, так как даже если мы знаем, что n=pq есть произведение двух простых, то их нужно уметь находить, что при нынешнем уровне знаний для очень больших n делать никто не умеет.

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

ссылка

отвечен 26 Дек '21 21:48

@falcao: спасибо!

(26 Дек '21 22:04) Вовачесс
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×102

задан
26 Дек '21 20:39

показан
187 раз

обновлен
26 Дек '21 22:04

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru