for programming nerds ONLY!
Vitriola — Thu, 07/30/2009 - 08:24
Where I work, we often bet on programming puzzles. The latest bet was who could write a program to find all the prime numbers to a million that ran the fastest. While I primarily program in Delphi and Java, I really like ruby. Ruby is interpreted and I do not have the really fast version but I won by a large margin. Mine ran in under half a second. So, in the throes of my happy dance, I post the final code here.
If you are not a for real programmer, look away and save yourself NOW!
require 'benchmark'
highestPrime = 1_000_000
highestMultiple = Math.sqrt(highestPrime).to_i
primes = Array.new(highestPrime, true)
Benchmark.bm do |x|
x.report('primes') do
currentNum = 3
while currentNum < highestMultiple do
(currentNum*currentNum).step(highestPrime, currentNum * 2) { |i| primes[i] = false }
begin currentNum += 2 end until primes[currentNum]
end
end
end
# the print out
numWidth = highestPrime.to_s.length + 1
print 2.to_s.rjust(numWidth)
col = 2
3.step(highestPrime, 2) do |i|
if primes[i]
print i.to_s.rjust(numWidth)
col += 1
end
if col == 20
col = 1
puts ""
end
end
the sincerest form of flattery
Vitriola — Thu, 07/30/2009 - 11:33I can see that you are trying to translate my algorithm. FYI, what won it for me was that I had optimizations that he did not consider.
First, when you are starting from a known odd prime, the first number you tick off as a multiple is its square. Any multiples lower than that will be covered by other primes. That means that
for (int i = currentPrime+currentPrime; i < HIGHEST_PRIME; i+= currentPrime)
should be currentPrime*currentPrime not currentPrime+currentPrime. Also, as every other multiple is a multiple of 2,
i+= currentPrime
can be optimized to
i+= currentPrime * 2
thus halving the number of steps. He also did not consider that he only needed to go as far as the square root of the max value. I left it as a mathematical function rather than hard coding because I tried it out with various max numbers.
He was also doing a lot of floating point math, where I do none. I know that the same algorithm will run faster if compiled, but we have few speed contests here. More often it is a matter of code golfing. (smallest code to git R done)
C# Primes
Knoppix (not verified) — Thu, 07/30/2009 - 09:15using System;
namespace Primes
{
class Program
{
static void Main(string[] args)
{
for (long i = 2; i <= 1000000; i++)
{
if ((i % 2 != 0) || (i == 2))
{
Console.WriteLine("{0} ", i);
}
}
Console.WriteLine("Complete!");
}
}
}
Take our the Console.WriteLine in the "if" statement and the code executes instantly, unless you want to print every prime number from 0 to 1,000,000 to the screen. Writting to the GUI this many times no matter what language is slow.
Isn't yours just listing the
saedo — Thu, 07/30/2009 - 09:28Isn't yours just listing the set of odd numbers and 2?
You are right, trying to
Knoppix (not verified) — Thu, 07/30/2009 - 09:51You are right, trying to indent this chopped off the upper part of the code. I will post this later, time to do my real work.