Выход за границы массива в решете Эратосфена

@bershas · Регистрация: 29.09.2024

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

Доброе утро, для решения задачи нужно было сделать массив из простых чисел, я воспользовался решетом Эратосфена, но что-то не углядел. Где-то в строках 12-19 массив temp ломается, только не пойму где, и из-за чего. Помогите пожалуйста, заранее спасибо. (VS пишет, что ошибкой является выход из массива)

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <vector>
using namespace std;
 
vector <int> primenums;
 
void primes()
{
    vector <int> temp(1000000);
    for (int i = 0; i < 1000000; i++)
        temp[i] = i;
    for (int p = 2; p < 1000000; p++)
    {
        if (temp[p] != 0)
        {
            for (int j = p * p; j < 1000000; j += p)
                temp[j] = 0;
        }
    }
    //cout << "PASSED";
    for (int k : temp)
    {
        if (k != 0)
            primenums.push_back(k);
    }
    primenums.resize(primenums.size() + 1);
}
int colorguide(int x)
{
    int l = 0;
    int r = primenums.size() - 1;
    int mid;
    while (l <= r)
    {
        mid = (l + r) / 2;
        if (primenums[mid] == x)
            return 2;
        else if (primenums[mid] > x)
            r = mid - 1;
        else
            l = mid + 1;
    }
    return 1;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    primes();
    int n; cin >> n;
    for (int i = 0; i < n; i++)
    {
        int a; cin >> a;
        cout << colorguide(a) << ' ';
    }
}

@alexu_007 · 14.01.2025, 16:37

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

простое число №11 078 937 имеет значение 199 999 991.

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

rime[200 000 000] = 4 222 234 741

Спасибо. У меня так же.

@Royal_X · 14.01.2025, 17:00

alexu_007, а где в проге ты вводишь длину решета?

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

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

А ну ка, проверьте. 200 000 000 (двухсотмиллионное) простое число. Мой алгоритм (без четных чисел) считает 55 сек. Чужой (но более быстрый) - 19 сек. А как у вас?

у меня вышло меньше 7 сек

Выход за границы массива в решете Эратосфена

@alexu_007 · 14.01.2025, 18:17

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

alexu_007, а где в проге ты вводишь длину решета?

Я не ввожу. Я порядковый номер простого числа умножаю на 22, для чисел размером приблизительно 32 бита (ну или чуть больше) этого достаточно. Для меньших чисел это избыточно, но там и времени вычисления, и памяти нужно меньше.

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

Вот мой алгоритм. Написано на qt, но отличие только в способе ввода-вывода:

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
// вставка пробелов в число 12345 -> 12 345
//---------------------------------------------------------------------------
QString fn_sptI(QString str)
{
    int x = str.length() - 3;
    while(x > 0) {str.insert(x, QString(" ")); x -= 3;}
    return str;
}
 
 
void Widget::press_pbtn_02()
{
    QString str = ui->lineEdit->text();
    str = str.remove(" ");
 
    quint64 cx = str.toULongLong();
    quint64 N = cx * 11;
    quint64 M = sqrt(N) + 1;
 
    quint64 i, j, k;
 
    bitset<0xFFFFFFFF> *bbuf = new bitset<0xFFFFFFFF>;
    bbuf->reset();
 
    // начало отсчёта времени выполнения
    m_time.start();
 
    for(i = 0; i < M; i++)
    {
        if(!bbuf->test(i))
        {
            k = (i*2)+3;
            for(j = k*(i+1)+i; j < N; j+=k) bbuf->set(j,true);
        }
    }
 
    quint64 cy = 1;
 
    // список простых чисел
    for(i = 0; i < N; i++)
     {
        if(!bbuf->test(i))
        {
            cy++;
            if(cy == cx) break;
        }
     }
 
    // конец отсчёта времени выполнения
    qint64 msecs = m_time.elapsed();
    QTime time(0,0,0,0);
 
    ui->tableWidget->item(0, 2)->setText(fn_sptI(QString::number(N)));
    ui->tableWidget->item(1, 2)->setText(fn_sptI(QString::number(cx)));
    ui->tableWidget->item(2, 2)->setText(fn_sptI(QString::number((i*2) + 3)));
    ui->tableWidget->item(3, 2)->setText(time.addMSecs(msecs).toString("hh:mm:ss.zzz"));
}

Вот алгоритм неизвестного мне чела, шустрее моего раза в три. Возможно я его скопировал на этом же сайте:

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
constexpr int64_t L1_CPU_CACHE = 32768; // 32 KiB = 32768 B
 
std::vector<int64_t> sieveOfEratosthenes(int64_t x)
{
    std::vector<int64_t> r;
    r.push_back(2);
    int64_t w = static_cast<int64_t>(std::sqrt(x));
    int64_t a = std::max(w, L1_CPU_CACHE);
    int64_t i = 3, n = i, s = n;
    std::vector<char> v(a);
    std::vector<char> q(w + 1, true);
    std::vector<int64_t> p;
    std::vector<int64_t> m;
 
    for (int64_t l = 0; l <= x; l += a)
    {
        std::fill(v.begin(), v.end(), true);
        int64_t h = l + a - 1;
        h = std::min(h, x);
        for (; i * i <= h; i += 2)
            if (q[i])
                for (int64_t j = i * i; j <= w; j += i)
                    q[j] = false;
 
        for (; s * s <= h; s += 2)
        {
            if (q[s])
            {
                p.push_back(s);
                m.push_back(s * s - l);
            }
        }
 
        for (std::size_t i = 0; i < p.size(); i++)
        {
            int64_t j = m[i];
            for (int64_t k = p[i] * 2; j < a; j += k)
            v[j] = false;
            m[i] = j - a;
        }
 
        for (; n <= h; n += 2)
            if (v[n - l])
                r.push_back(n);
    }
    return r;
}
 
 
 
void Widget::press_pbtn_03()
{
    QString str = ui->lineEdit->text();
    str.remove(" ");
 
    quint64 cx = str.toULongLong();
    quint64 N = cx * 22;
 
    // начало отсчёта времени выполнения
    m_time.start();
 
    std::vector<int64_t> s = sieveOfEratosthenes(N);
 
    // конец отсчёта времени выполнения
    qint64 msecs = m_time.elapsed();
    QTime time(0,0,0,0);
 
    ui->tableWidget->item(0, 3)->setText(fn_sptI(QString::number(N)));
    ui->tableWidget->item(1, 3)->setText(fn_sptI(QString::number(cx)));
    ui->tableWidget->item(2, 3)->setText(fn_sptI(QString::number(s[cx-1])));
    ui->tableWidget->item(3, 3)->setText(time.addMSecs(msecs).toString("hh:mm:ss.zzz"));
}

@Royal_X · 14.01.2025, 18:25

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

Вот алгоритм неизвестного мне чела, шустрее моего раза в три. Возможно я его скопировал на этом же сайте:

Это я тот неизвестный чел

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

@alexu_007 · 14.01.2025, 18:38

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

Это я тот неизвестный чел .

Да? Ну, мир тесен.

Я на всякий случай сохранил его у себя, как более быстрый. Вдруг для решения какой-либо задачи понадобится длинная последовательность простых чисел.

@Royal_X · 14.01.2025, 21:24

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

Я на всякий случай сохранил его у себя, как более быстрый.

Правильно сделал. Если честно, не я автор данного алгоритма. Я этот алгоритм тоже где-то увидел еще давно. Это общеизвестный алгоритм сегментированного решета. Помогает экономить память и по максимуму использовать быстрейший кеш проца.

Добавлено через 2 часа 28 минут

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

Я не ввожу.

для чисел $https://www.cyberforum.ru/cgi-bin/latex.cgi?\geq 18$ я использую такие нижние и верхние пределы

Нижний предел
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\lfloor n (\log (n)+\log (\log (n))-1)\rfloor$

Верхний предел

$https://www.cyberforum.ru/cgi-bin/latex.cgi?\lfloor n (\log (n)+\log (\log (n)))\rfloor$

Соответственно, можно уверенно взять верхний предел в качестве лимита решета для нахождения n-го простого числа

Новые блоги и статьи Все статьи Все блоги /
Кредитный калькулятор Maks 05.08.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .	У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35". kumehtar 04.08.2026 С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .	Как ИИ начал спорить и врать (возможно почуяв опасность для себя от индустрии - уход от электроники). Hrethgir 04.08.2026 Недельный диалог, на фоне событий с НПЗ. Да, из спирта можно получать бензин, и это не сложно. Но потом в схеме я решил избавиться от насоса, при этом полностью сделав контроль подачи спирта в. . .	Термопринтер QR701 Argus19 03.08.2026 Термопринтер QR701 Купил два термопринтера QR701. На сэлф-тесте написано: Language: PC936 (GB18030). Что означает, что принтеры могут печатать только латиницу и китайские иероглифы. Так же. . .
Создание формы заимствованного документа Maks 03.08.2026 Задача: Необходимо создать собственную форму заимствованного документа. На форме должен быть реквизит "Покупатель", а также табличная часть со следующими реквизитами: - Расчетный счет покупателя. . .	Задача предоставления скидок покупателям Maks 03.08.2026 Задача: В документе "Продажи" необходимо реализовать функционал предоставления скидок покупателям. Скидка должна автоматически рассчитываться и подставляться в соответствующее поле при выборе. . .	Почему SEO не начинается с ключевых слов: что проверить до написания текстов Neotwalker 01.08.2026 Когда владельцу сайта предлагают заняться SEO, первым шагом часто становится сбор запросов и написание текстов. Логика кажется понятной: 1. Находим ключевые слова. 2. Добавляем их на. . .	Знание — сила: Доктрина интенциональности знаний, углубление в формулу Hrethgir 01.08.2026 https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11957&stc=1&d=1785567302 Знаменитый афоризм Фрэнсиса Бэкона «Знание — сила» (Scientia potentia est) в массовой культуре принято понимать. . .

Опции темы