Задача: Суперпростые числа

Все, что вы хотели знать о программизме, но боялись спросить.
Аватара пользователя
Циник
Завсегдатай
Сообщения: 442
Зарегистрирован: 17 фев 2003, 17:17

Задача: Суперпростые числа

Сообщение Циник »

Определение:
Назовем натуральное число 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
Контактная информация:

Сообщение Marmot »

Это уже камасутра какая-то... :-)

PS

Программеру, кстати, вредно думать о цифрах, полезнее о битах...IMHO
:lol:
Аватара пользователя
папа Карло
Шарманщик
Сообщения: 8563
Зарегистрирован: 17 фев 2003, 15:04
Откуда: НН -> BC -> WA -> UT -> CA

Сообщение папа Карло »

Marmot писал(а):Это уже камасутра какая-то... :-)

PS

Программеру, кстати, вредно думать о цифрах, полезнее о битах...IMHO
:lol:
это не камасутра... он посто всех разводит. :) студент, блин ;)
Аватара пользователя
Циник
Завсегдатай
Сообщения: 442
Зарегистрирован: 17 фев 2003, 17:17

Сообщение Циник »

Marmot писал(а):Это уже камасутра какая-то... :-)
Это тебе так кажется.
Программеру, кстати, вредно думать о цифрах, полезнее о битах...IMHO
Если уж говорить об ИМХО, то программисту полезнее думать об алгоритмах. Биты же - вообще дело восемнадцатое.
Аватара пользователя
Циник
Завсегдатай
Сообщения: 442
Зарегистрирован: 17 фев 2003, 17:17

Сообщение Циник »

папа Карло писал(а):это не камасутра... он посто всех разводит. :) студент, блин ;)
За студента ответишь :twisted:

P.S. Задача, кстати, весьма интересная. Я, пожалуй, что-то подобное на интервью давать буду.
Аватара пользователя
папа Карло
Шарманщик
Сообщения: 8563
Зарегистрирован: 17 фев 2003, 15:04
Откуда: НН -> BC -> WA -> UT -> CA

Сообщение папа Карло »

Циник писал(а):За студента ответишь :twisted:

P.S. Задача, кстати, весьма интересная. Я, пожалуй, что-то подобное на интервью давать буду.
маньяк. :) я к тебе на интервью не пойду тогда :)
Аватара пользователя
Marmot
Графоман
Сообщения: 38302
Зарегистрирован: 17 фев 2003, 17:58
Откуда: Canyon Heights
Контактная информация:

Сообщение Marmot »

Циник писал(а):
Marmot писал(а):Это уже камасутра какая-то... :-)
Это тебе так кажется.
Программеру, кстати, вредно думать о цифрах, полезнее о битах...IMHO
Если уж говорить об ИМХО, то программисту полезнее думать об алгоритмах. Биты же - вообще дело восемнадцатое.
Ну, я надеюсь что ты понимаешь что ответ на твой вопрос зависит от используемой системы исчисления :-)
А биты они и в Африке биты...
А где нужны алгоритмы для этой камасутронной задачи я себе даже представить не могу. Вернее представить наверное можно, но вот то что денег на них не сделаешь - это уж наверняка...
Аватара пользователя
ajkj3em
Маньяк
Сообщения: 2063
Зарегистрирован: 12 ноя 2006, 06:53

Re: Задача: Суперпростые числа

Сообщение ajkj3em »

Циник писал(а):Определение:
Назовем натуральное число N суперпростым числом ранга R, если выполнены следующие условия:
а. Число N - простое.
б. Число М, полученное путем удаления из числа N цифры слева - суперпростое.
в. Число N - R-значное.

Примеры:
Число 3137 - суперпростое число ранга 4, так как числа 3137, 137, 37 и 7 - простые.
Число 2819 - не суперпростое, так как, несмотря на то, что простыми являются числа 2819 и 19, числа 819 и 9 - не простые.

Задача:
Написать программу для эффективного поиска суперпростых чисел.

Челлендж: Кто вычислит суперпростое число наибольшего ранга?
пис оф кэйк, тов циник. это где-то первый-второй семестр,
раздел рекурсивных функций. единственное, что надо знать
- это тот факт, что в отличие от *разложения* на простые множители
задача тестирования данного числа на простоту решается со свистом
через малую т.ферма.
Аватара пользователя
Циник
Завсегдатай
Сообщения: 442
Зарегистрирован: 17 фев 2003, 17:17

Сообщение Циник »

Marmot писал(а):Ну, я надеюсь что ты понимаешь что ответ на твой вопрос зависит от используемой системы исчисления :-)
Понимаю, понимаю. Подразумевается, для удобства, десятичная система счисления. Распространить на любую другую - дело несложной техники, как ты понимаешь.
А биты они и в Африке биты...
Ну и куда ты в Африке с битами? :twisted:
А где нужны алгоритмы для этой камасутронной задачи я себе даже представить не могу.
Они ближе, чем ты предполагаешь. Начнем с длинной арифметики (мы ведь не можем ограничится здесь даже 64 битами, надеюсь, ты понимаешь :twisted: ). Просто набери в командной строке calc... :twisted:

А уж как сделать алгоритм эффективным, какой вычислительный метод применить - так это вещи достаточно универсальные, применимые во многих местах и не к одной какой-то задаче. А если даже и уникальное что-то придется изобресть, так это тоже часть професионализма - в следующий раз ты быстрее изобретешь что-то другое уникальное, для реальной задачи. Надеюсь, что ты понимаешь, товарищ :twisted:
Вернее представить наверное можно, но вот то что денег на них не сделаешь - это уж наверняка...
Про деньги речь никто и не вел, товарищ. Чистый пир духа :twisted:
Аватара пользователя
Циник
Завсегдатай
Сообщения: 442
Зарегистрирован: 17 фев 2003, 17:17

Re: Задача: Суперпростые числа

Сообщение Циник »

huh писал(а):пис оф кэйк, тов циник. это где-то первый-второй семестр, раздел рекурсивных функций.
Спорить о номере семестра не буду, товарищ Хух, не в этом суть.
К сожаленью, молодое поколение профессионалов от программирования ничего этого не знает и знать не хочет в 99% случаев.

P.S. Число давай :twisted:
Аватара пользователя
Marmot
Графоман
Сообщения: 38302
Зарегистрирован: 17 фев 2003, 17:58
Откуда: Canyon Heights
Контактная информация:

Сообщение Marmot »

Циник писал(а):
Marmot писал(а):Ну, я надеюсь что ты понимаешь что ответ на твой вопрос зависит от используемой системы исчисления :-)
Понимаю, понимаю. Подразумевается, для удобства, десятичная система счисления.
Мне простительно, ровно 9 лет и неделю назад я пересёк экватор... :-)

[/quote]
ComputerMage
Частый Гость
Сообщения: 21
Зарегистрирован: 27 фев 2003, 13:38

Сообщение ComputerMage »

папа Карло писал(а):
Циник писал(а):За студента ответишь :twisted:

P.S. Задача, кстати, весьма интересная. Я, пожалуй, что-то подобное на интервью давать буду.
маньяк. :) я к тебе на интервью не пойду тогда :)
Да задача то элементарная. И нафига напрягаться?

Обчный цикл от одного до длины строчного представления числа.
А внутри модифицированное решето Эратосфена, которое возвращает true если число простое, и false в обратнои случае. Если на выходе ложь - возвращаем false, если нет - продолжаем. На выходе после цикла возвращаем true.
Аватара пользователя
Циник
Завсегдатай
Сообщения: 442
Зарегистрирован: 17 фев 2003, 17:17

Сообщение Циник »

ComputerMage писал(а):Да задача то элементарная. И нафига напрягаться?
Ну-ну. Задача, может, и элементарная для свежего выпускника MIT, но 99% интервьюируемых ее до конца не решат. Подобная лакмусовая бумажка как раз и выявит пробелы в их базовых знаниях и их умение думать.
Обчный цикл от одного до длины строчного представления числа.
А внутри модифицированное решето Эратосфена, которое возвращает true если число простое, и false в обратнои случае. Если на выходе ложь - возвращаем false, если нет - продолжаем. На выходе после цикла возвращаем true.
"Ты мне не зюзюкай", ты число давай - тем более если это так элементарно :twisted:
Аватара пользователя
fooit
Пользователь
Сообщения: 135
Зарегистрирован: 17 фев 2003, 19:09
Откуда: Toronto, ON
Контактная информация:

Re: Задача: Суперпростые числа

Сообщение fooit »

Циник писал(а): Челлендж: Кто вычислит суперпростое число наибольшего ранга?
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. Хватит?

Сообщение Циник »

Ура товарищу Зомби! Первый результат!
Zombie писал(а): Re: 984276962971. Хватит?
Во-первых, маловато будет.
Во-вторых, это не суперпростое число, так как 1 (в разряде единиц) не простое. Нетрудно увидеть, что суперпростые числа могут оканчиваться только либо на 3, либо на 7.
А если просто бороться за максимальный ранг, то вероятно будет эффективнее генерить число случайным образом и потом проверять его на суперпростоту.
Именно за это мы и боремся! :twisted:
Ответить