Версия для печати темы

Автор: Hindelberg 20.11.2005 15:00

Никак не могу сообразить эту задачу.
Прошу наводку или подсказку.

Пользователь вводит k(<=1000) чисел в файл.
Вывести все k-значные простые числа(если возможно), которые можно составить из введенных пользователем чисел.

Как составить из неизвестного кол-ва цифр число?

Например: 1 2 4 5 9
k=5
это надо определить сколько чисел,
и потом 1*10^(k-1)+ 2*10^(k-2) и Т.д.?

И как быть с 1000? Возможно по какой-то закономерности возможно меньшее кол-во чисел?

Автор: Altair 20.11.2005 15:11

это как ? именно из числел или из всех цифр которые ввеенны ?
то есть если

7 можно указать или нет ?
а 3 ?

Автор: volvo 20.11.2005 15:11

Hindelberg,
попробуй почитать про перестановки (по-моему в FAQ-е было), это поможет тебе из K цифр создать все возможные числа...

Если нужны такие большие K, то смотри и "Длинную арифметику"

Автор: Altair 20.11.2005 15:13

тогда гораздо проще исользовать множество... заполнить его цифрами встречающимися в числах и протсо перебрать
for i:=1 to <верхний предел> do ..
если протсое и составляется из цифр множества то ....
Hindelberg, для примера своего:

напиши несколько допустимых чисел

Автор: volvo 20.11.2005 15:14

Altair
Пример в студию...

Кстати, Hindelberg, вопрос:

Чисел, или все-таки цифр?

Автор: Altair 20.11.2005 15:18

To: volvo, только после того как автор ответит, пока задание не точно..

Автор: Hindelberg 20.11.2005 15:20

я не совсем точно описал условие.
Имеется файл. В него вводятся куча(<=1000) цифр. И нужно проверить сколько из этих цифр можно составить простых чисел, причем должны использоваться все цифры из файла.
Цифры любые, т.е. 0 1 2 3 4 5 6 7 8 9

Автор: volvo 20.11.2005 15:27

Hindelberg, скорее всего тут надо брать бубен и плясать в сторону признаков делимости на определенные числа, потому что все 1000 цифр перебирать, да еще и проверять на простоту числа - ресурсов не хватит никаких...

Автор: Altair 20.11.2005 15:32

мне кажется он задание все же не так как то произносит...
уж слишком это задача туманная и сложная...
если там 1000 цифр будет и

то это простите 1000 значное число ....

Автор: Hindelberg 20.11.2005 15:42

Правильно я произношу. Сказано- Некоторое кол-во цифр k(k<=1000).


Это я понимаю, но как это сделать я не могу сообразить.

Автор: volvo 20.11.2005 15:49

Ну, например, так:
1. Проверяешь, сколько всего цифр. С учетом этого вычисляешь, сколько чисел может быть составлено из этого количества цифр (для простоты будем считать, что допустимы числа типа "00093", "00903", ...)
2. Есть ли 2-ки? Есть... Сколько чисел можно составить, что в конце будет 2-ка? Отнимаешь это количество от общего количества возможных вариантов...
3. Есть ли 3-ки (и делится ли сумма всех цифр на 3), ... и т.д.

Чистая комбинаторика... В этом направлении я бы двигался...

Автор: Hindelberg 20.11.2005 15:52

Таким образом можно найти кол-во простых чисел. А ведь надо еще их вывести всех.

Автор: volvo 20.11.2005 15:56

Значит тебе прямая дорога в http://forum.pascal.net.ru/index.php?showtopic=2428, и запасайся терпением, 1000 цифр будут обрабатываться достаточно долго... Хотя перебор можно тоже значительно сократить (пользуясь теми же принципами, о которых я говорил выше)...

Автор: Hindelberg 20.11.2005 20:32

Это задача из олимпиадных. Так что врядли там приемлима Длинная Арифметика и долгая обработка...

М

А как ты собрался БЕЗ длинной арифметики и длительно обработки с числом скажем состоящим из 769 цифр работать?!! klem4

Автор: volvo 20.11.2005 20:40

To: Hindelberg
Олимпиадная? Это хакерская задача, ты мне-то сказки не рассказывай. Подбор ключей RSA делается по той же схеме: простые числа из 200+ цифр и их обработка...

Автор: Hindelberg 20.11.2005 21:39

Это задача с заочной олимпиады для старшеклассников за 2005-2006 год. Недавно была и я не решил эту задачу. Вот и стало интересно.
Листок сохранился, если ты так не веришь могу сфотать и прислать.

Автор: virt 20.11.2005 22:14

volvo
я на республиканских сборах по информатике в этом году хочу дать задачу подбора ключа к RSA 32 или 64 битного.

Автор: Altair 20.11.2005 22:15

Это как?

Автор: FreeMan 21.11.2005 22:20

Почитай про алгоритм Рабина-Миллера. Значительно уменьшает время поиска. Но всё-равно без длинной арифметики никуда