Thursday, March 20, 2008

Find Prime Number at Fastest Speed.

Introduction to the Prime Numbers:
A composite number is a positive integer which has a positive divisor other than one or itself. By definition, every integer greater than one is either a prime number or a composite number. The number one is considered to be neither prime nor composite.

For example,the integer 14 is a composite number because it can be factored as 2 × 7.

The first 15 composite numbers are
4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, and 25.

The firs 5 prime numbers are 2,3,5,7,11

Problem Description:I have find many programs which find the prime numbers or gives you whether the number is prime or not, or gives collection of numbers which are prime from the given number range but the problem in those programs are very slow and becomes Massey (and also sometimes hang your system)when you give the large number 100000 to find out prime number up to that number.

one of my colleague name mayur has suggested algorithm of find the prime numbers by the fastest way.The algorithm of Sieve of Eratosthenes pleast visit here.

C# code for that algorithm is given below.Try it and compare it with your program.

using System.Collections;

int range= 1000000;
BitArray numbers = new BitArray(range, true);

for(int i = 2; i < range; i++)
if(numbers[i])
{
for(int j = i * 2; j < range; j += i)
numbers[j] = false;
}

int primes = 0;

for(int i = 1; i < range; i++)
if(numbers[i])
{
primes++;
//Console.Out.WriteLine(i);
}

Console.Out.WriteLine();
Console.Out.WriteLine(primes + " out of " + range + " prime numbers found.");
Console.In.ReadLine();

The Older and simple program which was done in my school days.


ArrayList primeList = new ArrayList();

for(int i = 2; i < 100; i++)
{
bool divisible = false;

foreach(int number in primeList)
if(i % number == 0)
divisible = true;

if(divisible == false)
primeList.Add(i);
}

If you dare to beat above program then pleas visit this and send me your program after implementation best of luck guys.