xox*_*oxo 3 algorithm prime-factoring fxsl
我需要找出超过3000亿的主要因素.我有一个功能,正在添加到他们的列表......非常慢!它现在已经运行了大约一个小时,我认为它还有一段距离可以走了.我这样做是完全错误还是预期?
编辑:我试图找到数字600851475143的最大素数因子.
编辑:结果:
{
List<Int64> ListOfPrimeFactors = new List<Int64>();
Int64 Number = 600851475143;
Int64 DividingNumber = 2;
while (DividingNumber < Number / DividingNumber)
{
if (Number % DividingNumber == 0)
{
ListOfPrimeFactors.Add(DividingNumber);
Number = Number/DividingNumber;
}
else
DividingNumber++;
}
ListOfPrimeFactors.Add(Number);
listBox1.DataSource = ListOfPrimeFactors;
}
}
Run Code Online (Sandbox Code Playgroud)
Aln*_*tak 25
您还记得在找到它们时按每个因素划分您正在分解的数字吗?
比如说,你发现2是一个因素.您可以将其添加到因子列表中,然后将您尝试分解的数字除以该值.
现在你只是在寻找1500亿的因素.每次你应该从你刚刚找到的因素开始.因此,如果2是一个因素,再次测试2.如果您找到的下一个因素是3,则再次从2进行测试无法进行测试.
等等...
Bra*_*adC 20
使用蛮力很难找到素因子,这听起来像你正在使用的技术.
以下是一些提高速度的技巧:
编辑:一个简单的例子:您正在找到275的因子.
所以275 = 5*5*11
更有意义吗?
Ecl*_*pse 17
保理大数字是一个难题.事实上,我们很难依靠它来保持RSA的安全.但是,请查看维基百科页面,了解可以提供帮助的算法的一些指示.但对于一个小的数字,它真的不应该花那么长时间,除非你一遍又一遍地重新做一些你不需要去的地方.
对于暴力解决方案,请记住您可以进行一些小优化:
Dim*_*hev 10
这是一个XSLT解决方案!
此XSLT转换需要0.109秒.
<xsl:stylesheet version="2.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
xmlns:xs="http://www.w3.org/2001/XMLSchema"
xmlns:saxon="http://saxon.sf.net/"
xmlns:f="http://fxsl.sf.net/"
exclude-result-prefixes="xs saxon f"
>
<xsl:import href="../f/func-Primes.xsl"/>
<xsl:output method="text"/>
<xsl:template name="initial" match="/*">
<xsl:sequence select="f:maxPrimeFactor(600851475143)"/>
</xsl:template>
<xsl:function name="f:maxPrimeFactor" as="xs:integer">
<xsl:param name="pNum" as="xs:integer"/>
<xsl:sequence select=
"if(f:isPrime($pNum))
then $pNum
else
for $vEnd in xs:integer(floor(f:sqrt($pNum, 0.1E0))),
$vDiv1 in (2 to $vEnd)[$pNum mod . = 0][1],
$vDiv2 in $pNum idiv $vDiv1
return
max((f:maxPrimeFactor($vDiv1),f:maxPrimeFactor($vDiv2)))
"/>
</xsl:function>
</xsl:stylesheet>
Run Code Online (Sandbox Code Playgroud)
此转换仅在0.109秒内产生正确的结果(最大素数因子600851475143).:
6857
转换使用f:sqrt()
和f:isPrime()
定义的FXSL 2.0
- 一个用于XSLT中的函数编程的库.FXSL
本身完全是用XSLT编写的.
f:isPrime()
使用费马的小定理,以便确定原理是有效的.