可能重复:有效地查找数字的所有除数
这更像是一个效率问题,而不是通用的“找到一种方法”,但在得到一些奇怪的结果后,我想看看是否有人可以告诉我为什么最后一种方式如此低效:
方式1:蛮力,没有优化
public static List<int> proper_divisors(int x)
{
List<int> toreturn = new List<int>();
for (int i = 1; i <= Math.Floor(Math.Sqrt(x)); i++)
{
if (x % i == 0)
{
toreturn.Add(i);
toreturn.Add(x / i);
}
}
if (toreturn.ElementAt(toreturn.Count() / 2) == toreturn.ElementAt(toreturn.Count() / 2 - 1))
{
toreturn.Remove(toreturn.ElementAt(toreturn.Count() / 2));
}
return toreturn;
}
方式2:与之前相同,但这一次,检查它是否为第一个(因为这些情况占用了大部分时间,使用miller-rabin进行初步检查)
public static List<int> proper_divisors(int x)
{
List<int> toreturn = new List<int>();
if (!isprime(x))
{
for (int i = 1; i <= Math.Floor(Math.Sqrt(x)); i++)
{
if (x % i == 0)
{
toreturn.Add(i);
toreturn.Add(x / i);
}
}
if (toreturn.ElementAt(toreturn.Count() / 2) == toreturn.ElementAt(toreturn.Count() / 2 - 1))
{
toreturn.Remove(toreturn.ElementAt(toreturn.Count() / 2));
}
}
else
{
toreturn.Add(1);
toreturn.Add(x);
}
return toreturn;
}
它认为到目前为止最快的方式是方式3,因为它每次找到一个主要因素时它减少了它的工作次数,并且它只尝试了质数(这些是在运行时通过筛子生成的,大约需要34个这样做的最后一件事就是采用素数因子和它们的权力,并列出所有因素 .
方式3:
public static HashSet<int> prime_factors(int x)
{
if (!isprime(x))
{
List<int> toreturn = new List<int>();
int i = 0;
while (primes[i] <= x)
{
if (x % primes[i] == 0)
{
toreturn.Add(primes[i]);
x = x / primes[i];
}
else
{
i++;
}
}
var power_set_primes = GetPowerSet(toreturn);
var factors = new HashSet<int>();
foreach (var p in power_set_primes)
{
var factor = p.Select(z => z).Aggregate(1, (z, y) => z * y);
factors.Add(factor);
}
return factors;
}
else
{
HashSet<int> toreturn = new HashSet<int>();
toreturn.Add(1);
toreturn.Add(x);
return toreturn;
}
public static IEnumerable<IEnumerable<T>> GetPowerSet<T>(List<T> list)
{
return from m in Enumerable.Range(0, 1 << list.Count)
select
from i in Enumerable.Range(0, list.Count)
where (m & (1 << i)) != 0
select list[i];
}
花费第一百万个数字的时间:方式1:7223毫秒方式2:8985毫秒(对于小数字,我猜的主要检查不值得)方式3:49423毫秒
所以我的问题是双重的:1)为什么方式3这么慢? 2)有什么东西可以使它更快?另外,素数被计算为一个列表,然后转换为一个数组,因为我认为它会更快 . 糟糕的举动?
1 回答
这是整数分解的问题域 . 这里有许多众所周知的算法:
http://en.wikipedia.org/wiki/Integer_factorization#Factoring_algorithms
我建议你选择最匹配的 Profiles .
我原来的评论: