2
#include <stdio.h>
#include <math.h>

int main()
{
    int n;
    system("chcp 1251");
    printf("Введите целое число\t");
    scanf_s("%d", &n);

    for (int i = 2; i < sqrt(n) + 0.00001; ) {
        if (n % i == 0) {
            printf("%d ", i);
            n /= i;
        }
        else {
            ++i;
        }
    }

    if (n > 1)
        printf("%d", n);
    getchar(); getchar();
    return 0;
}

Вот простой код на С, который выводит простые делители числа.

Пример: 2600 = 2*2*2*5*5*13. Так вот, почему в for'е написано именно sqrt(n) + 0.00001?

1 ответ 1

5

i < sqrt(n) + 0.00001 — это аналог i <= sqrt(n) с учётом неточностей при вычислений дробных чисел. Автор алгоритма решил (или просто взял с потолка), что эта неточность — промах счётчика мимо значения корня — будет не более одной стотысячной, оттуда и константа.

Если переводить на человеческий язык, условие буквально означает «останови цикл, когда значение i чуть-чуть превысит значение квадратного корня из n».

8
  • 2
    кстати, любопытно, что на большинстве платформ (с 32-битным int и IEEE754 double) этот пример будет работать корректно даже при сравнении с <= т.к. целые типы представляются без погрешности... само собой, я не рекомендую и не оправдываю использование таких тонких и зыбких механик где-либо...
    – Fat-Zer
    Commented 29 мар. 2019 в 2:15
  • 1
    @Asmund Ошибка может накопиться как в меньшую сторону, так и в большую. i <= n не учтёт второй случай, из-за чего, к примеру, значение 4.0000015268 будет ошибочно пропущено при n = 16. Commented 29 мар. 2019 в 2:17
  • 1
    @Asmund ... или наоборот, квадратный корень выдаст значение меньше идеального, из-за чего последнее значение i опять же будет пропущено. Это целочисленная арифметика гарантирует неявное округление после каждой операции, которое сбрасывает неточности. При double же и float нам приходится самим учитывать наличие погрешности и её рост. Commented 29 мар. 2019 в 2:25
  • 1
    Если вопрос не конкретно про sqrt() + EPS, то никогда так не работайте с нецелочисленным типом данных. А с учетом тяжести операции sqrt() - это ужас. Вариант с целыми числами: i * i <= n. Commented 29 мар. 2019 в 8:52
  • 1
    @Arhad "не более одной десятимиллионной" - стотысячной, если позанудствовать...
    – tum_
    Commented 30 мар. 2019 в 7:34

Ваш ответ

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

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