|
0 / 0 / 0
Регистрация: 06.11.2019
Сообщений: 10
|
|
Какое число является 10001-ым простым числом?12.01.2020, 13:36. Показов 2819. Ответов 12
Метки нет (Все метки)
Выписав первые шесть простых чисел, получим 2, 3, 5, 7, 11 и 13. Очевидно, что 6-ое простое число - 13.
Какое число является 10001-ым простым числом? Долго ломаю голову, но не могу додуматься... Подскажете?
0
|
|
| 12.01.2020, 13:36 | |
|
Ответы с готовыми решениями:
12
Проверить, является ли число простым числом из диапазона от 1 до 1000 Проект Эйлера, задача №7. Какое число является 10001-ым простым числом?
|
|
2639 / 1567 / 853
Регистрация: 23.02.2019
Сообщений: 3,876
|
||||||
| 12.01.2020, 14:17 | ||||||
|
Вроде так, но что-то долговато считает, возможно есть более оптимальные варианты.
0
|
||||||
|
3566 / 2507 / 1174
Регистрация: 14.08.2016
Сообщений: 8,219
|
||||||
| 13.01.2020, 16:24 | ||||||
|
samana, можно значительно ускорить
0
|
||||||
|
2639 / 1567 / 853
Регистрация: 23.02.2019
Сообщений: 3,876
|
|
| 13.01.2020, 17:43 | |
|
Diamante, Да, ваш вариант значительно быстрее работает. Где-то в сети пробовал на онлайн калькуляторе высчитать, так там вообще мгновенно появляется результат, видимо какая-то умная формула используется.
0
|
|
|
3566 / 2507 / 1174
Регистрация: 14.08.2016
Сообщений: 8,219
|
|
| 13.01.2020, 17:52 | |
|
samana, нет таких формул, а вот кеширование есть
1
|
|
|
2639 / 1567 / 853
Регистрация: 23.02.2019
Сообщений: 3,876
|
|
| 13.01.2020, 18:42 | |
|
Diamante, аж легче стало!
0
|
|
|
Модератор
|
||||||||
| 14.01.2020, 01:55 | ||||||||
|
Добавлено через 5 минут Применение длины в 6 даст ускорение в 3 раза
1
|
||||||||
|
3566 / 2507 / 1174
Регистрация: 14.08.2016
Сообщений: 8,219
|
||
| 14.01.2020, 09:47 | ||
|
0
|
||
|
2639 / 1567 / 853
Регистрация: 23.02.2019
Сообщений: 3,876
|
||
| 14.01.2020, 13:09 | ||
|
0
|
||
|
44 / 34 / 12
Регистрация: 07.05.2016
Сообщений: 77
|
||||||
| 14.01.2020, 13:59 | ||||||
|
Элд Хасп, Ваш цикл выдает 104747, которое не является простым. Не разбираюсь в решете, но полагаю что связано с тем, что на итерации проверяется 2 числа, но выводится именно второе, i-5 решает проблему в данном случае, но не является универсальным.
Как насчет запоминать ранее найденные числа? Тогда можно проверять делимость только на ранее найденные числа. При большом n должно давать существенную прибавку. Вот что получилось
0
|
||||||
|
Модератор
|
||
| 14.01.2020, 14:36 | ||
|
Выбираем длину решета равную произведению простых чисел - назовём их основаниями. Простые числа могут появляться только в элементах не кратных основаниям. То есть мы разбиваем все числа на участки по длине решета, через решето просеиваются только числа не кратные основниям и только эти числа проверяем на простоту. Для 2 и 3 получаем длину 6. 6k+0 - проверять не надо (кратно 6) 6k+1 - проверять надо 6k+2 - проверять не надо (кратно 2) 6k+3 - проверять не надо (кратно 3) 6k+4 - проверять не надо (кратно 2) 6k+5 - проверять надо Следовательно добавив всего одну проверку в цикле, мы сможем делать цикл шагом шесть - ускорение в 3 раза Реально чуть с отклонением от трёх - в какую сторону зависит от компилятора и процессора. К сожалению такая эффективность только для этих оснований. Взяв 2,3 5 - получаем длину 30. Но проверок нужно сделать, по моему, 8. То есть даже в 4 раза ускорения не получится. Добавлено через 3 минуты Для полного поиска всех простых чисел в заданном диапазоне самый эффективный алгоритм Решето Эратосфена Добавлено через 2 минуты Верхний диапазон для N-го простого числа примерно равен N/ln(N). Можно взять массив с небольшим запасом 1,1..1,2*N/ln(N) и просеять его целиком через Решето Эратосфена. Это будет самый быстрый алгоритм для данной задачи.
1
|
||
|
Модератор
|
||
| 14.01.2020, 14:42 | ||
|
i возвращает начало или конец решета. И на выходе надо проверять превышен count или равен значению. Если равен то i-1, если превышен i-4 Если не запутался в коэффициентах
0
|
||
| 14.01.2020, 14:42 | |
|
Помогаю со студенческими работами здесь
13
Определить, является ли число простых чисел, меньших 10000, простым числом Назовем число красивым, если сумма квадратов его цифр является простым числом
Для целого числа n проверить утверждение, что если число 2n-1 – 1 является простым, то число 2n * (2n+1 – 1) является совершенным. Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств
8Observer8 07.02.2026
Содержание блога
Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .
|
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
Использованы. . .
|