habr.com — 12 октября 2024, почти 6 лет поиска. Самое большое известное простое число на сегодня, 41млн десятичных цифр. Предыдущее было 24.8 млн. цифр
Ну, например, число Мерсенна есть в стандарте С++11.
На их основе хорошие генераторы случайных чисел получаются - mersenne_twister_engine:
#include <random>
#include <stdio.h>
int main() {
std::mt19937 gen32;
printf("%d\n",gen32());
}
2^19937-1 - это 24-е число Мерсенна. Его искали 8 лет, с 1963 по 1971 годы.
Блин. Трудно гуманитарию жЫть. Прочитал (зачем-то), полез в гугел смотреть, что это такое - простое число. Затупил и спросил (зачем-то) жену. А она физмат заканчивала в своё время и чуть меня не съела.
В следующий раз буду у кота спрашивать, он простит.
> Блин. Трудно гуманитарию жЫть. Прочитал (зачем-то), полез в гугел смотреть, что это такое - простое число.
Делится только на себя и на единицу ;) Поэтому поиск таких чисел сложный, так как необходимо доказать это, а на числах с десятками миллионов цифр в значении - это весьма не просто.
Сложные - тоже есть, комплексные числа по-английски - complex numbers. А complex numbers - дословно по-русски - сложные числа.
И так выходит, что половину простых чисел можно разложить на сложные!
5 = (2+i)(2-i)
13 = (3+2i)(3-2i)
17 = (4+i)(4-i)
29 = (5+2i)(5-2i)
37 = (6+i)(6-i)
...
В этом ролике, кстати, показывают всё число целиком!
Пока чувак говорит, показывают 50 строчек по 80 цифр в каждой - первые 4000 цифр числа.
На следующем кадре ещё 4000 цифр.
Кадры сменяются 25 раз в секунду. За секунду можно увидеть 80 * 50 * 25 = 100 000 цифр.
Чтобы показать всё число в таком темпе, нужно более 410 секунд, почти 7 минут.
> На их основе хорошие генераторы случайных чисел получаются - mersenne_twister_engine:
> #include <random>
> #include <stdio.h>
> int main() {
> std::mt19937 gen32;
> printf("%d\n",gen32());
> }
>
> 2^19937-1 - это 24-е число Мерсенна. Его искали 8 лет, с 1963 по 1971 годы.
В смысле- хорошие? Там весь смысл криптографии - разложить число на простые. А тут такое число сладкое, куча единиц в 136 млн бит и в конце ноль!
Upd. А нахера его в десятичный разряд переводить? Что за шаблонность мышления ... Запишите на 32-х мегабайтную флешку и таскайте его в кармане
Проблема Гольдбаха (гипотеза Гольдбаха, проблема Эйлера, бинарная проблема Гольдбаха) — утверждение о том, что любое чётное число, начиная с 4, можно представить в виде суммы двух простых чисел.
С детства вызывает у меня религиозный трепет.
> Ответ на "Главный вопрос жизни, вселенной и вообще" - это 42.
> При чем тут всякие 73?
— Это 21 по порядку простое число.
— Зеркально отраженное число 37 тоже простое, и при этом оно 12 по порядку, то есть зеркально отраженное 21.
— Перемножение чисел 7 и 3 = 21.
— В бинарном виде 73 = 1001001, что является палиндромом.
На азбуке Морзе 73 — тоже палиндром.
Причём тут ответ на главный вопрос - не понятно. То, что ответ - 42, не делает 42 - отличным числом. Это просто 42.
> В смысле- хорошие? Там весь смысл криптографии - разложить число на простые.
Я там оговорился сначала, потом исправил. Не генераторы простых чисел, а генераторы случайных чисел.
У них какие требования? Числа должны выглядеть случайно - чтобы никакие статистические тесты не находили отклонений от равномерного распределения. Например, генерируя случайные числа в диапазоне от 0 до 999, должна быть вероятность 1/1000, что сгенерятся два одинаковых числа подряд. Ещё требование - длина периода должна быть как можно больше: если случайные числа генерятся алгоритмически, то, как не крути, со временем они начнут повторяться. Вот важно, чтобы это произошло как можно позже.
Другой пример генератора случайных чисел на основе простых чисел - алгоритм Блюм-Блюм-Шуба. Очень простой, но не самый быстрый. Берётся m = p*q, произведение двух простых чисел равных 3 по модулю 4 (числа Мерсенна все такие). Начальное число, от 2 до m-1, на каждом шаге возводится в квадрат по модулю m, и на выход отправляется младший бит. Вот он дохрена случайный получается.
> А тут такое число сладкое, куча единиц в 136 млн бит и в конце ноль!
Куча единиц и в конце тоже 1 :)
> Upd. А нахера его в десятичный разряд переводить? Что за шаблонность мышления ... Запишите на 32-х мегабайтную флешку и таскайте его в кармане
Во-первых это красиво!
А во-вторых, 136 миллионов единиц смотреть слишком скучно, некрасиво даже как-то.
Сейчас, сейчас
Новость на иностранном:[censored]
2000-летняя история поиска совершенных чисел, на русском:[censored]