Задача: Суперпростые числа
Правила форума
Пожалуйста, ознакомьтесь с правилами данного форума
Пожалуйста, ознакомьтесь с правилами данного форума
- Циник
- Завсегдатай
- Сообщения: 442
- Зарегистрирован: 17 фев 2003, 17:17
Задача: Суперпростые числа
Определение:
Назовем натуральное число N суперпростым числом ранга R, если выполнены следующие условия:
а. Число N - простое.
б. Число М, полученное путем удаления из числа N цифры слева - суперпростое.
в. Число N - R-значное.
Примеры:
Число 3137 - суперпростое число ранга 4, так как числа 3137, 137, 37 и 7 - простые.
Число 2819 - не суперпростое, так как, несмотря на то, что простыми являются числа 2819 и 19, числа 819 и 9 - не простые.
Задача:
Написать программу для эффективного поиска суперпростых чисел.
Челлендж: Кто вычислит суперпростое число наибольшего ранга?
Назовем натуральное число N суперпростым числом ранга R, если выполнены следующие условия:
а. Число N - простое.
б. Число М, полученное путем удаления из числа N цифры слева - суперпростое.
в. Число N - R-значное.
Примеры:
Число 3137 - суперпростое число ранга 4, так как числа 3137, 137, 37 и 7 - простые.
Число 2819 - не суперпростое, так как, несмотря на то, что простыми являются числа 2819 и 19, числа 819 и 9 - не простые.
Задача:
Написать программу для эффективного поиска суперпростых чисел.
Челлендж: Кто вычислит суперпростое число наибольшего ранга?
- Marmot
- Графоман
- Сообщения: 38302
- Зарегистрирован: 17 фев 2003, 17:58
- Откуда: Canyon Heights
- Контактная информация:
- папа Карло
- Шарманщик
- Сообщения: 8563
- Зарегистрирован: 17 фев 2003, 15:04
- Откуда: НН -> BC -> WA -> UT -> CA
- Циник
- Завсегдатай
- Сообщения: 442
- Зарегистрирован: 17 фев 2003, 17:17
- Циник
- Завсегдатай
- Сообщения: 442
- Зарегистрирован: 17 фев 2003, 17:17
- папа Карло
- Шарманщик
- Сообщения: 8563
- Зарегистрирован: 17 фев 2003, 15:04
- Откуда: НН -> BC -> WA -> UT -> CA
- Marmot
- Графоман
- Сообщения: 38302
- Зарегистрирован: 17 фев 2003, 17:58
- Откуда: Canyon Heights
- Контактная информация:
Ну, я надеюсь что ты понимаешь что ответ на твой вопрос зависит от используемой системы исчисленияЦиник писал(а):Это тебе так кажется.Marmot писал(а):Это уже камасутра какая-то...Если уж говорить об ИМХО, то программисту полезнее думать об алгоритмах. Биты же - вообще дело восемнадцатое.Программеру, кстати, вредно думать о цифрах, полезнее о битах...IMHO
А биты они и в Африке биты...
А где нужны алгоритмы для этой камасутронной задачи я себе даже представить не могу. Вернее представить наверное можно, но вот то что денег на них не сделаешь - это уж наверняка...
- ajkj3em
- Маньяк
- Сообщения: 2063
- Зарегистрирован: 12 ноя 2006, 06:53
Re: Задача: Суперпростые числа
пис оф кэйк, тов циник. это где-то первый-второй семестр,Циник писал(а):Определение:
Назовем натуральное число N суперпростым числом ранга R, если выполнены следующие условия:
а. Число N - простое.
б. Число М, полученное путем удаления из числа N цифры слева - суперпростое.
в. Число N - R-значное.
Примеры:
Число 3137 - суперпростое число ранга 4, так как числа 3137, 137, 37 и 7 - простые.
Число 2819 - не суперпростое, так как, несмотря на то, что простыми являются числа 2819 и 19, числа 819 и 9 - не простые.
Задача:
Написать программу для эффективного поиска суперпростых чисел.
Челлендж: Кто вычислит суперпростое число наибольшего ранга?
раздел рекурсивных функций. единственное, что надо знать
- это тот факт, что в отличие от *разложения* на простые множители
задача тестирования данного числа на простоту решается со свистом
через малую т.ферма.
- Циник
- Завсегдатай
- Сообщения: 442
- Зарегистрирован: 17 фев 2003, 17:17
Понимаю, понимаю. Подразумевается, для удобства, десятичная система счисления. Распространить на любую другую - дело несложной техники, как ты понимаешь.Marmot писал(а):Ну, я надеюсь что ты понимаешь что ответ на твой вопрос зависит от используемой системы исчисления
Ну и куда ты в Африке с битами?А биты они и в Африке биты...
Они ближе, чем ты предполагаешь. Начнем с длинной арифметики (мы ведь не можем ограничится здесь даже 64 битами, надеюсь, ты понимаешь ). Просто набери в командной строке calc...А где нужны алгоритмы для этой камасутронной задачи я себе даже представить не могу.
А уж как сделать алгоритм эффективным, какой вычислительный метод применить - так это вещи достаточно универсальные, применимые во многих местах и не к одной какой-то задаче. А если даже и уникальное что-то придется изобресть, так это тоже часть професионализма - в следующий раз ты быстрее изобретешь что-то другое уникальное, для реальной задачи. Надеюсь, что ты понимаешь, товарищ
Про деньги речь никто и не вел, товарищ. Чистый пир духаВернее представить наверное можно, но вот то что денег на них не сделаешь - это уж наверняка...
- Циник
- Завсегдатай
- Сообщения: 442
- Зарегистрирован: 17 фев 2003, 17:17
Re: Задача: Суперпростые числа
Спорить о номере семестра не буду, товарищ Хух, не в этом суть.huh писал(а):пис оф кэйк, тов циник. это где-то первый-второй семестр, раздел рекурсивных функций.
К сожаленью, молодое поколение профессионалов от программирования ничего этого не знает и знать не хочет в 99% случаев.
P.S. Число давай
- Marmot
- Графоман
- Сообщения: 38302
- Зарегистрирован: 17 фев 2003, 17:58
- Откуда: Canyon Heights
- Контактная информация:
-
- Частый Гость
- Сообщения: 21
- Зарегистрирован: 27 фев 2003, 13:38
Да задача то элементарная. И нафига напрягаться?папа Карло писал(а):маньяк. я к тебе на интервью не пойду тогдаЦиник писал(а):За студента ответишь
P.S. Задача, кстати, весьма интересная. Я, пожалуй, что-то подобное на интервью давать буду.
Обчный цикл от одного до длины строчного представления числа.
А внутри модифицированное решето Эратосфена, которое возвращает true если число простое, и false в обратнои случае. Если на выходе ложь - возвращаем false, если нет - продолжаем. На выходе после цикла возвращаем true.
- Циник
- Завсегдатай
- Сообщения: 442
- Зарегистрирован: 17 фев 2003, 17:17
Ну-ну. Задача, может, и элементарная для свежего выпускника MIT, но 99% интервьюируемых ее до конца не решат. Подобная лакмусовая бумажка как раз и выявит пробелы в их базовых знаниях и их умение думать.ComputerMage писал(а):Да задача то элементарная. И нафига напрягаться?
"Ты мне не зюзюкай", ты число давай - тем более если это так элементарноОбчный цикл от одного до длины строчного представления числа.
А внутри модифицированное решето Эратосфена, которое возвращает true если число простое, и false в обратнои случае. Если на выходе ложь - возвращаем false, если нет - продолжаем. На выходе после цикла возвращаем true.
- fooit
- Пользователь
- Сообщения: 135
- Зарегистрирован: 17 фев 2003, 19:09
- Откуда: Toronto, ON
- Контактная информация:
Re: Задача: Суперпростые числа
Циник писал(а): Челлендж: Кто вычислит суперпростое число наибольшего ранга?
Смею предположить, что и самое большое суперпростое число будет иметь похожий ранг.The largest known prime (found by GIMPS [Great Internet Mersenne Prime Search] in December 2001) is the 39th Mersenne prime: M13466917 which has 4053946 decimal digits.
- Циник
- Завсегдатай
- Сообщения: 442
- Зарегистрирован: 17 фев 2003, 17:17
Re: 984276962971. Хватит?
Ура товарищу Зомби! Первый результат!
Во-вторых, это не суперпростое число, так как 1 (в разряде единиц) не простое. Нетрудно увидеть, что суперпростые числа могут оканчиваться только либо на 3, либо на 7.
Во-первых, маловато будет.Zombie писал(а): Re: 984276962971. Хватит?
Во-вторых, это не суперпростое число, так как 1 (в разряде единиц) не простое. Нетрудно увидеть, что суперпростые числа могут оканчиваться только либо на 3, либо на 7.
Именно за это мы и боремся!А если просто бороться за максимальный ранг, то вероятно будет эффективнее генерить число случайным образом и потом проверять его на суперпростоту.