Блог

Главная - Вопросы по программированию - Почему этот код выдает ошибку во время выполнения в задаче timus 1086?

Почему этот код выдает ошибку во время выполнения в задаче timus 1086?

#c

#c

Вопрос:

В чем проблема с этим кодом? Это генератор n-го простого числа. Это дает мне правильный ответ, но выдает ошибку во время выполнения во втором тестовом примере в Timus online judge. Кто-нибудь может мне помочь? Вот мой код.

 #include <iostream>
#include <cmath>


using namespace std;

#define MAX 16000
bool prime[MAX];

void sieve() {
    prime[0]=prime[1]=true;
    int r=sqrt(MAX);
    for(int i = 3; i <= r; i  ) {
        for(int j = i*i; j <= MAX; j =(2*i)) {
            prime[j]=true;
        }
    }
}

int main()
{
    int t, n;
    sieve();
    cin >> t;
    for(int i = 0; i < t; i  ) {
        cin >> n;
        int c = 1, k, tk=2;
        for(k = 3; c < n; k =2) {
            if(k%2!=0 amp;amp; prime[k]==false) {
                c  ;
                tk = k;
            }
        }
        cout << tk << endl;
    }
    return 0;
}

Комментарии:

1. for(int j = i*i; j <= MAX; j =(2*i)) { prime[j]=true; — Что произойдет, если j == MAX ? Это одна из причин, по которой нельзя научиться писать безопасный код на C на сайтах онлайн-соревнований. Использование std::vector и vector::at() выявило бы эту проблему.

2. Каково точное написание вопроса? В частности, максимальные значения n , t ?

3. @Damien, максимальные значения n, t равны 15000.

4. Если максимальное значение n равно 15000, то максимальное простое число будет намного выше 16000

5. О, я допускаю эту ошибку. Спасибо

Ответ №1:

Одна из вопиющих ошибок заключается в следующем:

 #define MAX 16000
bool prime[MAX];
// ...
for(int j = i*i; j <= MAX; j =(2*i)) {
   prime[j]=true; // <-- Buffer overrun when j == MAX

Когда j == MAX вы пишете в prime[MAX] , когда самый высокий индекс MAX - 1 . Это переполнение буфера, что приводит к неопределенному поведению.

Любой цикл, имеющий <= в качестве условия продолжение, считается подозрительным. Это ошибочное использование <= условия in a for loop является одним из контрольных признаков того, что может произойти поочередный доступ.

Условие, вероятно, должно быть:

 for(int j = i*i; j < MAX; j =(2*i)) {
   prime[j]=true;

Что касается более безопасного кодирования, которое дает вам C , используя std::array<bool, MAX> , а затем at() функция будет отмечать это:

 #include <array>

#define MAX 16000
std::array<bool, MAX> prime;
// ...
for(int j = i*i; j <= MAX; j =(2*i)) {
   prime.at(j) = true; // <-- std::out_of_range exception thrown

Это std::out_of_range сразу же вызвало бы исключение j == MAX , остановив дальнейшую работу вашей программы с (надеюсь) описанием того, почему было вызвано исключение.