In order to solve the Euler Project problem n°5, I wrote the following program:
class p5
{
const int maxNumber = 20;
static void Main(string[] args)
{
Job(); // First warm-up call to avoid Jit latency
var sw = Stopwatch.StartNew();
var result = Job();
sw.Stop();
Debug.Assert(result == 232792560);
Console.WriteLine(result);
Console.WriteLine(sw.Elapsed);
Console.ReadLine();
}
private static int Job()
{
var result = Enumerable.Range(1, int.MaxValue - 1)
.Where(
n => Enumerable.Range(maxNumber / 2 + 1, maxNumber / 2).All(c => n % c == 0)
).First();
return result;
}
}
However, I found this is a bit long (17 seconds, in release mode), even if it's working.
Is there any possible optimization ?
FYI, I tried with AsParallel
method, but as expected, the chunk of works are too small and the context switch was heavier than the benefits (more that 1 minute) :
var result = Enumerable.Range(1, int.MaxValue - 1).AsParallel()
.Where(
n => Enumerable.Range(maxNumber / 2 + 1, maxNumber / 2).All(c => n % c == 0)
).First();
return result;
[Edit] According martin's suggestion, this version divided by 10 the time taken :
private static int Job()
{
var n =2;
bool result;
do
{
result = true;
for (int c = maxNumber / 2; c <= maxNumber; c++)
{
if (n % c > 0)
{
result = false;
break;
}
}
n ++;//= 2;
} while (!result);
return n;
}
[Edit] To sum up all my tests, rough execution time :
- My first implementation : 20 secs
- Removed the inner enumerable.Range call (replaced by a simple for loop): 3 seconds
- Removed the outer and inner enumerable.Range call: 1.5 second
- Only taking even numbers : (with loops only, no enumerable.range) : less than 1 second
- Using Gcd/LCm euclidean algorithms as suggested by drhirsch : 0.004 ms
The latest suggestion is clearly the good answer. I thank drhirsch for suggesting another approach instead of only simple loop optimization
See Question&Answers more detail:
os 与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…