Поиск k-го просто числа

@Cookien · Регистрация: 27.08.2023

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

Нужно оптимизировать код, чтобы выполнялся не больше 1 сек

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
 
using namespace std;
 
int main()
{
    int k, c, j, l = 0;
    cin >> k;
    for (int h=2; k != l; h++){
        c = 0;
        for (int i=1; h >= i; i++){
            if (h%i == 0 ){
                c += 1;
            }
        }
        if (c == 2){
            j = h;
            l ++;
        }
    }
    cout << j;
}

Это код для поиска k-го просто числа
При k = 100000, очень долго считает, как оптимизировать?
c - кол-во делителей числа
i - делитель
h - делимое
j - k-е число
l - Кол-во найденных чисел
k меньше 100000

Добавлено через 1 минуту

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

Это код для поиска k-го просто числа

Простого*

@lemegeton · 19.09.2023, 14:26

Не уверен, что существует математический способ найти к-тое простое число за единицу или за 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
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <vector>
#include <limits>
#include <cmath>
 
int main() {
    std::vector<std::size_t> primes {2, 3};
 
    std::size_t i;
    std::cin >> i;
    std::cout << i << std::endl;
 
    if (i < primes.size()) {
        std::cout << primes[i] << std::endl;
        return 0;
    }
 
    auto isPrime = [&primes](std::size_t n)->bool {
        for (std::size_t i = 1, last = primes.size(), root = std::sqrt(n); i < last && primes[i] <= root; ++i) {
            if (n % primes[i] == 0) {
                return false;
            }
        }
        return true;
    };
 
    for (auto j = primes[primes.size() - 1], max = std::numeric_limits<std::size_t>::max();
        primes.size() <= i && j < max; ++++j) {
        if (isPrime(j)) {
            primes.push_back(j);
        }
    }
 
    std::cout << primes[i] << std::endl;
 
    return 0;
}

@ram876 · 19.09.2023, 14:39

Найти K-е по счёту простое число

@alexu_007 · 20.09.2023, 08:53

Вот быстрый (с моей точки зрения) способ нахождения n-ного простого числа, с помощью ускоренного (без чётных чисел) решета Эрастофена. Правда написано на Qt, но там кутешного только ввод, вывод и замер времени выполнения, сам код чистый си. Максимальное значение n - 100 000 000

C++ (Qt)
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
// поиск n-ного простого числа
void Widget::press_pbtn_01()
{
    ui->lineEdit_03->clear();
    ui->lineEdit_04->clear();
 
    QString str = ui->lineEdit_01->text();
    str = str.remove(" ");
 
    quint64 n  = str.toULongLong();
    if(n == 0 || n > 100000000) return;
 
    quint64 razm = n * 11;
    quint64 m = sqrt(razm) + 1;
 
    QTime m_time;
 
 
    // с битсетом
    bitset<0x9FFFFFFF> *bbuf = new bitset<0x9FFFFFFF>;
    bbuf->reset();
 
    quint64 k = 0;
 
    ui->lineEdit_04->setText("Please, wait...");
    QApplication::processEvents();
 
 
    // начало отсчёта времени
    quint64 t_begin = m_time.elapsed();
 
    // решето
    for(quint64 i = 0; i < m; i++)
    {
        if(!bbuf->test(i))
        {
            k = (i*2)+3;
            for(quint64 j = k*(i+1)+i; j < razm; j+=k)
            {
                bbuf->set(j,true);
            }
        }
    }
 
    // подсчет результата
    quint64 cy = 1;
 
    if(n == 1) k = 2;
    else
    {
        for(quint64 i = 0; i < razm-1; i++)
        {
            if(!bbuf->test(i))
            {
                cy++;
                if(cy == n)
                {
                    k = i*2 + 3;
                    break;
                }
            }
        }
    }
 
 
    // конец отсчёта времени
    qint64 msecs = m_time.elapsed() - t_begin;
    QTime time(0,0,0,0);
 
    ui->lineEdit_03->setText(fn_SpsToInt(QString::number(k)));
    ui->lineEdit_04->setText(time.addMSecs(msecs).toString("hh:mm:ss.zzz"));
 
    delete bbuf;
}

Verevkin · 20.09.2023, 09:36

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

Вот быстрый (с моей точки зрения) способ нахождения n-ного простого числа, с помощью ускоренного (без чётных чисел) решета Эрастофена.

Согласен. Меня результат устроил.

@lemegeton · 20.09.2023, 16:27

0x9FFFFFFF бит это где-то... 320 мегабайт?

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

C++
1
2
quint64 razm = n * 11;
    quint64 m = sqrt(razm) + 1;

Не пойму, откуда такая оценка?

@alexu_007 · 20.09.2023, 20:27

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

Не пойму, откуда такая оценка?

Оценка получена опытным путём. Миллионное простое число равно 15 485 863, т.е. более чем в 15 раз больше порядкового номера. Десятимиллионное - 179 424 673 - в 18 раз. Стомиллионное - 2 038 074 743 - более чем в 20 раз. Поэтому для вычисления требуемой длины решета Эрастофена для поиска максимального стомиллионного числа порядковый номер (100 млн.) нужно умножить на 21 - получится с небольшим запасом. Но так как решето Эрастофена модифицированное, и не учитывает чётные числа, длину нужно поделить на 2, ближайшее целое число - 11.

Для меньших порядковых номеров такая длина избыточна, но т.к. и время вычисления существенно падает - с этим можно смириться.

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@ram876 759 / 456 / 213 Регистрация: 19.12.2016 Сообщений: 1,815
	19.09.2023, 14:39
	Найти K-е по счёту простое число 0

Опции темы

Поиск k-го просто числа

Решение