LINUX.ORG.RU
решено Форум — Talks  

Простые числа.

 


0

1

Евклид первым доказал, что простых чисел бесконечно много. Согласно его док-ву, если взять какой-либо рубеж, то при перемножении всех простых чисел, которые идут до этого рубежа, и прибавлении единицы получается новое простое число. Окей. 2*3*5*7*11*13+1 нифига не простое и делится на 59. Евклид ошибся или я чего-то недопонял?

← Что за виндовые замашки?
Сегодня 14 октября кедам исполняется 16 лет! →

Евклид ошибся или я чего-то недопонял?

Да, ты недопонял суть доказательства от противного.

metar ★★★
()

Из википедии:

Представим, что количество простых чисел конечно. Перемножим их и прибавим единицу. Полученное число не делится ни на одно из конечного набора простых чисел, потому что остаток от деления на любое из них даёт единицу. Значит, число должно делиться на некоторое простое число, не включённое в этот набор. Противоречие.

Sadler ★★★
()

Недопонял.
Если бы простых чисел было бы конечное множество (p1, p2, ..., pn), то число (p1*p2*...*pn + 1) не делилось бы ни на одно из них. Но, благодаря теореме о существовании разложения числа на простые множители (для существования там почти ничего не нужно, кстати), так не бывает.

yura_ts ★★
()
Ответ на: комментарий от Sadler

Спасибо большое, я так и думал, что что-то неправильно понял.

sgasgar1234
() автор топика

Окей. 2*3*5*7*11*13+1 нифига не простое и делится на 59

А с каких пор 59 меньше 13?

DNA_Seq ★★☆☆☆
()

Кстати, а как понять, простое ч-ло или нет, без деления на все предыдущие в цикле?

f1xmAn ★★★★★
()
Ответ на: комментарий от LongLiveUbuntu

Дадут. Не везет с математикой - повезет в любви!

stevejobs ★★★★☆
()
Ответ на: комментарий от jtootf

Тест Соловея — Штрассена неплох, например, да. Я его когда-то даже руками реализовывал на Сях.

Sadler ★★★
()

59 - это простое число. к слову, 509, которое в результате получится, тоже. но мы-то предположили, что за пределами 13 простых чисел нету, так что твой пример не шибко корректен, да и вообще подобные. кроме того, тут не на практике нужно проверять (доказательство-то от противного, поэтому подразумевается, что сделанное предположение ошибочно), а в абстракцию вдаваться. смешал всё в кашу, но как-то так

xsektorx ★★★
()

Boy meet world? Евклидову теорему уже сто раз уточнили.

vahtu
()
Ответ на: комментарий от DuratarskeyK

If `factor' is built without using GNU MP, only single-precision arithmetic is available

внезапно!

maloi ★★★★★
()

Да. Вот так и появляются фоменки, инглиисты и прочие теоретики заговоров и опровергатели теории относительности.

Sociopsih ★☆
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
← Что за виндовые замашки?
Talks
Сегодня 14 октября кедам исполняется 16 лет! →