Правила форума :: Скачать Pascal :: FAQ // Ада–2020 :: Скачать GNAT :: OEM–2015 :: Ada -> C/C++
  |
 Нахождение числа, взаимнопростого заданному |
| Unknown |
Сообщение
#1
|
 Пионер  Группа: Пользователи Сообщений: 104 Пол: Мужской Реальное имя: Евгений Репутация:  0   |
Как это сделать?
Перебирать все числа и проверять их с заданным числом НОД на равенство единице мне кажется долгим, наверное, есть варианты короче? Что-то типа перебирать простые числа и проверять заданное число на кратность найденному. Но тогда часть решений будет потеряна... -------------------- go ask Alice
|
   |
 
|
| Lapp |
Сообщение
#2
|
 Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Цитата(Unknown @ 23.07.2009 13:32)  Что-то типа перебирать простые числа и проверять заданное число на кратность найденному. Но тогда часть решений будет потеряна... Не понял - что будет потеряно?  Во-первых, условие ты поставил так, что одного числа будет достаточно (любого). Во-вторых, я не понимаю, что ты можешь потерять. Если нужны все - то добавь к простым еще и их всевозможные произведения. Проще тут не выйдет. Процесс разложения на множители по своей природе емкий. Не даром на нем основана криптография.. Найдешь простое решение - сможешь вскрывать все шифры, а заодно и Нобеля в карман положишь..)) -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
|
|
|
| Unknown |
Сообщение
#3
|
|
Пионер Группа: Пользователи Сообщений: 104 Пол: Мужской Реальное имя: Евгений Репутация: 0 |
Цитата(Lapp) Если нужны все - то добавь к простым еще и их всевозможные произведения. Да, это то, чего не хватало!  Цитата(Lapp) Процесс разложения на множители по своей природе емкий. Не даром на нем основана криптография.. Найдешь простое решение - сможешь вскрывать все шифры, а заодно и Нобеля в карман положишь..)) На нем основаны только асимметричные шифры, насколько я знаю. Наш ГОСТ не использует факторизацию... -------------------- go ask Alice
|
|
|
|
| Lapp |
Сообщение
#4
|
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Цитата(Unknown @ 24.07.2009 16:37) На нем основаны только асимметричные шифры, насколько я знаю. Наш ГОСТ не использует факторизацию... Ессно асимметричные. А ГОСТ еще существует? )))-------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
|
|
|
|
|
Текстовая версия | 22.12.2024 8:52 |
