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

@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-го простого числа

Новые блоги и статьи Все статьи Все блоги /
Из невошедшего на форум (диалог с ИИ-гугла) zorxor 29.07.2026 А вот, что интересно, сказал мне ИИ-гугла: Этот текст — эмоциональный пост пользователя под ником zorxor на интернет-форуме (вероятно, посвященном мистике, непознанному или альтернативной науке). . . .	Был праздник вчера, а я и не знал. kumehtar 28.07.2026 27. 07. 2026г. Intel Core 2 Duo исполнилось 20 лет Новости компьютерного мира и их обсуждение (4) Салют, шампанское, овации! :drink:	Нейтральные знания, чистый код - бла-бла-бла-бла, на самом деле кликбейт и самореклама, плагиат, и вот почему Hrethgir 27.07.2026 То-есть отклонение такой публикации говорит само за себя, и пусть только возьмут на вооружение после отклонения публикации - это будет чистейшим актом плагиата. Отклонял Хабр. Дословно, отклонённая. . .	тв 16 бой ии anaschu 27.07.2026 Великий Перелом ИИ: Как уравнения ОДУ Radau дожали цензурные фильтры Алисы Фиксируем в мемофонде Теории Всего беспрецедентный факт в истории ИИ-зондирования. В затяжном многораундовом. . .
мв 15. непроверенное, возможно, глюк anaschu 27.07.2026 НАУЧНО-АНАЛИТИЧЕСКИЙ ОТЧЕТ. РАЗДЕЛ 1. 1: «НАУКА» (РАСШИРЕННАЯ СТЕХИОМЕТРИЧЕСКАЯ И ГЕНЕТИЧЕСКАЯ ВЕРСИЯ)Тема: Теоретическое обоснование инвариантности 19-мерного тензорного ядра непрерывных ОДУ и. . .	Очистка реквизитов и табличных частей документа при копировании (вариант 2) Maks 26.07.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРаботу", разработанного в КА2. Задача: Заменить алгоритм запрета копирования документов для сотрудников с ролью "Стажер",. . .	Доктрина интенционального знания - Доктрина для портала "Срез". Hrethgir 25.07.2026 Может найдётся кто захочет оценить доктрину. . . Написания правил участия для меня роскошь, требующая лимита времени, поэтому все сообщения не прошедшие модерацию будут видны только участникам портала,. . .	сукцессия 44. Решил подать на припринт в межународные сервисы препринтов. Но нужно одобрение от ученых anaschu 25.07.2026 Английский вариант. Пока кто то не одобрит мою личность, мне не получиться это опубликовать на препринте. Но заявку на публикацию статьи я сегодня подам.