Простые числа и не очень

@йот · Регистрация: 08.09.2017

Студворк — интернет-сервис помощи студентам

Меня интересует Алгоритм, который мог бы выдавать, не обязательно в порядке возрастания, простые числа в пределах от 1 до 1 миллиона.

Решение и Объяснение задачи
1. числа вида $https://www.cyberforum.ru/cgi-bin/latex.cgi?6n\pm1$ выдают очень много простых чисел, но среди них немало и составных чисел...
2. Нужен Алгоритм, который выдавал бы "на гора" еще больше простых чисел и еще меньше составных.
3. Буду рад каждой формуле, предложенной вами...
...
примечание
1. Список простых чисел от 1 до 1 миллиона меня не интересует
2. Пусть будет формула... Или список формул...
3. Если в нескольких формулах простые числа пересекаются (повторяются), то все нормально...

@Igor3D · 04.10.2017, 07:52

Если нужны формулы - лучше посоветоваться с математиками, "алгоритмизировать" тут нечего, формула либо есть, либо нет

@йот · 04.10.2017, 08:18 **[ТС]**

Igor3D
вы действительно считаете, что система простых
квадратичных формул ничего не даст?

@Igor3D · 04.10.2017, 14:06

Сообщение от йот

вы действительно считаете, что система простых
квадратичных формул ничего не даст?

Ничего не считаю, просто это дело математиков (а не программистов)

Не по теме:

Если у человека есть время таким заниматься - значит проектом он не очень загружен

@salam · 04.10.2017, 15:36

найдите все простые до миллиона, интерполируйте полиномом и будет вам формула. вряд ли можно придумать что-то более конструктивное.

@йот · 04.10.2017, 17:49 **[ТС]**

salam
для этого нужен супер-компьютер... а так...
так ничего не выйдет...

Байт · 04.10.2017, 18:09

Сообщение от йот

еще больше простых чисел и еще меньше составных.

Еще меньше составных выдает 30n +- k, где k=1, 7, 11, 13
Причем решето Эратосфена, построенное на этой формуле, оказывается очень компактным. 1 байт = 8 битов = количеству разных остатков, которые может давать простое число при делении на 30. (Конечно, исключая первую тридцатку)
А вообще-то есть вероятностные методы нахождения простых чисел. Точнее, чисел, которые с большой вероятностью окажутся простыми. Но они, кажется, имеют смысл для больших чисел.

@йот · 04.10.2017, 18:16 **[ТС]**

Байт,
спасибо... А вы не могли бы в двух словах описать
поиск таких чисел... Нет, я конечно догадываюсь...
Взять сотню простых чисел и "наугад" проверять...
подойдет - не подойдет.

Байт · 04.10.2017, 19:18

Сообщение от йот

я конечно догадываюсь...

Нет, там как-то по другому, довольно интересно... Но вот как именно - не помню. Но мы же в век интернета живем! Попробуйте поискать...

@йот · 04.10.2017, 19:28 **[ТС]**

Байт,
Спасибо!

@oldnick85 · 04.10.2017, 20:39

Вот интересная (но на практике почти бесполезная) штука: полином Матиясевича.
Здесь его статья о формулах для простых чисел. Осторожно, матан! Кстати, обратите внимание на приведённый в этой статье многочлен $https://www.cyberforum.ru/cgi-bin/latex.cgi?x^2+x+41$

@йот · 05.10.2017, 08:56 **[ТС]**

oldnick85
Спасибо, это было очень интересно познакомиться с таким многочленом,
но меня интересует обычный многочлен от одной или двух переменных...
Он не обязан выдавать только простые числа. Пусть выдает и составные.
Но простых должно быть больше, чем составных...

@Shamil1 · 05.10.2017, 16:46

Сообщение от йот

но меня интересует обычный многочлен от одной или двух переменных

А разве это не обычный? И очень простой. И выдаёт много простых чисел.

@йот · 05.10.2017, 16:51 **[ТС]**

Shamil1
Тот многочлен хоть и выдает все простые числа, но считать будет
долго и много... Это проще массив забить простыми числами...

@Shamil1 · 05.10.2017, 17:13

йот,
x^2+x+41 будет долго считаться?

Сообщение от oldnick85

обратите внимание на приведённый в этой статье многочлен x^2+x+41

@йот · 05.10.2017, 17:29 **[ТС]**

Shamil1,
нет, этот многочлен быстро считается... потом его
можно записать и так x^2 + x + 41 = x(x + 1) + 41
...
только он один такой...

@Shamil1 · 05.10.2017, 17:33

Сообщение от йот

можно записать и так x^2 + x + 41 = x(x + 1) + 41

На количество операций это не влияет.

@йот · 05.10.2017, 17:36 **[ТС]**

Shamil1,
Спасибо, я обязательно посчитаю в каком отношении
к составным числам он выдает простые числа. Спасибо!!

@Shamil1 · 05.10.2017, 17:49

Сообщение от йот

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

Меньше миллиона:
Из первых 999 чисел, вычисленных по формуле, 580 простых. А всего простых 78498.

@йот · 05.10.2017, 18:04 **[ТС]**

Shamil1,
Спасибо!!

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

@йот 27 / 32 / 14 Регистрация: 08.09.2017 Сообщений: 448

	Простые числа и не очень 03.10.2017, 19:00. Показов 1619. Ответов 22 Метки нет (Все метки) Меня интересует Алгоритм, который мог бы выдавать, не обязательно в порядке возрастания, простые числа в пределах от 1 до 1 миллиона. Решение и Объяснение задачи 1. числа вида $https://www.cyberforum.ru/cgi-bin/latex.cgi?6n\pm1$ выдают очень много простых чисел, но среди них немало и составных чисел... 2. Нужен Алгоритм, который выдавал бы "на гора" еще больше простых чисел и еще меньше составных. 3. Буду рад каждой формуле, предложенной вами... ... примечание 1. Список простых чисел от 1 до 1 миллиона меня не интересует 2. Пусть будет формула... Или список формул... 3. Если в нескольких формулах простые числа пересекаются (повторяются), то все нормально... 0

@Igor3D 1968 / 824 / 115 Регистрация: 01.10.2012 Сообщений: 4,855 Записей в блоге: 2
	04.10.2017, 07:52
	Сообщение было отмечено йот как решение Решение Если нужны формулы - лучше посоветоваться с математиками, "алгоритмизировать" тут нечего, формула либо есть, либо нет 0

@йот 27 / 32 / 14 Регистрация: 08.09.2017 Сообщений: 448
	04.10.2017, 08:18 [ТС]
	Igor3D вы действительно считаете, что система простых квадратичных формул ничего не даст? 0

@salam 194 / 174 / 30 Регистрация: 10.07.2012 Сообщений: 800
	04.10.2017, 15:36
	Сообщение было отмечено йот как решение Решение найдите все простые до миллиона, интерполируйте полиномом и будет вам формула. вряд ли можно придумать что-то более конструктивное. 0

@йот 27 / 32 / 14 Регистрация: 08.09.2017 Сообщений: 448
	04.10.2017, 17:49 [ТС]
	salam для этого нужен супер-компьютер... а так... так ничего не выйдет... 0

@йот 27 / 32 / 14 Регистрация: 08.09.2017 Сообщений: 448
	04.10.2017, 18:16 [ТС]
	Байт, спасибо... А вы не могли бы в двух словах описать поиск таких чисел... Нет, я конечно догадываюсь... Взять сотню простых чисел и "наугад" проверять... подойдет - не подойдет. 0

@йот 27 / 32 / 14 Регистрация: 08.09.2017 Сообщений: 448
	04.10.2017, 19:28 [ТС]
	Байт, Спасибо! 0

@oldnick85 36 / 34 / 10 Регистрация: 15.07.2017 Сообщений: 128
	04.10.2017, 20:39
	Вот интересная (но на практике почти бесполезная) штука: полином Матиясевича. Здесь его статья о формулах для простых чисел. Осторожно, матан! Кстати, обратите внимание на приведённый в этой статье многочлен $https://www.cyberforum.ru/cgi-bin/latex.cgi?x^2+x+41$ 2

@йот 27 / 32 / 14 Регистрация: 08.09.2017 Сообщений: 448
	05.10.2017, 08:56 [ТС]
	oldnick85 Спасибо, это было очень интересно познакомиться с таким многочленом, но меня интересует обычный многочлен от одной или двух переменных... Он не обязан выдавать только простые числа. Пусть выдает и составные. Но простых должно быть больше, чем составных... 0

@йот 27 / 32 / 14 Регистрация: 08.09.2017 Сообщений: 448
	05.10.2017, 16:51 [ТС]
	Shamil1 Тот многочлен хоть и выдает все простые числа, но считать будет долго и много... Это проще массив забить простыми числами... 0

@йот 27 / 32 / 14 Регистрация: 08.09.2017 Сообщений: 448
	05.10.2017, 17:29 [ТС]
	Shamil1, нет, этот многочлен быстро считается... потом его можно записать и так x^2 + x + 41 = x(x + 1) + 41 ... только он один такой... 0

@йот 27 / 32 / 14 Регистрация: 08.09.2017 Сообщений: 448
	05.10.2017, 17:36 [ТС]
	Shamil1, Спасибо, я обязательно посчитаю в каком отношении к составным числам он выдает простые числа. Спасибо!! 0

@йот 27 / 32 / 14 Регистрация: 08.09.2017 Сообщений: 448
	05.10.2017, 18:04 [ТС]
	Shamil1, Спасибо!! 0