Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.92/13: Рейтинг темы: голосов - 13, средняя оценка - 4.92
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
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
12.01.2020, 13:36
Ответы с готовыми решениями:

Проверить, является ли число простым числом из диапазона от 1 до 1000
Разработайте функцию, которая принимает целочисленный параметр и возвра- щает логическое ("bool") значение "true",...

Проект Эйлера, задача №7. Какое число является 10001-ым простым числом?
Доброго времени суток. Я начинающий питонер\питонист\питонщик\ набрасал такой вот кодец. Прошу вашего мнения. Может кому пригодится. За...

Определить является ли число n простым числом
Определить является ли число n простым числом.При помощи цикла

12
 Аватар для samana
2639 / 1567 / 853
Регистрация: 23.02.2019
Сообщений: 3,876
12.01.2020, 14:17
Вроде так, но что-то долговато считает, возможно есть более оптимальные варианты.
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Program
{
 
    public static void Main()
    {
        int count = 0;
        int i;
        for (i = 0; count < 10001; i++)
        {
            if (IsSimple(i)) count++;
        }
 
        Console.WriteLine(i-1); // 104743
    }
 
    public static bool IsSimple(int number)
    {
        if (number < 2) return false;
 
        for (int i = 2; i < number; i++)
        {
            if (number % i == 0) return false;
        }
 
        return true;
    }
 
 
}
0
3566 / 2507 / 1174
Регистрация: 14.08.2016
Сообщений: 8,219
13.01.2020, 16:24
samana, можно значительно ускорить
C#
1
2
3
4
5
6
7
8
9
        static bool IsPrime(int n)
        {
            if (n < 2) return false;
            for (int i = 2; i*i <= n; i++)
            {
                if (n % i == 0) return false;
            }
            return true;
        }
на моем калькуляторе разница примерно в 10 раз
0
 Аватар для samana
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
 Аватар для samana
2639 / 1567 / 853
Регистрация: 23.02.2019
Сообщений: 3,876
13.01.2020, 18:42
Diamante, аж легче стало!
0
Модератор
Эксперт .NET
 Аватар для Элд Хасп
16124 / 11248 / 2888
Регистрация: 21.04.2018
Сообщений: 33,082
Записей в блоге: 2
14.01.2020, 01:55
Цитата Сообщение от Diamante Посмотреть сообщение
а вот кеширование есть
А кеширование здесь при чём?

Добавлено через 5 минут
Цитата Сообщение от samana Посмотреть сообщение
возможно есть более оптимальные варианты.
Кроме сокращения цикла перебора делителей числа (вариант Diamante) можно использовать ещё вариацию решета.
Применение длины в 6 даст ускорение в 3 раза
C#
4
5
6
7
8
9
10
11
12
13
14
15
    public static void Main()
    {
        int count = 3;
        int i;
        for (i = 6; count < 10001; i+=6)
        {
            if (IsSimple(i+1)) count++;
            if (IsSimple(i+5)) count++;
        }
 
        Console.WriteLine(i-1); // 104743
    }
1
3566 / 2507 / 1174
Регистрация: 14.08.2016
Сообщений: 8,219
14.01.2020, 09:47
Цитата Сообщение от Элд Хасп Посмотреть сообщение
А кеширование здесь при чём?
онлайн калькулятором, скорее всего, пользуются много людей и ранее высчитанные значения наверняка кешируются, вот из кеша и выплевывает мгновенно
0
Модератор
Эксперт .NET
 Аватар для Элд Хасп
16124 / 11248 / 2888
Регистрация: 21.04.2018
Сообщений: 33,082
Записей в блоге: 2
14.01.2020, 11:04
Цитата Сообщение от Diamante Посмотреть сообщение
онлайн калькулятором, скорее всего, пользуются много людей и ранее высчитанные значения наверняка кешируются, вот из кеша и выплевывает мгновенно
Теперь понял о чём вы.
0
 Аватар для samana
2639 / 1567 / 853
Регистрация: 23.02.2019
Сообщений: 3,876
14.01.2020, 13:09
Цитата Сообщение от Элд Хасп Посмотреть сообщение
Кроме сокращения цикла перебора делителей числа (вариант Diamante) можно использовать ещё вариацию решета.
Применение длины в 6 даст ускорение в 3 раза
Элд Хасп, Здорово получается! Я не осознаю как это работает, но мне нравится видеть, что всегда есть что улучшить. Кто знает, может когда нибудь в этой ветке появится и мгновенный поиск любого простого числа.
0
44 / 34 / 12
Регистрация: 07.05.2016
Сообщений: 77
14.01.2020, 13:59
Элд Хасп, Ваш цикл выдает 104747, которое не является простым. Не разбираюсь в решете, но полагаю что связано с тем, что на итерации проверяется 2 числа, но выводится именно второе, i-5 решает проблему в данном случае, но не является универсальным.
Как насчет запоминать ранее найденные числа? Тогда можно проверять делимость только на ранее найденные числа. При большом n должно давать существенную прибавку. Вот что получилось
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class FindSimple
    {
        static List<int> a;
        static bool IsSimple(int n)
        {
            if (n < 2) return false;
            for(int i = 0; a[i]*a[i]<=n;i++)
            {
               if (n % a[i] == 0) return false;
            }
            return true;
        }
        public static void Main()
        {
 
            a = new List<int>() { 2, 3, 5 };
            int count = 3;
            int i;
            for (i = 6; count < 10001; i += 6)
            {
                if (IsSimple(i + 1)) { a.Add(i + 1); count++; }
                if (IsSimple(i + 5)) { a.Add(i + 5); count++; }
            }
            Console.WriteLine(i - 5); // 104743
        }
    }
0
Модератор
Эксперт .NET
 Аватар для Элд Хасп
16124 / 11248 / 2888
Регистрация: 21.04.2018
Сообщений: 33,082
Записей в блоге: 2
14.01.2020, 14:36
Цитата Сообщение от samana Посмотреть сообщение
Я не осознаю как это работает
Очень просто.
Выбираем длину решета равную произведению простых чисел - назовём их основаниями.
Простые числа могут появляться только в элементах не кратных основаниям.
То есть мы разбиваем все числа на участки по длине решета, через решето просеиваются только числа не кратные основниям и только эти числа проверяем на простоту.

Для 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
Модератор
Эксперт .NET
 Аватар для Элд Хасп
16124 / 11248 / 2888
Регистрация: 21.04.2018
Сообщений: 33,082
Записей в блоге: 2
14.01.2020, 14:42
Цитата Сообщение от kilidon Посмотреть сообщение
Ваш цикл выдает 104747, которое не является простым.
Я не отлаживал.
i возвращает начало или конец решета.
И на выходе надо проверять превышен count или равен значению.
Если равен то i-1, если превышен i-4

Если не запутался в коэффициентах
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
14.01.2020, 14:42
Помогаю со студенческими работами здесь

Найти k по счету простое число (первым простым числом является 2)
Найти k-ое по счету простое число (первым простым числом является 2).

Определить, является ли число простых чисел, меньших 10000, простым числом
Определить, является ли число простых чисел, меньших 10000, простым числом

Назовем число красивым, если сумма квадратов его цифр является простым числом
Здравствуйте. Помогите с задачкой ((Назовем число красивым, если сумма квадратов его цифр в десятичной системе счисления является...

Из некоторого количества значений натурального N, получаемых от пользователя, указать является ли простым числом число
Для каждого из некоторого количества значений натурального N, получаемых от пользователя, указать является ли простым числом число,...

Для целого числа n проверить утверждение, что если число 2n-1 – 1 является простым, то число 2n * (2n+1 – 1) является совершенным.
Для целого числа n проверить утверждение, что если число 2n-1 – 1 является простым, то число 2n * (2n+1 – 1) является совершенным.


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
13
Ответ Создать тему
Новые блоги и статьи
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 Использованы. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru