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

0

1

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

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

Ссылка

←	объёмный график на питоне

Посоветуйте пакет символьной алгебры под linux

→

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

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

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

fsb4000 ★★★★★
(24.10.21 09:48:24 MSK)

Ссылка

package gcd

func GCD(a, b int) int {
	for a != b {
		if b > a {
			a, b = b, a
		}
		a -= b
	}
	return a
}

beastie ★★★★★
(24.10.21 09:53:39 MSK)

Ответ на: комментарий от beastie 24.10.21 09:53:39 MSK

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

pacify ★★★★★
(24.10.21 10:01:06 MSK) автор топика

Ссылка

Ответ на: комментарий от beastie 24.10.21 09:53:39 MSK

Бинарный же быстрее.

~~fernandos~~ ★★★
(24.10.21 10:05:35 MSK)

Ссылка

Алгоритм Евклида же

~~Crocodoom~~ ★★★★★
(24.10.21 10:06:24 MSK)

Ответ на: комментарий от Crocodoom 24.10.21 10:06:24 MSK

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

pacify ★★★★★
(24.10.21 10:12:15 MSK) автор топика
Последнее исправление: pacify 24.10.21 10:16:41 MSK (всего исправлений: 1)

Ответ на: комментарий от pacify 24.10.21 10:12:15 MSK

Да, это 6/pi^2

См. https://en.wikipedia.org/wiki/Coprime_integers

~~Crocodoom~~ ★★★★★
(24.10.21 10:28:04 MSK)

Ссылка

наличие общего делителя

quickquest ★★★★★
(24.10.21 12:11:53 MSK)

Ответ на: комментарий от quickquest 24.10.21 12:11:53 MSK

:)

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

pacify ★★★★★
(24.10.21 12:36:17 MSK) автор топика

Ссылка

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

←	объёмный график на питоне

Science & Engineering

Посоветуйте пакет символьной алгебры под linux

→

Похожие темы