Задачка по си++,очень интересная=)

[MaksSsimuS]

Дано натуральное число n. Найти все меньшие n числа Мерсена. Простое число называется числом Мерсена, если оно может быть представлено в виде (2^p)-1 , где p – тоже простое число.
Буду очень признателен,если поможете или подскажете,как ее решать=)....

[chnry]

393877844
Могу за 500 руб продать прогу, которая проверяет, является ли число простым. Длина числа от 1 до 255 цифр.

[chnry]

Прога написана на языке Паскаль

[un4-funeral]

определить простое число или нет легко

прогоняем цикл от одного до n и смотрим делится ли n на это число без остатка
если без остатка, то наращиваем какую-то переменную

если после прохождения цикла она = 2, то число простое

а по задаче
заносишь в массив все числа простые от 1 до n (как определить простые я уже написал)
а потом по формуле твоей (2^p)-1 проверяешь каждый элемент массива к твоему n


chnry, щутник )))

[Хыиуду]

un4-funeral, да будет вам, все еще проще. Цикл достаточно проводить от 2 до корня из N. Вообще в разделе Алгоритмы это есть.

>>заносишь в массив все числа простые от 1 до n (как определить простые я уже написал) а потом по формуле твоей (2^p)-1 проверяешь каждый элемент массива к твоему n
Каждый - не надо. Как только 2^p-1 превысит N, цикл можно прерывать.

[chur]

Вообщем-то, практически определить является ли достаточно большое число простым, не такая, мягко скажем, простая задача . Японские криптологи год раскладывали на множители 300-битное число (90 десятичных порядков). И это с использованием хрен знает каких машин и извращенных алгоритмов.
А тут все удовольствие за 500 руб. Улыбнул

А по задаче. Тупо составляешь заранее массив из простых чисел Мерсена (благо их совсем мало) и простым пробегом по массиву определяешь количество чисел меньше n. Всё.

[BBB]

Простое число называется числом Мерсена, если оно может быть представлено в виде (2^p)-1 , где p – тоже простое число.

Че-то мне смутно помнится, что если p не является простым, то и (2^p)-1 тоже не будет простым... Или противоположное утверждение верно: если p - простое, то и (2^p)-1 тоже простое. А, может, оба верны... Не помню уже.

[Хыиуду]

Второе явно неверно. 3 - простое, 2^3-1=8, не простое

[Albor]

Второе явно неверно. 3 - простое, 2^3-1=8, не простое

Так вроде 7 получается.

[MaksSsimuS]

Да,так и получается,если мы берем простое число p,то у нас в результате будет тож простое.....но скажите,как определить число p простым.....по идее оно должно делиться только на себя и на 1.так получаеся,что надо определенное число брать и делить на все числа стоящие перед ним???чтобы определить простоту???или как проще?и как выделить памятьт под массив???подскажите=)