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

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

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

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

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

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

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

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

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

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

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

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

Кстати, Hindelberg, вопрос:
Чисел, или все-таки цифр?

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

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

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

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

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

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


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

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

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

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

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

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

М

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

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

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

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

Это как?

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