Ферма алгоритм для вычисления простых множителей

Question

В соответствии с YouTube linkпростые множители из нечетного числа может быть рассчитана следующим образом:

а = SQRT (N + Ь^2)

я написал ниже программы для этого, но я не получаю основных факторов 2345678917. Я знаю, что это простое число, но для других простых чисел программа возвращает 1 и само число, но для этого числа это не происходит. Зачем?

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

Answer 1

Прежде всего, тип i (int) не соответствует x (unsigned long long). Измените тип i на unsigned long long, чтобы начать работу.

Как только вы это сделаете, ваша программа с радостью объявит, что 14 * 167548494 = 2345678917. Конечно, это неверно, так как произведение двух четных чисел не может быть нечетным. Проблема здесь заключается в потере точности, поэтому вам нужно реализовать функцию квадратного тестирования для целых чисел, а не тестировать, является ли квадратный корень с плавающей точкой интегральным.

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