gpt4 book ai didi

java - 整数分解

转载 作者:行者123 更新时间:2023-12-04 05:12:09 25 4
gpt4 key购买 nike

谁能向我解释为什么下面的算法是一个无错误的整数分解方法,它总是返回一个非平凡的 N 因子。
我知道这听起来有多奇怪,但我在 2 年前设计了这种方法,但仍然不了解其背后的数学逻辑,这使我很难改进它。它非常简单,只涉及加法和减法。

public static long factorX( long N )
{
long x=0, y=0;
long b = (long)(Math.sqrt(N));
long a = b*(b+1)-N;
if( a==b ) return a;

while ( a!= 0 )
{
a-= ( 2+2*x++ - y);
if( a<0 ) { a+= (x+b+1); y++; }
}

return ( x+b+1 );
}

看起来上面的方法实际上是通过迭代丢番图方程找到了一个解:
f(x,y) = a - x(x+1) + (x+b+1)y
where b = floor( sqrt(N) ) and a = b(b+1) - N
that is, when a = 0, f(x,y) = 0 and (x+b+1) is a factor of N.

Example: N = 8509
b = 92, a = 47
f(34,9) = 47 - 34(34+1) + 9(34+92+1) = 0
and so x+b+1 = 127 is a factor of N.

重写方法:
public static long factorX(long N)
{
long x=1, y=0, f=1;
long b = (long)(Math.sqrt(N));
long a = b*(b+1)-N;
if( a==b ) return a;

while( f != 0 )
{
f = a - x*(x+1) + (x+b+1)*y;
if( f < 0 ) y++;
x++;
}

return x+b+1;
}

我非常感谢有关如何改进此方法的任何建议。

这是 10 个 18 位随机半素数的列表:
349752871155505651 = 666524689 x 524741059   in 322 ms
259160452058194903 = 598230151 x 433211953 in 404 ms
339850094323758691 = 764567807 x 444499613 in 1037 ms
244246972999490723 = 606170657 x 402934339 in 560 ms
285622950750261931 = 576888113 x 495109787 in 174 ms
191975635567268981 = 463688299 x 414018719 in 101 ms
207216185150553571 = 628978741 x 329448631 in 1029 ms
224869951114090657 = 675730721 x 332780417 in 1165 ms
315886983148626037 = 590221057 x 535201141 in 110 ms
810807767237895131 = 957028363 x 847213937 in 226 ms
469066333624309021 = 863917189 x 542952889 in 914 ms

最佳答案

好的,我用 Matlab 看看这里发生了什么。这是 N=100000 的结果:
enter image description here
您在增加 x在每次迭代中,以及 a 的有趣模式变量与余数密切相关 N % x+b+1 (正如您在绘图的灰线中看到的, a + (N % (x+b+1)) - x = floor(sqrt(N)) )。
因此,我想 您只是发现第一个因子大于 sqrt(N)通过简单的迭代,但用一个相当模糊的标准来决定它真的是一个因素:D
(抱歉回答一半……我要走了,我可能会稍后继续)。

这是 matlab 代码,以防万一你想自己测试:

clear all
close all

N = int64(100000);

histx = [];
histDiffA = [];
histy = [];
hista = [];
histMod = [];
histb = [];

x=int64(0);
y=int64(0);
b = int64(floor(sqrt(double(N))));
a = int64(b*(b+1)-N);
if( a==b )
factor = a;
else
while ( a ~= 0 )
a = a - ( 2+2*x - y);
histDiffA(end+1) = ( 2+2*x - y);
x = x+1;
if( a<0 )
a = a + (x+b+1);
y = y+1;
end
hista(end+1) = a;
histb(end+1) = b;
histx(end+1) = x;
histy(end+1) = y;
histMod(end+1) = mod(N,(x+b+1));
end
factor = x+b+1;
end

figure('Name', 'Values');
hold on
plot(hista,'-or')
plot(hista+histMod-histx,'--*', 'Color', [0.7 0.7 0.7])
plot(histb,'-ob')
plot(histx,'-*g')
plot(histy,'-*y')
legend({'a', 'a+mod(N,x+b+1)-x', 'b', 'x', 'y'}); % 'Input',
hold off

fprintf( 'factor is %d \n', factor );

关于java - 整数分解,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14769792/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com