Member 13277493 Ответов: 1

Почему переменная размера в случае больших значений не верна?

Мне нужно найти n-е простое число, в этом случае я использую алгоритм Эратосфена, но у меня есть некоторое непонимание переменной размера, почему она дает ошибку. Простые числа растут по некоторому шаблону, начиная с 5, я использовал этот шаблон для оценки размера.

<pre>#include <iostream>
#include <vector>
#include <cmath>

long long getNthPrime(int n)
{
    long long size=n+8*(n+2);

    std::vector<char>is_prime(size+1, 't');
    is_prime[0]=is_prime[1]='f';
    int count=0;
    for(long long i=2; i<=size; i++)
    {
        if(is_prime[i]=='t')
        {
            count++;
            if(count==n)
            {
                return i;
            }
            for(long long j=i*i; j<=size; j+=i)
            {
                is_prime[j]='f';
            }
        }
    }

}

int main() {
    int k;
    int n;
    std::cin >> k;
    int arr[k];

    for (int i = 0; i < k; i++) {
        std::cin >> n;
        arr[i] = n;
    }
    for (int i = 0; i < k; i++) {
        std::cout << getNthPrime(arr[i]) << std::endl;
    }

}


Что я уже пробовал:

Я попытался отладить код.

Patrice T

и вы планируете сообщить об ошибке сообщение ?

Member 13277493

нет, мне просто нужно напечатать n-е простое число для каждого входного сигнала

Richard MacCutchan

Какая ошибка? Пожалуйста, не ждите, что люди догадаются, что вы видите на экране.

Rick York

При поиске простых чисел стандартная тактика состоит в том, чтобы проверить 2, затем 3, а затем пропустить 2 (а не 1!). Это происходит потому, что после проверки на множители 2 нет необходимости проверять любые другие четные числа. Там все еще будет несколько избыточных проверок, но намного меньше, чем если бы вы также проверили эвены.

1 Ответов

Рейтинг:
11

OriginalGriff

Компиляция не означает, что ваш код верен! :смеяться:
Подумайте о процессе разработки как о написании электронного письма: успешная компиляция означает, что вы написали письмо на правильном языке - например, на английском, а не на немецком, - а не то, что письмо содержало сообщение, которое вы хотели отправить.

Итак, теперь вы входите во вторую стадию разработки (на самом деле это четвертая или пятая, но вы перейдете к более ранним стадиям позже): тестирование и отладка.

Начните с рассмотрения того, что он делает, и как это отличается от того, что вы хотели. Это важно, потому что это дает вам информацию о том, почему он это делает. Например, если программа предназначена для того, чтобы позволить пользователю ввести число, а затем удвоить его и напечатать ответ, то если бы ввод / вывод был таким:

Input   Expected output    Actual output
  1            2                 1
  2            4                 4
  3            6                 9
  4            8                16
Тогда совершенно очевидно, что проблема заключается в бите, который удваивает его - он не прибавляет себя к себе или умножает его на 2, он умножает его на себя и возвращает квадрат входного сигнала.
Таким образом, вы можете посмотреть на код, и очевидно, что он находится где-то здесь:
int Double(int value)
   {
   return value * value;
   }

Как только у вас появится идея, что может пойти не так, начните использовать отладчик, чтобы выяснить, почему. Поместите точку останова в первую строку метода и запустите приложение. Когда он достигнет точки останова, отладчик остановится и передаст управление вам. Теперь вы можете запускать свой код построчно (так называемый "одноступенчатый") и просматривать (или даже изменять) содержимое переменных по мере необходимости (черт возьми, вы даже можете изменить код и повторить попытку, если вам это нужно).
Подумайте о том, что должна делать каждая строка кода перед ее выполнением, и сравните это с тем, что она действительно делала, когда вы использовали кнопку "Step over" для выполнения каждой строки по очереди. Он сделал то, что вы ожидали? Если да, то переходите к следующей строке.
Если нет, то почему? Чем это отличается?
Надеюсь, это поможет вам определить, в какой части этого кода есть проблема и в чем она заключается.
Это навык, и его стоит развивать, поскольку он помогает вам как в реальном мире, так и в развитии. И, как и все навыки, он только улучшается при использовании!

Member 13277493

спасибо, я попробую именно так

OriginalGriff

Всегда пожалуйста!