простой путь с использованием BFS

Question

Я решал вопрос простой путь Я использую bfs, чтобы решить этот вопрос

Вот мое решение https://ideone.com/GMOyWX

, когда я использую этофункция проверки на простое число, я получаю правильный ответ как 6

bool isprime(int number) {
    for (int i = 2; i < sqrt(number); i++) {
        if (number % i == 0 && i != number) return false;
    }
    return true;
}

Но когда я использую сита, я получаю неправильный ответ как 5

void sieves(int n) {
    isPrime[0] = false;
    isPrime[1] = false;
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            for (int j = 2*i; j <= n; j+=i) {

                isPrime[j] = false;

            }
        }
    }
}

Может кто-нибудь сказать мне, что не такс ситами?

Answer 1

Я думаю, что вы решите, что реализация правильная, поэтому вы делаете что-то не так в любом другом месте.из вашего кода я вижу, что вы вызываете свою функцию сита для каждого теста.Это не должно быть необходимым.В постановке задачи четко указано, что ввод будет состоять из четырех цифр, состоящих из двух чисел, поэтому в максимальном случае 100000 должно быть достаточным пределом для создания вектора проверки, является ли каждое число простым или нет.Так что просто позвоните один раз на ваше сито с 100000 один раз.Простые числа являются фиксированными числами.