Что не так в решении задачи?

Question

[dmitrii000]

Вот условие

Вот решение, но вместо 104743 оно выводит 30001, что не так?

#include <iostream>
#include <vector>

int main() {
    std::vector<int> primeNums(10001);

    int n = 0;
    int index = 0;

    while (primeNums[primeNums.size() - 1] == 0) {
        ++n;
        if ((n * n) % 24 == 1) {
            primeNums[index] = n;
            ++index;
        }
    }

    std::cout << primeNums[primeNums.size() - 1];

    return 0;
}

Answer 1

[Алексей Уколов]

(n * n) % 24 == 1

Что-то я не видал такого метода определения прайма. Числа 2 и 3 он не считает праймами, наверняка, и дальше есть расхождения.

P.S. Зачем тут вообще массив...

Comments

[Wataru]

Массив по-любому нужен. Или вы проверяете число на простоту через проверку на делимость на все предыдущие простые числа, или вы делаете решето Эратосфена.

[Алексей Уколов]

Wataru, ну в данной-то реализации создаётся сразу массив из 10001 нуля и в него последовательно складываются числа, которые алгоритм посчитал простыми, а потом берётся последнее из них. В этой конкретной реализации массив просто ест память и его можно заменить одним intом.

[Wataru]

Алексей Уколов, Ну, если стоит задача вывести какой-то мусор, то - да, массив не нужен.

[Алексей Уколов]

Wataru, мои слова относятся к конкретному приведённому коду. Автор же, когда его писал, думал, что алгоритм у него рабочий. И для этого алгоритма массив не нужен. То, что алгоритм неправильный и в правильном используется массив — это следующий шаг.

[Wataru]

Алексей Уколов, Автор, очевидно, где-то почерпнул вдохновление с правильного решения с массивом. Но не смог воспроизвести его полностью.

[Алексей Уколов]

Wataru, ну да, я именно на это и пытался указать, просто не очень удачно сформулировал.

Answer 2

[Wataru]

Проверка числа на простоту не так.
Во-первых, начинайте c n=2, ибо 1 у вас иначе простым числом будет.

Во-вторых, в вашем случае надо проверять, что n не делится на все предыдущие простые числа. Вложенным циклом. Ну, или решето эратосфена реализуйте.

Answer 3

[WAR_VIK]

Вот так можно написать:

#include <iostream>

bool is_prime(int n) {
    for (int i = 2; i <= n / 2; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

int main()
{
    int count = 10001, prime = 0, res = 0;
    for(int i = 2; i < 1000000; ++i) {
        if(is_prime(i)) ++prime;
        if(count == prime) {
            res = i;
            break;
        }
    }
    std::cout << res;
    return 0;
}