关于一个整数分解因子的程序的思考（有点难）(50分)

今天看了一个关于整数分解的数学公式
公式如下：
n=x^2-y^2=(x-y)(x+y);
原理：任何一个整数都可以写成如上的公式
也就是说传统的分解整数的方法是:
for i:=1 to Sqrtdo
if n mod i then
........//执行代码
传统的方法在面对大整数时，比较慢
而采用n=x^2-y^2=(x-y)(x+y);比较快
思路是这样的：
for i:=1 to Sqrtdo
x:=Sqrt+i;
y:=sqrt((x2+i)-n);
if y是整数 then
break;
分解出来的两个数为(x-y)和(x+y),只要继续这样判断下去，就可以分解出所有的因子
但是，在程序中该怎麽实现?自己考虑了半天，也没有结果。
自己开始考虑的是递归，后面考虑的是多线程，感觉都不行。
整个感觉这个解下去的方法应该是个2叉树，可是自己对数据结构不太清楚
恳请高手给个完整的源代码或者思路（自己已经只有这点分了）

x:=Sqrt+i;
y:=sqrt((x2+i)-n);
这两句解释一下？

上面我改了一下,不好意思写错了一点
for i:=1 to Sqrtdo
x:=trunc(Sqrt+i);
y:=sqrt((x^2+i)-n);
if y是整数 then
break;
因为任何一个整数n都可以表示成n=x^2-y^2=(x-y)(x+y);
这样吧举个例子n=45
Sqrt大约为6.8吧，我自己估算的
i=1时x:=trunc(Sqrt+i);x为7
y:=sqrt((x^2+i)-n);
7^2就等于49然后sqrt(49-45)后y=2
if y是整数 then
x+y=9，x-y=5,9*5就等于45
接下来的问题是：分解9和5
通过 if x-y=1 then
来判断结束
但是对于一个输入的整数n在编程中，我不知道该怎麽实现这种方法的分解
自己对数据结构不太清楚，恳请高手给个完整的源代码或者思路（自己已经只有这点分了）

如果 n=2 那么 x=? y=?

n=2为特例
当然要把他特殊考虑出来

原算法的需要做 Sqrt 次的 MOD 运算。利用两数平方差的算法需要做 Sqrt 次的
Trunc运算以及Sqrt运算，而Sqrt运算似乎比MOD运算更加复杂、更加耗时，并且还存在浮点
运算精度问题——我看不出新算法有任何优势。

to :creation-zy
又看到你了，你在dwf上面的分还真高呢，分一点给我吧
这个算法是经过数学论证的
本生是一个关于解密方面的数学
那你想出来算法了吗？
当然在前面要
考虑的是x-y=0和x-y=1两种情况
我考虑了一下，如果是很大的数话，会是一个向下的伸展树的问题

应该是y:=sqrt(x^2-n)吧
初始化
x:=trunc(Sqrt+i);
y:=sqrt(x^2-n);
函数：
function fenjie(x:Extended;y:Extended)；
var
tempX,tempY:Extended;
begin
for i:=1 to Sqrtdo
begin
tempX:=trunc(Sqrt(x+y)+i);
tempY:=sqrt(x^2-n);
if y不为整数 then
continue
else
begin
if (tempX-tempY)<>1 then
fenjie((tempX-tempY),(tempX+tmepY))
else
break;
end;
tempX:=trunc(Sqrt(x-y)+i);
tempY:=sqrt(x^2-n);
if y不为整数 then
continue
else
begin
if (tempX-tempY)<>1 then
fenjie((tempX-tempY),(tempX+tmepY))
else
break;
end;
end;
end;


匆忙写的，不知道对不对……

忽然发现忘了加输出的语句，只要在那个判断<>1的结束循环里加个从上次调用函数后有没有再次调用就可以判断哪个是最终的数了，应该是吧……
能力有限……

“经过论证”——楼主一开始说，该公式适用于任何整数，然后就有人提出n=2时无解，
楼主立刻“纠正”说：n=2为“特殊情况”——我实在不知道还有多少个特殊情况。关于论
证我暂时没有看到论证过程——如果x,y可以是非自然数，那么自然没有问题，问题是因数
分解的目标是整数——我实在不知道哪里能找到能够让所有整数n都有整数x,y解的详细论证
过程。
对于楼主的结论：
>>传统的方法在面对大整数时，比较慢
>>而采用n=x^2-y^2=(x-y)(x+y);比较快
在下同样没有看到楼主是如何“论证”出上面的结论的。反正，根据我个人对楼主的循环
内部算法分析，该算法的效率非常低，而且开方运算受浮点数精度有限的影响，可能会出现
误判（即整数算成非整数，非整数算成整数）。还有，高质量的程序开发中基本上不会使用
“if 整数=浮点表达式 then
” 这样的比较方式——同样是因为精度的问题。
楼主根据 n=(x-y)(x+y) 就得到了“二叉树”的结论，那么按照这个思路，老算法所使用
的最简单的 n=x*y 不也是二叉树分解么？请问新算法到底有什么突破呢？
就您所举的45做为例子，利用老算法，一样可以从1循环到Trunc(Sqrt(45))，而得到5和9
并继续对5,9进行分解。新的算法除了将精确的MOD变成了更慢且不精确的Sqrt之外，没有实
质改进。如果我们不那么“笨”的使用自然数序列而采用素数序列来进行分解，需要检测的
数就会大幅度减少（对2,3,5,7,11,13...进行MOD运算，而不是2,3,4,5,6,7,8...），从而
提高效率（对于大数而言，素数的分布密度趋向于 Ln(X)/X ——效率的提高不言而喻）。
关于分数——只要你多学习、思考、实践并帮助别人，自然不会缺。

ps: 如果被分解的数为 14 ，那么用老算法可以很容易的得到因数2和7，但是，采用新算法
的话，请问还有整数的x,y解么？

[]

to creation-zy兄
果然是高手，一眼就看出了这个公式的出处。
不知道这个论坛里，还有比你强的麽？
我也回去考虑了一下，这个算法的确是很慢，只有针对一些特殊的情况，才很快
至于我所说的“二叉树”是指这个分解
n=x^2-y^2=(x-y)(x+y);
打个比方说n第一次分解下来为x=17,y=8,x-y=9,x+y=25,第二次就要对9和25分别进行分解，
是不是这个算法展开就有点像“二叉树”
也就是因子越多向下面展开越多
我现在先不考虑这样考虑算法的运行速度以及x=2,y=7这些情况，只是以这个算法作个模型
像这样发散的“二叉树”，有不有什麽可以实现的方法？
我现在想征求这种模型的实现方法

这个算法，我已经知道了，通过构造二叉树，就能够解决
但是，我有了个新的问题，在看数据结构时产生的，程序中有一句没有看懂
哪位帮我解释一下，具体问题在程序中，我给了注释
程序如下：
用链表存储方式生成上述二叉树，中序遍历之。
1.将上述二叉树用广义表表示为A(B(D,E(G)),C(F(,H)))
2.根据广义表串（以#结束）生成二叉树。
--------------------------------------------------------------------------------
program ltree;
const n=8;
type trlist=^node;
node=record
da:char;
l,r:trlist;
end;
var
s:array[1..n] of trlist;
p,root:trlist;
ch:char;
top,k:integer;
procedure creat(var head:trlist);
begin
read(ch);
top:=0;
while ch<>'#'do
begin
case ch of
'A'..'Z':begin
new(p);p^.da:=ch;p^.l:=nil;p^.r:=nil;
if top<>0 then
case k of
1: s[top]^.l:=p;
2: s[top]^.r:=p;
end
end;
{下面这句不懂，里面有两个''括号外面和里面分别有一个'符号，并且begin
前面还有冒号这种语法以前没有遇到过，这个是什麽意思啊？}
'(':begin
top:=top+1;s[top]:=p;k:=1;
end;
')':top:=top-1;
',':k:=2;
end;
read(ch);
end;
head:=s[1];
end;
procedure inorder(head:trlist);
begin
if head^.l<>nil then
inorder(head^.l);
write(head^.da);
if head^.r<>nil then
inorder(head^.r);
end;
begin
write('input tree string:');
creat(root);
inorder(root);
end.
--------------------------------------------------------------------------------
这个问题解决后我就给分了

抛开算法优劣不谈,楼主的想法可以用广度优先实现:
先把待分解的数放进open表,然后取open表首数放入close表,如果该数能分解,则将其分解的因子放入open表.如此往复,直到open表取空则得解.

program Project1;
{$APPTYPE CONSOLE}
uses
Math;
const
MaxLen = 1000000;
type
TNode = record
Value: LongWord;
CanDecomposed: Boolean
end;

var
n: LongWord;
sqrtn: LongWord;
x, y: LongWord;
List: array [1..MaxLen] of TNode;
Close, Open: 0..MaxLen;
i: LongWord;
function Decompose(const n, sqrtn: LongWord;
var x, y: LongWord): Boolean;
var
i: LongWord;
d:do
uble;
a, b: LongWord;
begin
if n<3 then
Decompose:=False
else
if n mod 2=0 then
begin
Decompose:=True;
x:=n div 2;
y:=2
end
else
begin
Decompose:=False;
for i:=1 to sqrtndo
begin
a:=sqrtn+i;
b:=a*a-n;
if not (b mod 10 in [2, 3, 7, 8]) then
begin
d:=Sqrt(b);
b:=Round(d);
if Abs(b-d)<1e-05 then
begin
x:=a+b;
y:=a-b;
Decompose:=y<>1;
Break
end
end
end
end
end;

begin
Write('Input n=');
ReadLn;
Close:=0;
Open:=1;
List[Open].Value:=n;
List[Open].CanDecomposed:=False;
repeat
Inc(Close);
sqrtn:=Trunc(Sqrt(List[Close].Value));
if Abs(sqrtn-Sqrt(List[Close].Value))<1e-05 then
Dec(sqrtn);
if Decompose(List[Close].Value, sqrtn, x, y) then
begin
List[Close].CanDecomposed:=True;
Inc(Open);
List[Open].Value:=x;
List[Open].CanDecomposed:=False;
Inc(Open);
List[Open].Value:=y;
List[Open].CanDecomposed:=False
end
until (Close=Open) or (Open>MaxLen-2);
if Close=Open then
begin
Write(n, '=');
for i:=1 to Closedo
if not List.CanDecomposed then
Write(List.Value, 'x');
WriteLn('1')
end
else
WriteLn('Out of buffer');
ReadLn
end.

瞎讲一下,这个好像是<歌德巴赫猜想>吧???
目前在理论上好像还没有任何公式可快速求证!
因此,我趁早退出该问题的讨论!!

虽然不推荐,但递归也是可以的,Decompose算法请楼主自己实现吧,俺上面写的也有问题,调用方法如下.
function f(const n: LongWord): string;
var
x, y: LongWord;
begin
if Decompose(n, x, y) then
Result:=Decompose(x)+'x'+Decompose
else
Result:=IntToStr
end;

多人接受答案了。