Страница 2 из 3
Re: Задачка по си++,очень интересная=)
Добавлено: 27 май 2008, 17:47
Albor
MaksSsimuS писал(а):Да,так и получается,если мы берем простое число p,то у нас в результате будет тож простое.....но скажите,как определить число p простым.....по идее оно должно делиться только на себя и на 1.так получаеся,что надо определенное число брать и делить на все числа стоящие перед ним???чтобы определить простоту???или как проще?и как выделить памятьт под массив???подскажите=)
Зачем на все?, выше уже писали "до корня из N". Можно "перепрыгивать" чётные делители - проверить только двойку.
Re: Задачка по си++,очень интересная=)
Добавлено: 27 май 2008, 19:03
chur
Это неверно, что если p простое, то и 2^p-1 то же простое.
Верно только, что если p составное, то и 2^p-1 то же составное.
.
Добавлено: 28 май 2008, 10:35
BBB
chur писал(а):Это неверно, что если p простое, то и 2^p-1 то же простое.
А контрпример привести можете? (Я не говорю, что это неверно, как я писал выше, я сам точно в этом не уверен. Просто интересно взглянуть на пример)
Re: Задачка по си++,очень интересная=)
Добавлено: 28 май 2008, 11:24
Хыиуду
Albor писал(а):Так вроде 7 получается.
Ай, мозги совсем состарились... Вы правы
MaksSsimuS, см. раздел "Алгоримы", тема "Определение простоты числа".
Re: Задачка по си++,очень интересная=)
Добавлено: 28 май 2008, 11:25
Хыиуду
Хыиуду писал(а):Ай, мозги совсем состарились... Вы правы
MaksSsimuS, см. раздел "Алгоритмы", тема "простые числа"
Re: Задачка по си++,очень интересная=)
Добавлено: 28 май 2008, 11:29
Хыиуду
chur писал(а):Это неверно, что если p простое, то и 2^p-1 то же простое.
Верно только, что если p составное, то и 2^p-1 то же составное.
Также верно, что если 2^p-1 простое, то p тоже простое.
Re: Задачка по си++,очень интересная=)
Добавлено: 28 май 2008, 11:31
somewhere
Легко. На самом деле утверждение
если p простое, то и 2^p-1 то же простое
неверно. Например 2047 (2^11-1) делится на 23. Любое из такие чисел, кажется, имеет минимум один делитель вида 2n+1 (2*11 + 1)
В качестве помощи проблеме настоятельно рекомендую почитать
вот здесь
Re: Задачка по си++,очень интересная=)
Добавлено: 28 май 2008, 11:58
BBB
somewhere, спасибо за контрпример.
Re: Задачка по си++,очень интересная=)
Добавлено: 28 май 2008, 12:58
Albor
somewhere писал(а): Любое из такие чисел, кажется, имеет минимум один делитель вида 2n+1 (2*11 + 1)
Из представленной статьи видно, что число Мерсенна может быть простым, а может и не быть таковым. Поэтому, "минимум один делитель" - неверно.
Re: Задачка по си++,очень интересная=)
Добавлено: 28 май 2008, 13:13
chur
Количество известных простых чисел Мерсена на данный момент чуть более 40 штук. Не 40 тысяч, а просто 40.
Т.е. с вероятностью близкой к единице число вида 2^p-1 будет составным
