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

Albor · 27 май 2008, 17:47

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

Зачем на все?, выше уже писали "до корня из N". Можно "перепрыгивать" чётные делители - проверить только двойку.

chur · 27 май 2008, 19:03

Это неверно, что если p простое, то и 2^p-1 то же простое.
Верно только, что если p составное, то и 2^p-1 то же составное.

BBB · 28 май 2008, 10:35

chur писал(а):Это неверно, что если p простое, то и 2^p-1 то же простое.

А контрпример привести можете? (Я не говорю, что это неверно, как я писал выше, я сам точно в этом не уверен. Просто интересно взглянуть на пример)

Хыиуду · 28 май 2008, 11:24

Albor писал(а):Так вроде 7 получается.

Ай, мозги совсем состарились... Вы правы
MaksSsimuS, см. раздел "Алгоримы", тема "Определение простоты числа".

Хыиуду · 28 май 2008, 11:25

Хыиуду писал(а):Ай, мозги совсем состарились... Вы правы

MaksSsimuS, см. раздел "Алгоритмы", тема "простые числа"

Хыиуду · 28 май 2008, 11:29

chur писал(а):Это неверно, что если p простое, то и 2^p-1 то же простое.
Верно только, что если p составное, то и 2^p-1 то же составное.

Также верно, что если 2^p-1 простое, то p тоже простое.

somewhere · 28 май 2008, 11:31

Легко. На самом деле утверждение

если p простое, то и 2^p-1 то же простое

неверно. Например 2047 (2^11-1) делится на 23. Любое из такие чисел, кажется, имеет минимум один делитель вида 2n+1 (2*11 + 1)
В качестве помощи проблеме настоятельно рекомендую почитать вот здесь

BBB · 28 май 2008, 11:58

somewhere, спасибо за контрпример.

Albor · 28 май 2008, 12:58

somewhere писал(а): Любое из такие чисел, кажется, имеет минимум один делитель вида 2n+1 (2*11 + 1)

Из представленной статьи видно, что число Мерсенна может быть простым, а может и не быть таковым. Поэтому, "минимум один делитель" - неверно.

chur · 28 май 2008, 13:13

Количество известных простых чисел Мерсена на данный момент чуть более 40 штук. Не 40 тысяч, а просто 40.
Т.е. с вероятностью близкой к единице число вида 2^p-1 будет составным