PrimeFinder
Alright everyone has written the obligatory "Hello World!" program when they start to learn a new language. I have my own variety of that practice and its PrimeFinder. Whenever I start to learn a new language I write a program that finds primes. I know this may sound a little strange but this normally allows me to practice a number of new skills and techniques as well as see if there is a way I can improve both my prime number finding logic and find out if the new language has anything to offer that is unique for this task. In this post I'll examine PrimeFinder written in PowerShell, C#, and T-SQL. I will discuss each and the surprises I found out about each. Feel free to take this as a challenge to find more efficient ways in these languages or any others; I would like to see any different solutions that are more efficient.
There are some rules though, here they are:
1. The solution must be robust enough to find all primes ranging from 1 to 2,147,483,647 (signed 4 byte int limit)
2. The solution must output the prime numbers in some manner which is recordable. (printing to standard out is fine since that can be pushed into a text file)
3. The solution must restartable, or easily changed to a state that allows it to be restartable. In that it can produce a certain number of primes, stopped and pick up where it left off. (this is the reason for the requirement #2, very flexible on this requirment)
4. The solution must be timed
5. The solution should find the first 10000 primes by default when executed
6. The solution is allowed three primary constants of 1, 2, and 3. These are allowed to remove any single use code that would be in place to find these 3 primes.
The first solution was written in C# and is the reason that I was looking into the problem to begin with. This code was a pretty much brute force attack against prime numbers but it seems to be very efficient. I am running this code in a screen shot below wrapped in a a few lines of PowerShell code to produce an easy to read timer at the bottom of the screen shot.
7.48 seconds not bad!
Save the following code in a .cs file, compile it should be exectable.
using System;
namespace fibich.math
{
class primeFinder
{
const int prime1=1;
const int prime2=2;
const int prime3=3;
static void Main()
{
//Variable Decleration
bool isPrime =true;
int possiblePrime =prime3;
int primeCount=0;
//Const Output
Console.WriteLine("Starting to find Primes");
Console.WriteLine("prime:" + prime1.ToString());
Console.WriteLine("prime:" + prime2.ToString());
Console.WriteLine("prime:" + prime3.ToString());
//Finding Primes
while (primeCount<10000)
{
possiblePrime+=prime2;
for (int primeFinder =prime3; primeFinder
{
if ((possiblePrime % primeFinder)==0)
{
isPrime=false;
break;
}
else
{
isPrime=true;
}
}
if (isPrime==true)
{
primeCount++;
Console.WriteLine("prime:"+possiblePrime.ToString()+" primeCount:"+primeCount.ToString());
}
}
return;
}
}
}
The second solution I offer up is written in PowerShell. The reason I wrote this was because I wrote the C# solution I noticed how similar the syntax was and I figured why not I it only required a few changes to the code to make it executable as a powershell script. Basically I added $ all my variables, changed == to -eq and < to -gt removed the Console.WriteLine from the output statements and that was about it. I wrapped this code in the same PowerShell statements to produce the exact same timer information.
277 seconds! Wow that was over 37 times slower than the C# solution.
I expected PowerShell to be slower but man I didn't expect that, I was thinking maybe 10 times as worst. Hey PowerShell's power is not in number crunching, its a scripting environment and gets its power from delivering more productivity per key stroke, empowering the developer not squeezing every ounce of performance from a process so I'm not disappointed. Just a little surprised.
Save the following code to a ps1 file enable scripts in PowerShell and you should be good to go.
#Variable Decleration
$primeCount=1
$prime1=1;
$prime2=2;
$prime3=3;
$isPrime =$true;
$possiblePrime =$prime3;
$primeCount=0;
#Const Output
"Starting to find Primes";
"prime:" + $prime1.ToString();
"prime:" + $prime2.ToString();
"prime:" + $prime3.ToString();
#Finding Primes
while ($primeCount -lt 10000)
{
$possiblePrime+=$prime2;
for ($primeFinder =$prime3; $primeFinder -le ([Math]::Sqrt($possiblePrime))+1;$primeFinder+=$prime2)
{
if (($possiblePrime % $primeFinder) -eq 0)
{
$isPrime=$false;
break;
}
else
{
$isPrime=$true;
}
}
if ($isPrime -eq $true)
{
$primeCount++;
"prime:"+$possiblePrime.ToString()+" primeCount:"+$primeCount.ToString();
}
}
The final solution is something a little different. It’s a T-SQL solution, where the prime numbers that are found are used to find the next prime numbers. I was hoping that this approach would be more efficient than the brute force used by the other two solutions and it still maybe at the higher range end of prime numbers. This solution also utilizes set based logic to calculate the modulus of each number, instead of trying one number at a time against the trial prime number.
No Screen shot unfortunately but this solution took 70 seconds so it came in third in the trails to find the first 10,000 primer numbers.
This solution requires a database name dataHub, a schema named numbers and a table named primes in that schema.
use datahub
BEGIN
if not exists(select * from sys.schemas where name='numbers')
BEGIN
execute('Create Schema numbers authorization dbo')
print 'schema created:Numbers'
END
else
BEGIN
print 'schema already exists:Numbers'
END
END
use datahub
IF EXISTS (SELECT * FROM sys.objects WHERE object_id = OBJECT_ID(N'[Numbers].[primes]') AND type in (N'U'))
DROP TABLE [Numbers].[primes]
GO
create table numbers.primes (
prime bigint not null primary key
,version int not null
)
use dataHub
GO
IF EXISTS (SELECT * FROM sys.objects WHERE object_id = OBJECT_ID(N'[Numbers].[primeFinder]') AND type in (N'P', N'PC'))
DROP PROCEDURE [Numbers].[primeFinder]
GO
create procedure numbers.primeFinder
@primeCount int = 10000
,@purge bit =0
as
declare @version int
declare @possiblePrime bigInt
declare @primeCounter int
set @primeCounter=0
if @purge=1
BEGIN
delete numbers.primes
set @version=1
--insert into numbers.primes
--(prime,version)
--values(1,@version)
--insert into numbers.primes
--(prime,version)
--values(2,@version)
insert into numbers.primes
(prime,version)
values(3,@version)
END
else
BEGIN
select @version = coalesce(max(version),0) from numbers.primes
END
select @possiblePrime = max(prime) from numbers.primes
while @primeCounter <@primeCount
BEGIN
set @possiblePrime=@possiblePrime+2
if not exists(select 1 from numbers.primes where prime<=sqrt(@possiblePrime) and @possiblePrime%prime=0)
BEGIN
insert into numbers.primes
(prime,version)
values(@possiblePrime,@version)
set @primeCounter=@primeCounter+1
END
END
go
Well that’s it; I look forward to hearing back from everyone and seeing any different or new takes on these solutions. I already I have an idea for a combination solution utilizing the CLR integration in SQL Server, but that will have to wait to another time.