@ram
you are generating wrong primes, look:
if (n > Math.Sqrt(n))
there the square root of n will always be smaller than n. you got to
write Num instead of n, like this:
if (n > Math.Sqrt(Num))
by the way I can clearly see that your so called "highest prime":
15493305 is actually divisible by 5...
oh, dear, ram... don't cheat me!
Any way, I took your aproach, and created a really faster algorithm.
Actually I need the code I did above was for a situation where space
complexity needed to be O(c).
ok... optimized until its nails.
-----------------------------
CPU: Intel Pentiun 4 2.26GHz
Cores: 1
RAM: 768MB
OS: Windows XP Professional SP3
.Net: 3.5
Number of primes in 10 seconds: 530448
Highest Prime is: 7851709
-----------------------------
Give me my prize! >_<
-----------------------------
using System;
using System.Diagnostics;
using System.Collections.Generic;
namespace Primes
{
class Program
{
const int seconds = 10; //a const is faster than a variable
[DebuggerNonUserCode()]
static void Main(string[] args)
{
DateTime x, y = DateTime.Now;
primes[0] = 2.0;
primes[1] = 3.0;
int a = 5;
do
{
//this never tests factors of 2 or 3
IsPrim(a);
IsPrim(a+=2);
a+=4;
x = DateTime.Now;
} while ((x - y).TotalSeconds < seconds);
Console.WriteLine((L + 1).ToString() + " primes founds in
" + seconds + " seconds");
Console.WriteLine("Highest Prime is: " + primes[L].ToString
());
Console.WriteLine("Checking for integrity...");
for (int I = 0; I < L + 1; I++)
{
if (!OldIsPrim(primes[I])) Console.WriteLine
("ERROR"); //you'll never see this in the console
}
Console.WriteLine("DONE");
Console.ReadKey();
}
static double R = 1, T = 1; static int L = 1;
static double[] primes = new double[999999]; //a vector is
faster than a list, increase the side if needed
[DebuggerNonUserCode()]
static bool IsPrim(double Num) //don't use Num <= 2
{
if (R < Num) R = ++T * T; //why to do sqrt, there are
faster things
double J;
int I = 2; //it is not taking factors of 2 or 3
for (; ; )
{
if (I > L || (J = primes[I++]) > T) break; //increment
returns, don't waste it
if (Num % J == 0) return false;
}
primes[++L] = Num;
return true;
}
//----------------------
[DebuggerNonUserCode()]
static bool OldIsPrim(double Num)
{
if (Num == 2 ||Num == 3) return true;
if (Num % 2 == 0 || Num % 3 == 0) return false;
double J, H = Math.Ceiling(Math.Sqrt(Num));
for (J = 5; J <= H; J+=6)
if (Num % J == 0 || Num % J+2 == 0)
return false;
return true;
}
}
}
