最近我对LINQ很感兴趣。我想求质数。我实际上做得很好,但我的代码没有显示质数,它低于Sqrt(n)。
static void Main(string[] args)
{
Func<int, int, IEnumerable<int>> EnumerableRange =
(startPoint, endPoint) =>
Enumerable.Range(Math.Min(startPoint, endPoint), Math.Abs(startPoint - endPoint) + 1);
Func<int, int, bool> isFullyDivided =
(value, divisor) =>
(value % divisor).Equals(0);
int sp = 2,
ep = 100;
var query =
EnumerableRange(sp, ep)
.Where(value =>
EnumerableRange(2, (int)Math.Ceiling(Math.Sqrt(ep)))
.Any(divisor =>
isFullyDivided(value, divisor))
);
var primeNumbers =
EnumerableRange(sp, ep)
.Except(query);
foreach (var item in primeNumbers)
{
Console
.WriteLine(item);
}
Console
.Read();
}
目前,该代码错误忽略了小于sqrt(n)
的素数。代码应该得到2到100之间的质数。相反,它只打印质数11及以上。缺少了质数2, 3, 5, 7
。
您的除数约束是不正确的-当您只需要检查2和Sqrt(value)
之间的除数时,您正在查看2和Sqrt(ep)
(10)之间的除数:
var query =
EnumerableRange(sp, ep)
.Where(value => V----------
EnumerableRange(2, (int)Math.Ceiling(Math.Sqrt(value)))
.Any(divisor =>
isFullyDivided(value, divisor))
);
这就是为什么你的质数从11开始,因为你的除数到10,这将包括值本身。@ryanyuyu的回答也以不同的方式解决了同样的问题。您的代码仍然会检查不必要的除数。
你的逻辑有问题。所有的东西都可以平均地自分,所以你应该检查value != divisor
。否则,您将错误地排除可自除的数字(例如5 % 5 == 0
)。
var query =
EnumerableRange(sp, ep)
.Where(value =>
EnumerableRange(2, (int)Math.Ceiling(Math.Sqrt(ep)))
.Any(divisor =>
value != divisor && //This is the logic you are missing
isFullyDivided(value, divisor))
);
最佳方案:
var query =
EnumerableRange(sp, ep)
.Where(value =>
EnumerableRange(2, (int)Math.Ceiling(Math.Sqrt(value)))
.Any(divisor =>
!value.Equals(divisor) &&
isFullyDivided(value, divisor))
);
数学。地板不对。正确的是Math.Ceiling