Задача о минимальном числе с изв. к-вом делитей. Опции

[Digitalator]

Я тут почитал задачки, на форуме - все простенькие такие.
Дать вам одну для разминки серого вещества ?

собственно сабж - дано некоторое число n E [1,1000], найти минимальное число имеющее ровно n делителей (любых, без повторений).
Все бы ничего, но - таймлимит 5 сек на P3 500... использовать не больше 640кб мозгов... вот так

У меня там еще задачки были, посложнее потом откопаю....

[zx1024]

Если считать само число и 1, то 2^(n-1).
Куда уж меньше.
Делителями будут числа 2^i, где i=0,...,(n-1).

[Digitalator]

Перед тем как отвечать, подумай и проверь! Твое "решение" в корне не верно!
например, нужно 4 делителя - по твоей "схеме" получаетс 2^(4-1)=8, а на самом деле 6 - тут делители 1,2,3,6

[zx1024]

Твое "решение" в корне не верно!

С "корнем" ты загнул. Для простых n верно.

[zx1024]

Да, с "корнем" ты, действительно, загнул.
Придумал я алгоритм. И там, показанная ранее "схема", является основой решения.
Давай тесты, если есть. Где n побольше. Ессно с ответами.

[Digitalator]

покажи алгоритм
а лучше прогу, чтоб можно было сразу на таймлимит проверить

PS: ну с корнем я можь и загнул - 2^n первое что всем лезет в голову, но верно, как правильно заметил, только для простых

Сообщение отредактировано: Digitalator - 30.10.2004 21:40

[zx1024]

Лень прогу писать.
Нужен массив простых чисел (чтоб в проге не считать)- B (по возраст.).
B = 2,3,5,7,11,13,...
Надо разложить n на простые множители и 8(пусть они k1...kj) и составить массив A. A[i] = k[i]-1. 8 - критич. число. Для неё в A добавляется 3 и 1. Сортируем A по убыванию.
Ответом будет произведение B[i]^A[i].
Пример n = 28 = 7*2*2.
A = 6,1,1. Ответ - 2^6 * 3^1 * 5^1 = 960.
n = 16 = 8 * 2.
A = 3,1,1. Ответ - 2^3 * 3 * 5 = 120.
Поэтому я и просил тесты. Мож ещё где (кроме 8) не работает общая схема.

Время. Разложение числа до 1000 на простые множители. Сортировка (очень маленького массива). Возведение в степень и произведение больших чисел.

[Altair]

Digitalator, сформулируйте пожалуйста уловие точнее...
Я правильно понял:
Дано:
Целое число n из промежутка [1,1000]

Требуется:
Нати минимальное целое, положительное число, имеющее n делитетей. (n заданно).

[Digitalator]

Да. а где неточно условие?

to zx1024
Вроде как все правильно... но надо еще проверить... ;)

[Altair]

Все ясно.... к сожалению меня лишили возможности думать над этот задачей, показав рещение