Поиск 2х взаимнопростых чисел из решета Эратосфена

@влад0 · Регистрация: 22.05.2012

Author24 — интернет-сервис помощи студентам

В общем столкнулся с задачкой. У меня есть Список простых числе от 1 до N представленных списком. Нужно выбрать 2 случайных числа что бы они являлись взаимнопростыми.
Все что я придумал по этому поводу, это случайно выбирать числа из списка и проверять их алгоритмом Евклида, но время затраченное на такой подбор может оказаться невероятно велико.

Хотелось бы послушать советы, может быть есть какие то более действенные и мение ресурсоемкие способы и алгоритмы решения данной задачи...
Вот пока мои наработки

C#

        public static void RelativelySimple(out SimpleNumber First, out SimpleNumber Second)
        {
            while (true)
            {
                if (GCD((First = Random()), (Second = Random())) == 1)
                    break;
            }
        }

GCD - НОД, возвращает Int32

Random() возвращает случайное простое число до 10000 из таблицы Эратосфена

Psilon · 15.11.2015, 13:30

влад0, википедия

Любые два (различных) простых числа взаимно просты.

так что если список изначально состоит из простых чисел, выбираем 2 любых. Конец.

@влад0 · 15.11.2015, 13:35 **[ТС]**

А ведь и вправду

Что-то у меня с математикой не очень

Psilon Master of Orion 6098 / 4954 / 905 Регистрация: 10.07.2011 Сообщений: 14,522 Записей в блоге: 5
	15.11.2015, 13:30	2
	влад0, википедия Любые два (различных) простых числа взаимно просты. так что если список изначально состоит из простых чисел, выбираем 2 любых. Конец. 1

@влад0 5 / 5 / 0 Регистрация: 22.05.2012 Сообщений: 122
	15.11.2015, 13:35 [ТС]	3
	А ведь и вправду Что-то у меня с математикой не очень 0