LINUX.ORG.RU

Наличие общего делителя целых чисел

 


0

1

Какой есть несложный и быстрый способ проверки двух чисел на наличие общего делителя (не обязательно НОД)?

Что-то поискал в интернете, сходу не нашёл. Простой перебор по делителям от 2 до min(a,b) && (a != b) слишком медленный.

★★★★★

ростой перебор по делителям от 2 до min(a,b) && (a != b) слишком медленный.

зачем перебор когда есть нод(gcd)?

используй функцию gcd, быстрее будет чем твой перебор…

fsb4000 ★★★★★
()
Ответ на: комментарий от beastie

Совсем забыл про этот алгоритм. Спасибо.

pacify ★★★★★
() автор топика
Ответ на: комментарий от Crocodoom

Я заметил, что в квадрате [1...N] x [1...N] процент взаимнопростых пар стремится примерно к 60.83 %. Это какая-то константа?

pacify ★★★★★
() автор топика
Последнее исправление: pacify (всего исправлений: 1)
Ответ на: комментарий от quickquest

:)

Работал как-то в 6 лет (детсадовский возраст) на стройке, надо было 1 кубометр песка закидать. Рабочие решили посмеяться - выдали нам 2 лопаты на троих и 2 рубля за выполненную работу.

pacify ★★★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.