Как найти наибольший делитель числа не равный самому числу
Перейти к содержимому

Как найти наибольший делитель числа не равный самому числу

  • автор:

Как найти наибольший делитель числа, не равный самому числу?

для простых чисел-это само число потому что просто число делится на себя и 1.Для других чисел находите делитли начиная с минимальных-2.3.5. и найдете максимальное. ПРИМЕР: 144\2=72\2=36\2=18\2=9\3. 72 =Наибольший делитель1)21-72)39-13..3)108- 54..85-17.

Остальные ответы

найди наименьшее число, большее 1, на которое делится исходное и подели. вот и ответ.
________________________________________

достаточно перебирать простые числа, не превосходящие квадратного корня из исходного числа. если среди них нет делителя исходного числа, ответ 1

найди наименьшее число, большее 1, на которое делится исходное и подели. вот и ответ.
________________________________________

достаточно перебирать простые числа, не превосходящие квадратного корня из исходного числа. если среди них нет делителя исходного числа, ответ 1

Наибольший делитель, не равный самому числу

Как найти наибольший делитель, не равный самому числу?
Способ «разложить на множители и выбрать наибольший из них» не предлагать.

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

Это т. наз. задача «факторизации больших чисел». Для нее не существует известного способа быстрого решения.
И на этом (на невозможности быстрого решения) построены некоторые алгоритмы шифрования «с открытым ключом».

Кто-нибудь найдет способ — и секретность рухнет. )))))

Делим Число1 на Делитель=(Число1 минус один) . Если результат целый, то Делитель=(Число1 минус один) — наибольший делитель. Иначе уменьшаем Делитель на еще 1 и повторяем проверку (организуем цикл) .

Еще надо рассмотреть исключения- если Число1 задано как ноль, единица или отрицательное

Для большиих чисел: тогда подходи с другой стороны: дели на 2, проверяй результат на целое ли число, потом на 2+1 и т. д. «результат» — искомый макс. делитель.

Как в C++ найти наибольший делитель числа?

А я ведь не зря говорил о поиске наименьшего делителя. Гляньте, сколько работает ваш код для 2142972483, и сколько — мой. И еще — все же не стоит поощрять лень и решать такие задания за человека, которому важнее не знать, а сдать.

18 окт 2018 в 15:41
@Harry главное, что работает, это еще не та работа где нужна максимальная скорость
18 окт 2018 в 16:02

Да как сказать. Факторизация как раз задача из тех, которые могут ну очень долго выполняться. Это — никак не преждевременная оптимизация, это смена алгоритма. У вас в худшем варианте нужно перепробовать n/2-sqrt(n) вариантов, у меня — sqrt(n)/2 — можно пропускать четные. Итого разница в sqrt(n)-2 раза — даже для миллиона — в 1000 раз. Даже если вы тоже будете пропускать четные — в 500 раз. Согласитесь, разница в несколько порядков — это таки существенно 🙂

18 окт 2018 в 17:02

@Harry я понял что можно было сделать по другому, но все равно решение то рабочее(хоть можно было и лучше сделать), и почему бы галочку ему не поставить, я все таки старался

Как найти наибольший делитель числа не равный самому числу

Напишите программу, которая перебирает целые числа, большие \(650~000\), в порядке возрастания и ищет среди них такие, для которых наибольший натуральный делитель, не равный самому числу, не является простым числом. Программа должна найти и вывести первые \(6\) таких чисел и соответствующие им значения упомянутых делителей.
Формат вывода: для каждого из \(6\) таких натуральных чисел в отдельной строке сначала выводится само число, затем упомянутый делитель. Строки выводятся в порядке возрастания найденных чисел.
Например, для числа \(105\) наибольший натуральный делитель \(35\) не является простым, для числа \(15\) наибольший натуральный делитель \(5\) — простое число, а для числа \(13\) такого делителя не существует.

Решение:

Python

 def is_prime(n: int) -> bool: if n == 1: return False if n in (2, 3): return True for x in range(2, int(n**0.5)+1): if n % x == 0: return False return True def min_divisor(n: int) -> int: for x in range(2, int(n**0.5) + 1): if n % x == 0: return x return 1 def max_divisor(n: int) -> int: return n // min_divisor(n) n = 650001 k = 0 while k < 6: md = max_divisor(n) if md < n and not is_prime(md): print(n, md) k += 1 n += 1 

Ответ:
\(650001\) \(216667\)
\(650003\) \(28261\)
\(650004\) \(325002\)
\(650005\) \(130001\)
\(650006\) \(325003\)
\(650007\) \(216669\)

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *