Составление Простого Числа Опции

[Hindelberg]

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

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

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

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

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

[Altair]

которые можно составить из введенных пользователем чисел.

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

Например: 1 2 4 5 9
k=5

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

[volvo]

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

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

[Altair]

из K цифр создать

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

Например: 1 2 4 5 9
k=5

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

[volvo]

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

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

Пользователь вводит k(<=1000) чисел в файл

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

[Altair]

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

Hindelberg, для примера своего:
QUOTE
Например: 1 2 4 5 9
k=5

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

[Hindelberg]

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

Сообщение отредактировано: Hindelberg - 20.11.2005 11:23

[volvo]

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

[Altair]

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

причем должны использоваться все цифры из файла.

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

[Hindelberg]

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

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

плясать в сторону признаков делимости на определенные числа

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

[volvo]

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

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

[Hindelberg]

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

[volvo]

Значит тебе прямая дорога в FAQ: Длинная арифметика, и запасайся терпением, 1000 цифр будут обрабатываться достаточно долго... Хотя перебор можно тоже значительно сократить (пользуясь теми же принципами, о которых я говорил выше)...

[Hindelberg]

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

М

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

[volvo]

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

[Hindelberg]

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

[virt]

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

[Altair]

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

Это как?

[FreeMan]

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