Код не проходит тесты

Рейтинг: 1Ответов: 2Опубликовано: 16.11.2014

Задача довольно простая, отсюда http://acm.timus.ru/problem.aspx?space=1&num=1086

Решил, просто посчитав решето эратосфена до числа, где порядковый номер последнего простого числа 15 000. На моем компе все работает (смотри скриншот), а на сайте заваливает даже 1 тест. На форуме сборника задач не отвечают. Что делать, не знаю... Может, подкинете варианты входных данных, на которых я могу словить ошибку?

Скриншот:

alt text

Код:

bool *eratosthen(){
    bool *arr = new bool[LIMIT+1];

    arr[1] = 1;
    for(unsigned int i=2; i<=LIMIT; i++){
        if(arr[i] == false){
            for(unsigned int k = i*i; k<=LIMIT; k+=i)
                arr[k] = 1;
        }
    }


    return arr;
}
unsigned int searchPrimeNumbers(bool *arr, int num){
    unsigned int count = 0, curr = 0;

    while(++curr <= LIMIT){
        if(arr[curr] == 0){
            count++;
        }
        if(count == num){
            return curr;            
        }
    }
}
int main()
{
    // FILE *file = freopen("input.txt", "rt", stdin); //при сдаче эта строка закоменчена
    bool *result = eratosthen();
        int n;
    cin >> n; //сколько всего чисел
    while(cin >> n){
        if(n == 0){ // для нуля выводим нуль
            cout << "0" << "\n";
            continue;
        }
        cout << searchPrimeNumbers(result, n) << "\n";
    }

    return 0;
}

P.S. Решается в свободное время, не является учебным заданием.

Обновление:

В попытках найти ошибку я решил взять эталонный набор простых чисел и сравнить их с моими:

alt text

Слева эталон, справа мое. Как исправить ошибку?

Обновление_2:

Смещение на 1 появилось из-за предела возможного числа unsigned int. Странно другое. Исправив так, что все сходится с эталонными числами, я все равно не прохожу тесты. Wrong answer и все. :*(

Кстати, в алгоритме допущена была ошибка: в первом цикле не i<=LIMIT, а i*i<=LIMIT, поскольку проходить значения выше чем sqrt(LIMIT) не имеет смысла. Если это исправить, то unsigned int хватает.

Ответы

Ответов пока нет.