2

Нужно узнать, является ли число простым. Попробовал взять первое решение отсюда (Является ли число простым) и запихнуть его в свой код, но тогда получается, что 1 - простое, 4 - простое, а это не так. Пожалуйста, не нужно сложных алгоритмов, которые якобы увеличивают производительность, не до этого мне сейчас. Я хочу понять, почему не работает мой код (пропускает 4ку, например). А т.к. код брал у того автора, интересно, почему его ответ в плюсе.

#include <stdio.h>

int main() {
    bool simple = true;
    int n;

    scanf_s("%d", &n);
    for (int i = 2; i < sqrt(n); i++) {
        if (n == 1) simple == false;
        if (n % i == 0) {
        simple = false;
        return 0;
        }
    }
    if (simple)
        printf("YES");
    else
        printf("NO");
    return 0;
}
1
  • Цитирую комментарий с того же ответа: должно быть i<=sqrt(n), иначе квадрат простого числа тоже будет простым.
    – Shadasviar
    21 дек 2016 в 11:45

2 ответа 2

5

Ну, давайте разберем ваш код...

#include <stdio.h>
int main() {
    bool simple = true;
    int n;
    scanf_s("%d", &n);

Пока все логично.

    for (int i = 2; i < sqrt(n); i++) {

Итак, если n - квадрат простого числа (кстати, где #include <math.h>?), то это простое число не проверяется (оно же не меньше, а равно корню квадратному). Например, для 4 этот цикл выполнен не будет, т.к. 2 не меньше 2.

        if (n == 1) simple == false;

Если n - единица, сравниваем simple и false. Зачем - непонятно.

        if (n % i == 0) {
            simple = false;
            return 0;
        }

Если n делится на i, присваиваем simple значение false и завершаем программу.

    }

Цикл закончен. simple ни разу не менялось (там, где менялось - тут же программа завершается), так что оно равно true. Значит, код

    if (simple)
        printf("YES");
    else
        printf("NO");
    return 0;
}

Выводит просто YES, даже без перевода каретки. Код с выводом NO никогда не выполняется.

Код разобран? Почему не работает - вопросов больше нет?

3
  • Я понял! Спасибо огромное за детальный разбор, все по полочкам разложил себе, теперь можно задаваться вопросом, как сделать это быстрее :) 21 дек 2016 в 12:05
  • Кстати, в VS 15 sqrt работал без подключения. Но когда залил на сайт для проверки - ошибка компиляции. Обидно. 21 дек 2016 в 12:07
  • Ну, если ответ устраивает - помечайте как принятый :) А быстрее - можно начать с проверки только нечетных. или тех, которые имеют вид 6n+1 или 6n-1 (2 и 3 проверять отдельно). Условие цикла я вы переписал как i*i <= n. Еще быстрее - по крайней мере хотя бы какой-то кусок таблицы простых чисел если не на ходу просчитывать, то просто прошить в программе...
    – Harry
    21 дек 2016 в 12:27
3

Раз у вас цикл начинается с 2

for (int i = 2; i < sqrt(n); i++) {

то по крайней мере 1 сразу же следует исключить из простых чисел. Также не имеет смысла проверять для четных чисел, являются ли они простыми или нет. Поэтому в цикле достаточно рассматривать в качестве делителей нечетные числа.

В этом цикле

for (int i = 2; i < sqrt(n); i++) {
    if (n == 1) simple == false;
    if (n % i == 0) {
    simple = false;
    return 0;
    }
}

некорректное условие цикла i < sqrt(n). Должно быть по крайней мере i <= sqrt(n). В начале цикла каждый раз происходит лишняя проверка переменной n на равенство 1. И кроме того происходит непонятный выход из программы.

Используйте следующий подход

int n;

scanf_s("%d", &n);

bool prime = n == 2 || (n % 2 && n != 1);

for (int i = 3; prime && i <= n / i; i += 2)
{
    prime = n % i;
}

Вот простая демонстрационная программа, показывающая данный подход

#include <iostream>

int main()
{
    for (unsigned int n = 1; n <= 100; n++)
    {
        bool prime = n == 2 || (n % 2 && n != 1);

        for (unsigned int i = 3; prime && i <= n / i; i += 2)
        {
            prime = n % i;
        }

        if (prime) std::cout << n << ' ';
    }

    std::cout << std::endl;
}

Вывод программы на консоль:

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.