CODEWITHSUNDEEP
c++
Nafis
Nafis

Reputation: 19

Why this code gives a run time error in timus 1086 problem?

What is the problem with this code? It's nth prime number generator. It gives me the right answer but it gives a run time error in the second test case in Timus online judge. Can anyone please help me? Here is my code.

#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 && prime[k]==false) {
                c++;
                tk = k;
            }
        }
        cout << tk << endl;
    }
    return 0;
}

Upvotes: 0

Views: 337

Answers (1)

PaulMcKenzie
PaulMcKenzie

Reputation: 35440

One glaring error is this one:

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

When j == MAX, you are writing to prime[MAX], when the highest index is MAX - 1. This is a buffer overrun, thus leading to undefined behavior.

Any loop that has <= as the condition to continue is considered suspect. This erroneous use of <= in a for loop condition is one tell-tale sign that an off-by-one access may occur.

The condition probably should be:

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

As to the safer coding that C++ gives you, using std::array<bool, MAX>, and then the at() function would flag this:

#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

This would have thrown a std::out_of_range exception as soon as j == MAX, stopping your program from going forward with (hopefully) a description of why the exception was raised.

Upvotes: 2

Related Questions