@Theraot
I haven't looked much into the methods, but I guess its time I
revealed my results:
CPU: Intel Q6600
Cores: 4
RAM: 3GB
OS: Vista Home Premium
.Net: 3.5
Number of primes in 10 seconds: 1,699,203
Highest Prime found: 27,047,651
@Theraot
Your algorithm would be faster than mine I think, but my
implementation is somewhat different.
@ram
Your logic is right, it would be quicker to see if the number being
tested has any previous primes as a factor, however there are two
problems with doing it this way.
1. The overhead of maintaining a list and iterating through it is
quite high
2. You can't maintain a good list when using a multithreaded approach.
If you want to test my code, try fiddling with the arrays near the
top, you can use them to get the best results from your system.
It reruns the test with each combination from this array, I picked the
number out that was the highest from my tests.
I also learnt how much of a difference it makes running it in debug /
release mode.
Here is my code:
class Program
{
static Int64 i = 0; //Int64.MaxValue;
static Int64 count = 0;
static Int32 seconds = 10;
static Int64 largest = 0;
static Int32 processors = 8; //Environment.ProcessorCount;
static Int32 runningProcesses = 0;
static Int32 batchSize = 200000;
static Int32 busyWaitTime = 100;
static Boolean async = true;
static System.IO.StreamWriter sr;
static List<Int64> primes;
static void Main(string[] args)
{
#region Test Area
//primes = new List<Int64>();
//for (Int64 i = 3; i < 20; i++)
//{
// if (IsPrime2(i))
// {
// Console.WriteLine(i);
// }
//}
//return;
#endregion
Int32[] processorArray = new Int32[] { 4, 6, 8, 12 };
Int32[] batchSizeArray = new Int32[] { 200000, 1000000,
10000000 };
Int32[] busyWaitTimeArray = new Int32[] { 10, 50, 200 };
sr = new System.IO.StreamWriter(@"C:\temp\primes.txt");
sr.WriteLine("Threads Batch Delay Result");
sr.WriteLine("------- ------- ------
--------------------------------------------------");
foreach (Int32 processorArrayItem in processorArray)
{
processors = processorArrayItem;
foreach (Int32 batchSizeArrayItem in batchSizeArray)
{
batchSize = batchSizeArrayItem;
foreach (Int32 busyWaitTimeArrayItem in
busyWaitTimeArray)
{
busyWaitTime = busyWaitTimeArrayItem;
RunWithSettings();
}
}
}
sr.Flush();
sr.Dispose();
Console.WriteLine("Done");
Console.ReadLine();
}
static void RunWithSettings()
{
//primes = new List<Int64>();
DateTime start = DateTime.Now;
DateTime end = DateTime.Now.AddSeconds(seconds);
System.Threading.ThreadPool.SetMaxThreads(processors,
processors);
i = 2;
count = 0;
//while (count < 10)
while (DateTime.Now < end)
{
if (async)
{
if (runningProcesses < processors)
{
runningProcesses++;
System.Threading.Thread thread = new
System.Threading.Thread(new System.Threading.ParameterizedThreadStart
(CheckNum));
thread.Start(i);
i += batchSize;
}
else
{
System.Threading.Thread.Sleep(busyWaitTime);
}
}
else
{
if (IsPrime2(i))
{
//Console.Write("{0},", i);
//primes.Add(i);
count++;
largest = i;
}
i++;
}
}
String output = String.Format("{0}\t{1}\t{2}\tFound {3}
primes in {4} secs. Largest = {5}", processors, batchSize,
busyWaitTime, count, seconds, largest);
Console.WriteLine(output);
sr.WriteLine(output);
}
static void CheckNum(Object num)
{
Int64 numInt = (Int64)num;
if ((Int64)numInt % 2 == 0) numInt++;
for (Int64 batchNum = numInt; batchNum < numInt +
batchSize; batchNum += 2)
{
if (IsPrime2(batchNum))
{
//Console.Write("{0},", i);
//primes.Add(i);
count++;
largest = batchNum;
}
}
runningProcesses--;
}
static Boolean IsPrime(Int64 num)
{
for (Int64 i = 2; i < (num / 2) + 1; i++)
{
if (num % i == 0)
return false;
}
return true;
}
static Boolean IsPrime2(Int64 num)
{
Int64 largest = num;
if (num % 2 == 0) return false;
Int64 test = 3;
largest = (Int64)Math.Sqrt(num) + 1;
while (test < largest)
//foreach(Int64 test in primes)
{
//Console.WriteLine("num: {0}", num);
//Console.WriteLine("largest: {0}", largest);
//Console.WriteLine("test: {0}", test);
//Console.WriteLine("num % test: {0}", num % test);
//Console.WriteLine("=================");
if (num % test == 0)
return false;
test+=2;
}
return true;
}
}
On 13 Nov, 08:04, Theraot <[EMAIL PROTECTED]> wrote:
> @ram
> I wanted a rematch >_<
>
> you know that there are sequence of numbers and recursive algorithms
> that always match to primes, with certain parameters. I think that's a
> better way to get primes faster, the time to get the next prime would
> be near to O(c). In fact I tried one of those, but because this series
> don't give all the primes (they skip) it reached overflow very quickly
> (around the third second).
>
> And if what you said is becuase the weird look of my last code,
> actually is something to don't touch, it can't be improved, only
> replaced with something better.
>
> If you like the challenges, you can try {http://www.topcoder.com/},
> join and visit the arena.
>
> @CK
> you said you were doing an algorithm too, what do you think of using
> Sophie Germain numbers, or Fermat numbers? I think we will need to use
> a code for long number computation, but you have to say if the
> challenge is worth of it.
