Q:

Fermat Algorithm for prime factors calculation

According to youtube link the prime factors of an odd number can be calculated as follows:
a = sqrt(N + b^2)
I wrote below program to do that but I am not getting the prime factors of 2345678917. I know this is prime number but for other prime numbers the program does return 1 and the number itself but for this number it is not happening. Why?
#include <stdio.h>
#include <math.h>

void foo(unsigned long long x)
{
    int i;
    for (i=1;i<x;i++)
        if (fmod(sqrt(x + i*i), 1) == 0) {
            printf("%f %f\n", (sqrt(x + i*i) - i), (sqrt(x + i*i)+i));
            return;
        }
}

int main(void) {
    foo((unsigned long long)2345678917);
    return 0;
}

A:

First of all, the type of i (int) does not match x (unsigned long long). Change the type of i to unsigned long long to get going.
Once you do that, your program will proclaim happily that 14 * 167548494 = 2345678917. Of course, this is not true, since the product of two even numbers cannot be odd. The problem here is loss of precision, so you need to implement a square testing function for integers, rather than testing if the floating point square root is integral.
#include <stdio.h>
#include <math.h>

unsigned long long find_sqrt(unsigned long long x)
{
    unsigned long long lo = 1;
    while (4 * lo * lo <= x) lo *= 2;
    unsigned long long hi = 2 * lo;
    while (lo + 1 < hi) {
        unsigned long long mid = lo + (hi - lo) / 2;
        if (mid * mid <= x) lo = mid;
        else hi = mid;
    }
    return lo * lo == x ? lo : 0;
}

void foo(unsigned long long x)
{
    unsigned long long i;
    for (i=1;i<x;i++) {
        unsigned long long sqrt_x_ii = find_sqrt(x + i*i);
        if (sqrt_x_ii) {
            printf("%llu = %llu * %llu\n",
                   x, sqrt_x_ii - i, sqrt_x_ii + i);
            return;
        }
    }
}

int main(void) {
    foo((unsigned long long) 2345678917);
    return 0;
}

