费马算法素因子计算

Question

据的YouTube link素因子奇数可以如下计算：

A = SQRT（N + B^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; 
}