#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; }

Here is a simple C code that prints the prime dividers of a number.

Example: 2600 = 2 * 2 * 2 * 5 * 5 * 13. So, why is sqrt (n) + 0.00001 written in for'e?

    1 answer 1

    i < sqrt(n) + 0.00001 is an analogue of i <= sqrt(n) taking into account inaccuracies when calculating fractional numbers. The author of the algorithm decided (or simply took it from the ceiling) that this inaccuracy - a counter miss past the root value - would be no more than one hundred thousandth, and from there a constant.

    If translated into human language, the condition literally means “stop the cycle when the value of i slightly exceeds the value of the square root of n ”.

    • But why not just i <= n? - Asmund
    • By the way, it is curious that on most platforms (with 32-bit int and IEEE754 double ) this example will work correctly even when compared with <= since whole types are presented without error ... by itself, I do not recommend or condone the use of such thin and unstable mechanics anywhere ... - Fat-Zer
    • @Asmund, related question: ru.stackoverflow.com/questions/417453/… ... and in this case it would be correct to get rid of floating point arithmetic and use i*i <= n . - Fat-Zer
    • @Asmund The error can accumulate both down and up. i <= n does not take into account the second case, because of what, for example, the value 4.0000015268 will be mistakenly missed when n = 16 . - ߊߚߤߘ
    • @Asmund ... or vice versa, the square root will produce a value less than ideal, which is why the last value of i will again be skipped. This integer arithmetic guarantees implicit rounding after each operation that discards inaccuracies. With double and float we have to take into account the presence of an error and its growth. - ߊߚߤߘ