Код не проходит тесты
Задача довольно простая, отсюда http://acm.timus.ru/problem.aspx?space=1&num=1086
Решил, просто посчитав решето эратосфена до числа, где порядковый номер последнего простого числа 15 000. На моем компе все работает (смотри скриншот), а на сайте заваливает даже 1 тест. На форуме сборника задач не отвечают. Что делать, не знаю... Может, подкинете варианты входных данных, на которых я могу словить ошибку?
Скриншот:
Код:
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. Решается в свободное время, не является учебным заданием.
Обновление:
В попытках найти ошибку я решил взять эталонный набор простых чисел и сравнить их с моими:
Слева эталон, справа мое. Как исправить ошибку?
Обновление_2:
Смещение на 1 появилось из-за предела возможного числа unsigned int. Странно другое. Исправив так, что все сходится с эталонными числами, я все равно не прохожу тесты. Wrong answer и все. :*(
Кстати, в алгоритме допущена была ошибка: в первом цикле не i<=LIMIT
, а i*i<=LIMIT
, поскольку проходить значения выше чем sqrt(LIMIT)
не имеет смысла. Если это исправить, то unsigned int хватает.