[amry]

assalamualaikum..

di sini terpanggil aku untuk promote kepada kawan2 join website yang bagi satu set soalan cabaran matematik / programming..

secara amnya, idea asas di sebalik cabaran ni ialah dia menyediakan berapa banyak soalan2 programming. tapi lebih kepada nak selesaikan masalah matematik. sehingga saat aku menaip sekarang ni, jumlah masalah yang dia dah post ada sebanyak 118, dan masalah2 tu sentiasa ditambah dari masa ke semasa.

dalam banyak soalan yang diberi, aku baru je jawab berapa kerat, setelah join lama dulu. rating aku sekarang baru 4% genius .. dan perlu diberi perhatian, untuk setiap masalah tu dia ada beri something called "One Minute Rule", yang mana dia kata setiap masalah tu telah direka supaya bila aturcara yang kita buat tu run, algoritma yang baik membolehkan masalah tersebut tu diselesaikan dalam kurang seminit di atas pc yang biasa. dan untuk makluman semua, ada gak aturcara yang aku buat berjaya selesaikan masalah dan dapatkan jawapan betul, tapi hanya setelah membiarkan program yang aku buat tu running satu hari satu malam, so maksudnya algoritma aku tu tak betul laa tu

dia ada sediakan forum di mana orang bleh berdiskusi penyelesaian kepada masalah2 yang diberi, tapi tu hanya boleh masuk setelah kita selesaikan masalah berkenaan. so sukacitanya aku membuka satu topik nak mengajak kawan2 join sama menyahut cabaran dan berdiskusi sesama kita, kalau boleh tanpa merujuk sebarang rujukan programming luar, hanya rujuk luar untuk algoritma matematik yang boleh dicari dan sebagainya.

dengan menyahut cabaran yang diberi, adalah diharap supaya kita semua boleh meningkatkan kemahiran kita dalam bidang programming, menggunakan teknik2 yang tak penah kita guna sebelum ni. mana laa tau, dalam kita duk cari penyelesaian, kita dah sedikit sebanyak menjejakkan kaki dalam bidang AI ke.. (aku penah terpikir nak buat parallel programming, tapi tu clearly dah melawan dia punya one minute rule tu )

so, linknya di sini: Project Euler

[zamri]

Banyak main prime number ni yg aku lomah ni. tak heran la sebab Euler banyak mengeluarkan conjecture berkenaan prime number.

Sebelum korang menjawab soalan dalam website tu, try buat ni dulu:

bina satu program (tak kira apa bahasa korang guna, preferably C/C++) utk menyenaraikan semua prime number dari 1 - 1000.

Kalau dapat, boleh mula jawab soalan2 dalam website tu.

[mbek]

hahahhaa.... dah dekat 1/2 jam aku run script aku utk cari 10001st prime number... heheheh x sudah2... nampak sgt aku nyer algo masih lemah... hehehe

[kureng]

Banyak main prime number ni yg aku lomah ni. tak heran la sebab Euler banyak mengeluarkan conjecture berkenaan prime number.

Sebelum korang menjawab soalan dalam website tu, try buat ni dulu:

bina satu program (tak kira apa bahasa korang guna, preferably C/C++) utk menyenaraikan semua prime number dari 1 - 1000.

Kalau dapat, boleh mula jawab soalan2 dalam website tu.

<{POST_SNAPBACK}>

sini, klik jemcm2 method ada bro...

The first rendition requires 1:23 (one minute 23 seconds) to calculate all primes below ten million

bro mbek, tukar la dlm PERL
yg otai2 .net sila2 kan
yg otai2 php pon sila2 kan juga

This post has been edited by kureng: 01 May 2006 - 07:49 PM

[amry]

hehe sama laa aku .. kebanyakan solution yang aku ada buat pun lebih berat guna teknik proprietary yang aku bangunkan sendiri: BRUTEFORCE, lepas ni nak gi patentkan laa teknik tu

[jEmBaLanG]

sini, klik jemcm2 method ada bro...

The first rendition requires 1:23 (one minute 23 seconds) to calculate all primes below ten million

bro mbek, tukar la dlm PERL
yg otai2 .net sila2 kan 
yg otai2 php pon sila2 kan juga

<{POST_SNAPBACK}>

hoho ni satu cabaran nih.. aku sahut!! tp tgk time gak la eheh..

[efaisal]

Menarik Saya cuba buat 2 soalan awal guna Python (versi 2.3 ke atas saja). Soalan 3 tak sempat nak buat sebab kena buat keje pulak.

CODE

#!/usr/bin/env python

# Soalan 1 : average 0.039s
x, y, num, sum = 3, 5, 1, 0
while num < 1000:
   sum += num * (3 + 5)
   num += 1
print sum

CODE

#!/usr/bin/env python

# Soalan 2 : average 0.039s
def fib(limit):
   a, b = 0, 1
   while b < limit:
       yield b
       a, b = b, a + b

seq, sum = 1000000, 0
fib = fib(seq)
fibnum = fib.next()
while fibnum < seq:
   if fibnum & 1 == 0:
       sum += fibnum
   try:
       fibnum = fib.next()
   except StopIteration:
       break

print sum

Untuk soalan saudara zamri, cari prime number dari 1 hingga 1000, mungkin boleh buat camni:

CODE

#!/usr/bin/env python

# Average: 0.040s
def prime(limit):
   marker, num = {}, 2
   while num <= limit:
       p = marker.pop(num, None)
       if p:
           x = p + num
           while x in marker: x += p
           marker[x] = p
       else :
           marker[num*num] = num
           yield num
       num += 1

cuba = prime(1000)
while True:
   try:
       print cuba.next()
   except StopIteration:
       break

[efaisal]

OK ada kesilapan untuk soalan 1, salah baca soalan

CODE

#!/usr/bin/env python

num, sum = 1, 0
while num < 1000:
   if num % 3 == 0 or num % 5 == 0: sum += num
   num += 1
print sum

[amry]

This is my response to Zamri's challenge. Answered in C# .NET 2.0. Created two functions: BruteForcePrimeNumber & SmarterBruteForcePrimeNumber (for obvious reason )..

[ The average execution time on my laptop ]

BruteForcePrimeNumber: 0.0014264 s
SmarterBruteForcePrimeNumber: 0.0013943 s

Well, that may seem not to much of a difference, so I reexecuted the same code with a bigger range.. so.. here goes....
[ The average execution time for range 1 - 100,000 ]

BruteForcePrimeNumber: 4.4866034 s
SmarterBruteForcePrimeNumber: 0.9691913 s

CODE

using System;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;

namespace Zamri
{
   class Program
   {
       static void Main(string[] args)
       {
           const int start = 2;
           const int end = 100000;

           Stopwatch watch = new Stopwatch();

           watch.Start();
           List<int> bruteForceList = BruteForcePrimeNumber(start, end);
           watch.Stop();
           PrintOutput(bruteForceList, watch);

           watch.Reset();
           watch.Start();
           List<int> smarterBruteForceList = SmarterBruteForcePrimeNumber(start, end);
           watch.Stop();
           PrintOutput(smarterBruteForceList, watch);

           Console.WriteLine("Press any key to quit...");
           Console.ReadKey();
       }

       static void PrintOutput(List<int> list, Stopwatch watch)
       {
           //foreach (int i in list) {
           //    Console.WriteLine(i);
           //}

           Console.WriteLine("Number of prime numbers: {0}", list.Count);
           Console.WriteLine("Timed: {0}", watch.Elapsed);
       }

       static List<int> BruteForcePrimeNumber(int start, int end)
       {
           List<int> listOfPrimeNumbers = new List<int>();

           for (int i = start; i <= end; i++) {
               bool isPrimeNumber = true;

               for (int j = 2; j < i; j++) {
                   if (i % j == 0) {
                       isPrimeNumber = false;
                       break;
                   }
               }

               if (isPrimeNumber) {
                   listOfPrimeNumbers.Add(i);
               }
           }

           return listOfPrimeNumbers;
       }

       static List<int> SmarterBruteForcePrimeNumber(int start, int end)
       {
           List<int> listOfPrimeNumbers = new List<int>();

           for (int i = start; i <= end; i++) {
               bool isPrimeNumber = true;

               int currentNumberToBeCompared = 1;
               foreach (int currentRecordedPrimeNumber in listOfPrimeNumbers) {
                   currentNumberToBeCompared = currentRecordedPrimeNumber;
                   if (i % currentNumberToBeCompared == 0) {
                       isPrimeNumber = false;
                       break;
                   }
               }

               if (isPrimeNumber) {
                   for (int j = currentNumberToBeCompared + 1; j < i; j++) {
                       if (i % j == 0) {
                           isPrimeNumber = false;
                           break;
                       }
                   }
               }

               if (isPrimeNumber) {
                   listOfPrimeNumbers.Add(i);
               }
           }

           return listOfPrimeNumbers;
       }
   }
}

[amry]

As a sidequest, I executed my SmarterBruteForcePrimeNumber (based on Zamri's challenge) to calculate primes under 10 million (as quoted by kureng). This is the result:

Number of prime numbers: 664579
Timed: 01:15:09.4836447

That would read as 1 hour, 15 minutes and 9.4836447 seconds. OK isn't it? Not that 'far' from the the quoted time by kureng (1 minute 23 seconds)

p/s: still thinking of improving the bruteforce algorithm without referring to the link kureng gave, yet....

[zamri]

mmm. that sounds promising. Your OS load (and OS?) and programming language may affect the performance though. I'm thinking to rewrite yours in C and running it on my pc and see the difference.

[amry]

mmm.. speaking about technical specs.

OS: WinXP Pro SP2
CPU: Intel Dual Core 1.83 GHz (just got my laptop)
RAM: 2 GB, 667 MHz

Well, I executed it just before I went to sleep (look at my time of post ), so besides background services etc, the prototype app is the only user app running at that time. And I already thought about the choice of programming language effecting the performance, and reminding myself that there could always be a small performance overhead if .NET start its garbage collection, directly knew that C / C++ would be the best language if performance would be an issue, but not up to the mood to use C++

About CPU load: 50%.. maybe it's the highest it can go for a dual core CPU since the code I wrote is single threaded. I'm going to rewrite a multithreaded code to see whether it will make the CPU go 100%

[efaisal]

mmm. that sounds promising. Your OS load (and OS?) and programming language may affect the performance though. I'm thinking to rewrite yours in C and running it on my pc and see the difference.

<{POST_SNAPBACK}>

Yes, it's very true - OS load, language, hardware all play an important role. Writing in C could be the time. Since the method you're trying to implement is using the brute force, may be during the iteration of number, step the number by 2, afterall "2" is the only even prime number, the rest are all odd number.

BTW, for those not doing coding, my earlier code in Python was using sieve method, not brute force and therefore will have better performance as compared to brute force method, even when you write using C. My benchmark using Pentium Celeron 2.4GHz with 128KB L2 cache (bogomips 4800), 512MB memory, for calculating primes below 10 millions took an average of 45s - and yes that include loading the interpreter - and make use of 45MB of memory

[amry]

yes, the proper mathematical way will always beat the brute force. however, just for fun, I'll be trying to do bruteforce until I get tired of it, to see how far I can go with my logic thinking alone, and my current available knowledge. And the step by 2 idea is just nice, never actually thought of it.

[amry]

[ Solution for Project Euler Problem 1 ]

Basically the same and simple algorithm as used by efaisal, just in C#.

CODE

using System;
using System.Diagnostics;

namespace EulerProblem1
{
   class Program
   {
       static void Main(string[] args)
       {
           Stopwatch watch = new Stopwatch();
           watch.Start();
           int sum = BruteForceSum();
           watch.Stop();

           Console.WriteLine("the sum of all the multiples of 3 or 5 below 1000: {0}", sum);
           Console.WriteLine("Timed: {0}", watch.Elapsed);

           Console.WriteLine("Press any key to quit...");
           Console.ReadKey();
       }

       static int BruteForceSum()
       {
           int sum = 0;
           for (int i = 0; i < 1000; i++) {
               if (i % 3 == 0 || i % 5 == 0) {
                   sum += i;
               }
           }
           return sum;
       }
   }
}

[amry]

[ Solution for Project Euler Problem 2 ]

CODE

using System;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;

namespace EulerProblem2
{
   class Program
   {
       static void Main(string[] args)
       {
           Stopwatch watch = new Stopwatch();

           watch.Start();
           Queue<int> fibonacciQ = new Queue<int>(2);
           fibonacciQ.Enqueue(1);

           const int limit = 1000000;
           int i = 2;
           int sum = 2;

           while (i < limit) {
               fibonacciQ.Enqueue(i);
               i += fibonacciQ.Dequeue();

               if (i % 2 == 0) {
                   sum += i;
               }
           }
           watch.Stop();

           Console.WriteLine("Sum of even numbers: {0}", sum);
           Console.WriteLine("Timed: {0}", watch.Elapsed);

           Console.WriteLine("Press any key to quit...");
           Console.ReadKey();
       }
   }
}

[1kHz]

Yg soalan 2 Fibonacci tu berapa sum dia? Code aku dapat 1089155, tapi aku run amry punya dapat 1089154 ..aku pun tak tahu mana satu betul

CODE

using System;
using System.Diagnostics;

public class MyClass
{
   public static void Main()
   {
       Stopwatch watch = new Stopwatch();
       watch.Start();
       
       int n1 = 1, n2 = 2, n3 = 0;
       long sum = 3;
       
       for (;;)
       {
           n3 = n1 + n2;
           if (n3 >= 1000000) break;
           if (n3 % 2 == 0) sum += n3;
           n1 = n2;
           n2 = n3;
       }
       
       watch.Stop();
       
       Console.WriteLine("Sum: " + sum.ToString());
       Console.WriteLine("Time: " + watch.Elapsed);
       Console.ReadLine();
   }    
}

Code aku brute force versi simple simple kacang menglembu je... tapi ada tak aci sikit, dah tahu sequence number 1 dan 2.

[amry]

Yang aku punye jawapan tu disahkan betul, since post kat website project euler tu dia kata memang betul

plus sila perhatikan soalan dia balik dengan teliti, dia minta hasil tambah nombor2 fibonacci genap sahaja. so mustahil laa kan kalau hasil tambah genap boleh dapat nombor ganjil..

[jEmBaLanG]

Yang aku punye jawapan tu disahkan betul, since post kat website project euler tu dia kata memang betul 

plus sila perhatikan soalan dia balik dengan teliti, dia minta hasil tambah nombor2 fibonacci genap sahaja. so mustahil laa kan kalau hasil tambah genap boleh dapat nombor ganjil.. 

<{POST_SNAPBACK}>

wah korang semangat kental!! bagus... aku gak x buat2 lagi..

This post has been edited by jEmBaLanG: 05 May 2006 - 09:32 PM

[amry]

[ Solution for Project Euler Problem 4 ]

Answer: 993 x 913 = 906609
Timed: 00:00:00.2651859

Skipped Problem 3, unable to produce code which could get the answer in an acceptable time

CODE

using System;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;

namespace EulerProblem4
{
   class Program
   {
       static void Main(string[] args)
       {
           Stopwatch watch = new Stopwatch();
           watch.Start();
           FindPalindrome();
           watch.Stop();

           Console.WriteLine("Timed: {0}", watch.Elapsed);
           Console.WriteLine("Press any key to quit...");
           Console.ReadKey();
       }

       static void FindPalindrome()
       {
           int topResult = 0;
           int topI = 0;
           int topJ = 0;

           for (int i = 999; i >= 100; i--) {
               for (int j = 999; j >= 100; j--) {
                   int result = i * j;
                   if (IsPalindrome(result)) {
                       if (result > topResult) {
                           topResult = result;
                           topI = i;
                           topJ = j;
                       }
                   }
               }
           }

           Console.WriteLine("Answer: {0} x {1} = {2}", topI, topJ, topResult);
       }

       static bool IsPalindrome(int n)
       {
           string nStr = n.ToString();
           int length = nStr.Length;
           bool isPalindrome = true;

           for (int i = 0; i < length / 2; i++) {
               if (nStr[i] != nStr[length - 1 - i]) {
                   isPalindrome = false;
                   break;
               }
           }

           return isPalindrome;
       }
   }
}

[amry]

[ Solution for Project Euler Problem 5 ]

Answer: 232792560
Timed: 00:00:00.5113119

CODE

using System;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;

namespace EulerProblem5
{
   class Program
   {
       static void Main(string[] args)
       {
           int[] divisor = { 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 7 };

           Stopwatch watch = new Stopwatch();
           watch.Start();

           for (int i = 20; true; i += 20) {
               bool canBeDividedByAll = true;
               foreach (int j in divisor) {
                   if (i % j != 0) {
                       canBeDividedByAll = false;
                       break;
                   }
               }

               if (canBeDividedByAll) {
                   Console.WriteLine("Answer: {0}", i);
                   break;
               }
           }

           watch.Stop();
           Console.WriteLine("Timed: {0}", watch.Elapsed);
           Console.WriteLine("Press any key to quit...");
           Console.ReadKey();
       }
   }
}

[amry]

[ Solution for Project Euler Problem 6]

Answer: 25164150
Timed: 00:00:00.0004573

CODE

using System;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;

namespace EulerProblem6
{
   class Program
   {
       static void Main(string[] args)
       {
           const int start = 1;
           const int end = 100;

           Stopwatch watch = new Stopwatch();
           watch.Start();
           int difference = SquareOfSum(start, end) - SumOfSquare(start, end);
           watch.Stop();

           Console.WriteLine("Answer: {0}", difference);
           Console.WriteLine("Timed: {0}", watch.Elapsed);
           Console.WriteLine("Press any key to quit...");
           Console.ReadKey();
       }

       static int SumOfSquare(int start, int end)
       {
           int sum = 0;
           for (int i = start; i <= end; i++) {
               sum += i * i;
           }
           return sum;
       }

       static int SquareOfSum(int start, int end)
       {
           int sum = 0;
           for (int i = start; i <= end; i++) {
               sum += i;
           }
           return sum * sum;
       }
   }
}

[amry]

[ Solution for Project Euler Problem 7 ]

The 10001st prime number: 104743
Timed: 00:00:01.0579313

Based on the SmarterBruteForcePrimeNumber algorithm used in Zamri's challenge, modified to do step 2 courtesy of efaisal.

CODE

using System;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;

namespace EulerProblem7
{
   class Program
   {
       static void Main(string[] args)
       {
           Stopwatch watch = new Stopwatch();
           watch.Start();

           List<int> listOfPrimeNumbers = new List<int>(10001);
           listOfPrimeNumbers.Add(2);

           for (int i = 3; listOfPrimeNumbers.Count != 10001; i += 2) {
               bool isPrimeNumber = true;

               int currentNumberToBeCompared = 2;
               foreach (int currentRecordedPrimeNumber in listOfPrimeNumbers) {
                   currentNumberToBeCompared = currentRecordedPrimeNumber;
                   if (i % currentNumberToBeCompared == 0) {
                       isPrimeNumber = false;
                       break;
                   }
               }

               if (isPrimeNumber) {
                   for (int j = currentNumberToBeCompared + 1; j < i; j += 2) {
                       if (i % j == 0) {
                           isPrimeNumber = false;
                           break;
                       }
                   }
               }

               if (isPrimeNumber) {
                   listOfPrimeNumbers.Add(i);
               }
           }

           watch.Stop();
           Console.WriteLine("The 10001st prime number: {0}", listOfPrimeNumbers[10000]);
           Console.WriteLine("Timed: {0}", watch.Elapsed);
           Console.WriteLine("Press any key to quit...");
           Console.ReadKey();
       }
   }
}

[1kHz]

Yang aku punye jawapan tu disahkan betul, since post kat website project euler tu dia kata memang betul 

plus sila perhatikan soalan dia balik dengan teliti, dia minta hasil tambah nombor2 fibonacci genap sahaja. so mustahil laa kan kalau hasil tambah genap boleh dapat nombor ganjil.. 

<{POST_SNAPBACK}>

Oooh ye lah.. bongok betul lah.. aku tertambah nombor 1 tu, patutnya start dgn 2

[mbek]

hahaha... nampak sgt byk bende dah aku lupa... janjang, kebarangkalian etc... hehehhe ..

** best gak layan bende ni time bosan2... hehehe..
** soalan 1st aku jawab ID #7
it's take me more than 1/2 an hour utk dpt jawapan .... CPU usage dkt 100%. hehehe ... mengong...

[amry]

hahaha... nampak sgt byk bende dah aku lupa... janjang, kebarangkalian etc... hehehhe ..

** best gak layan bende ni time bosan2... hehehe..
** soalan 1st aku jawab ID #7
it's take me more than 1/2 an hour utk dpt jawapan .... CPU usage dkt 100%. hehehe ... mengong...

<{POST_SNAPBACK}>

mathematical problem dia most probably akan buat CPU 100% lebih2 lagi kepada sesiapa yang pakai brute force, dan biasa juga laa kena pikir beberapa lama sikit sebelum buat solution.

[amry]

[ Solution for Project Euler Problem 8 ]

Greatest product: 40824
Time: 00:00:00.0004763

Project setup steps (assuming use VS2005 / VS Express)
1. Create a new text file inside project, named 'numbers.txt'.
2. Have that file to be an embedded resource by right-clicking it and choose Properties, and set its Build Action property to Embedded Resource.
3. Include the following content into the file:

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

4. If you create a project with other name than 'EulerProject8', then its default namespace is going to be the project's name and you should change the "EulerProject8.numbers.txt" in the code to "<whatever you default namespace is>.numbers.txt".

CODE

using System;
using System.Collections.Generic;
using System.Text;
using System.Reflection;
using System.IO;
using System.Diagnostics;

namespace EulerProblem8
{
   class Program
   {
       static void Main(string[] args)
       {
           Stopwatch watch = new Stopwatch();
           watch.Start();

           string numberString;
           using (StreamReader reader = new StreamReader(
               Assembly.GetExecutingAssembly().GetManifestResourceStream("EulerProblem8.numbers.txt"))) {
               numberString = reader.ReadToEnd();
           }

           List<int> numbers = new List<int>();
           foreach (char c in numberString) {
               if (c >= '0' && c <= '9') {
                   numbers.Add(Int32.Parse(c.ToString()));
               }
           }

           int greatestProduct = 0;
           for (int i = 0; i < numbers.Count - 5; i++) {
               int currentProduct = 1;
               for (int j = 0; j < 5; j++) {
                   currentProduct *= numbers[i + j];
               }

               if (currentProduct > greatestProduct) {
                   greatestProduct = currentProduct;
               }
           }

           watch.Stop();
           Console.WriteLine("Greatest product: {0}", greatestProduct);
           Console.WriteLine("Time: {0}", watch.Elapsed);
           Console.WriteLine("Press any key to quit...");
           Console.ReadKey();
       }
   }
}

[amry]

[ Solution for Project Euler Problem 9 ]

Answer: 31875000
Time: 00:00:00.0010632

CODE

using System;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;

namespace EulerProblem9
{
   class Program
   {
       static void Main(string[] args)
       {
           Stopwatch watch = new Stopwatch();
           watch.Start();
           int answer = CalculateAnswer();
           watch.Stop();

           Console.WriteLine("Answer: {0}", answer);
           Console.WriteLine("Time: {0}", watch.Elapsed);
           Console.WriteLine("Press any key to quit...");
           Console.ReadKey();
       }

       static int CalculateAnswer()
       {
           for (int c = 997;; c--) {
               int b = 999 - c;
               int a = 1;

               while (a < b) {
                   if (a * a + b * b == c * c) {
                       return a * b * c;
                   } else {
                       a++;
                       b--;
                   }
               }
           }
       }
   }
}

[amry]

[ Solution for Project Euler Problem 10 ]

Sum: 37550402023
Time: 00:00:18.0270852

Sum: 37550402023
Time: 00:00:09.2108474

Peak Private Bytes: 22,688 K
Peak Working Set: 14,936 K

Setakat ni, code ni yang paling cepat selesaikan masalah prime number secara brute force, jauh lebih cepat dari code2 yang aku hasilkan sebelum ni. Dan aku buat multithread untuk menguji kebolehan processor dual core. So masalah utama yang dihadapi bila buat multithread ni tidak lain dan tidak bukan: synchronization issue. Code yang dah dihasilkan ni kalau run guna 1 thread then insyaAllah result yang diperolehi reliable, tapi kalau guna lebih 1 thread then ada kemungkinan (walaupun aku tak pernah lagi hadapi) result yang dihasilkan salah.

Masalah yang paling besar disebabkan dengan algoritma di mana nombor perdana yang dah dijumpai ditambahkan ke dalam senarai tanpa kawalan. Maksudnya ada kemungkinan nombor yang ditambah tu tak ikut susunan sekiranya execution multithreaded. Dah cuba menggunakan SortedList instead of List, tapi dia punye performance hit bila guna SortedList tu quite tinggi. Ada gak cuba kaedah sieve yang efaisal cakap tu, cari kat internet berdasarkan, dan berdasarkan kefahaman sendiri yang mungkin dah salah faham tu, code yang aku buat makan memori gila punya banyak, so break tengah jalan tolak code tu ketepi.

So code yang aku gunakan ada dua file, yang pertama Program.cs dan yang kedua MultiThreadedBruteForceMethod.cs. Boleh digabungkan jadi satu kalau nak.

CODE

using System;
using System.Diagnostics;

namespace EulerProblem10
{
   class Program
   {
       static void Main(string[] args)
       {
           Stopwatch watch = new Stopwatch();
           watch.Start();

           //
           // 2nd parameter determines the number of thread being used.
           // Set to Environment.ProcessorCount so that this program can make use of full processor power.
           //
           MultiThreadedBruteForceMethod t = new MultiThreadedBruteForceMethod(1000000, Environment.ProcessorCount);
           t.Start();

           watch.Stop();
           Console.WriteLine("Sum: {0}", t.SumOfPrimeNumbers);
           Console.WriteLine("Time: {0}", watch.Elapsed);

           Console.WriteLine("Press any key to quit...");
           Console.ReadKey();
       }
   }
}

CODE

using System;
using System.Collections.Generic;
using System.Text;
using System.Runtime.CompilerServices;
using System.Threading;
using System.Diagnostics;
using System.Collections;

namespace EulerProblem10
{
   class MultiThreadedBruteForceMethod
   {
       readonly List<int> listOfPrimeNumbers = new List<int>();
       readonly int max;
       readonly int nThreads;
       int currentNumber;
       long sum;

       public MultiThreadedBruteForceMethod(int max)
           : this(max, 1)
       { }

       public MultiThreadedBruteForceMethod(int max, int numberOfThreads)
       {
           this.max = max;
           this.nThreads = numberOfThreads;
       }

       public void Start()
       {
           currentNumber = 1;
           sum = 2;

           listOfPrimeNumbers.Clear();
           listOfPrimeNumbers.Add(2);

           EventWaitHandle[] waitHandles = new EventWaitHandle[nThreads];
           Thread[] threads = new Thread[nThreads];

           for (int i = 0; i < nThreads; i++) {
               waitHandles[i] = new ManualResetEvent(false);
               threads[i] = new Thread(new ParameterizedThreadStart(Process));
               threads[i].Start(waitHandles[i]);
           }

           WaitHandle.WaitAll(waitHandles);
       }

       public long SumOfPrimeNumbers
       {
           get { return sum; }
       }

       int NextNumber
       {
           get { return Interlocked.Add(ref currentNumber, 2); }
       }

       void Process(object waitHandle)
       {
           int i = NextNumber;
           while (i < max) {
               Subprocess(i);
               i = NextNumber;
           }

           ((EventWaitHandle) waitHandle).Set();
       }

       void Subprocess(int x)
       {
           int divisor = 0;
           for (int i = 1; i < listOfPrimeNumbers.Count && divisor * 4 < x; i++) {
               divisor = listOfPrimeNumbers[i];
               if (x % divisor == 0) {
                   return;
               }
           }

           for (divisor += 2; divisor * 4 < x; divisor += 2) {
               if (x % divisor == 0) {
                   return;
               }
           }

           RegisterPrimeNumber(x);
       }

       void RegisterPrimeNumber(int i)
       {
           lock (listOfPrimeNumbers) {
               listOfPrimeNumbers.Add(i);
           }
           Interlocked.Add(ref sum, i);
       }
   }
}

[amry]

Menggunakan aturcara yang sama seperti di atas, masalah nak selesaikan nombor perdana bawah 10 juta telah dikurangkan seperti berikut berbanding daripada masa asal (walaupun masih lagi jauh dari 1 minit )

1 Thread
Sum: 3203324994356
Time: 00:20:30.2352779

2 Threads
Sum: 3203324994356
Time: 00:10:45.4913160

[kkmka90]

Hrm.. menarik tul.

ade try sikit.

CODE

#!/usr/bin/python
# http://mathschallenge.net/
# Problem 1
import time

now = time.clock()
sum = 0
for i in range(1, 1000):
 if (i % 3 == 0) or (i % 5 == 0):
   sum = sum + i
then = time.clock()  
print sum, " in ", then - now, " ms"

Pagi nanti sambung.

[Mi-G]

aku ade masalah la nak paham soalan2 dlm BI nih...sape2 leh tolong terangkan kat aku...

Problem 1

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

aku c++ programmer...actually beginner baru la...so, ni baru problem 1 nih...kalo xdpt jawab..malu oooo..hehe

[amry]

Masalah 1

Jika kita senaraikan kesemua nombor bawah 10 yang merupakan gandaan 3 atau 5, kita akan dapat 3, 5, 6 dan 9. Jumlah kesemua nombor gandaan tersebut ialah 23.

Cari jumlah kesemua nombor gandaan 3 atau 5 bawah 1000.

[Mi-G]

Masalah 1

Jika kita senaraikan kesemua nombor bawah 10 yang merupakan gandaan 3 atau 5, kita akan dapat 3, 5, 6 dan 9. Jumlah kesemua nombor gandaan tersebut ialah 23.

Cari jumlah kesemua nombor gandaan 3 atau 5 bawah 1000.

saya ada masalah dengan soalan dlm problem 1 nih...saya xtau ape masalahnye...syntax tu bile saya run...saya buat gandaan tu bawah 10...betul mcm example yang diorang bagi...tp bile saya masukkan bawah 1000 salah pulak jawapan die....ni tatau ape yg nak diperbetulkan...rase2 xde ape2 yg salah....

kalau saya paste syntax tu kat sini xde hal kan...lagipun problem 1 tu ramai org bleh jawap...cume saye ni je hah...terkial kial lagi..ahaks....

CODE

#include<iostream.h>
#include<conio.h>

main()
{
   int counter = 1,Multi_3 = 3,Multi_5 = 5,sum_1 = 0,sum_2 = 0;
   int total,total_3 = 0,total_5 = 0;
   int ans;

   cout<<"\t\t\tMathschallenge.net Problem - 1" <<endl;
     cout<<"============================================================================
=" <<endl;
   cout<<"\nFind the sum of all the multiples of 3 or 5 below ? : ";
   cin>>ans;

   while (counter < ans)
   {     sum_1 += Multi_3;
         sum_2 += Multi_5;

   if (sum_1 < ans)
   {    cout<<"Number of Multiples of 3 <" <<counter <<"> = " <<sum_1 <<endl;
       total_3 += sum_1;
   }
      if (sum_2 < ans)
   {    cout<<"Number of Multiples of 5 <" <<counter <<"> = " <<sum_2 <<endl;
      total_5 += sum_2;
   }

   total = total_3 + total_5;
   counter++;
   }

   cout<<"\nThe Sum Is : " <<total;

   getch();
   return 0;
}

lari sket bile paste....x dan plak nak edit...
saya ni baru lagi dlm programming...baru blajar takat loop ni ....so ni mane2 yg sudi nak tolong...sila silalah...
baru tadi berjaya jawap problem 2...hahaha jadi lah....untuk 'kickstart' dlm challenge nih....

[amry]

kesilapan yang dibuat berkaitan dengan pemahaman soalan matematik dia.

gandaan 3 dan 5 bawah 10:
3: 3, 6, 9
5: 5

cuba gandaan 3 dan 5 bawah 20:
3: 3, 6, 9, 12, 15, 18
5: 5, 10, 15

agak2 apa silap dia? yang ni sila fikirkan sendiri.

p/s: kalau simply nak kira sum of numbers baik guna rumus matematik Sn = n/2 * (2a + (n - 1) d).

-----------

next nasihat dari aspek cara pengaturcaraan pula.

apa kegunaan variable multi_3 dan multi_5 di situ? kalau sekadar nak dijadikan constant, sebaiknya define as const int multi_3 = 3 contohnya. tapi constant untuk nombor biasa yang mudah ditulis baik tak payah. kalau nak define constant contohnya macam const double pi = 3.1428571428571428571428571428571 tu ye la gak, sebab nombor tu susah nak diingat dan ditaip berulang kali.

[Mi-G]

ooo baru paham...tu pesel le jawapan asik salah jer...ok thanx bro

[Mi-G]

nih ade soalan2 yg saye xbrape paham....

Problem 2

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Find the sum of all the even terms in the sequence below one million.

'even term' yg disebutkan tu bukan ke nombor genap ? ...saye dah buah spt yg saye paham la...tambahkan semua nombor genap dlm fibonacci sequence bawah 1 juta...bile masukkan sbg jawapan dlm website xbleh plak....salah !!
ape sebenarnye yg die nak ni....bukan nak minta jawapan, terangkan lebih sket, bg saye paham....

Problem 20

n! means n × (n − 1) × ... × 3 × 2 × 1

Find the sum of the digits in the number 100!

utk soalan ni...saye baru je mule tadi...tp macam biase la...xpaham je memanjang...'factorial' saye paham ...tp bile die ckp "find the sum of the digits in the number 100!." tu yg wat confuse tu....

lari sket bile paste....x dan plak nak edit...
saya ni baru lagi dlm programming...baru blajar takat loop ni ....so ni mane2 yg sudi nak tolong...sila silalah...
baru tadi berjaya jawap problem 2...hahaha jadi lah....untuk 'kickstart' dlm challenge nih....

bukan problem 2...problem 6...silap plak

[amry]

Untuk problem fibonaci tu dah betul la pemahaman tu.
Untuk problem factorial tu, dapatkan result bagi 100!.. pastu jumlahkan setiap digit dalam result tu.

[Mi-G]

jadik betul la logic saye utk soalan fibonacci tu..tp yg confuse apsal salah jwpn saye...hmmm nnt la check balik...salah data type la agaknye...saye letak unsigned int ....sbb result die berpuluh juta...
tp utk soalan factorial tu confirm bleh jawap malam ni... thanx

[amry]

kalau result berpuluh juta tu jauh tersasar tu.. sebab jawapan dia: 1089154 .. dan penggunaan unsigned int tu patut bukan pembawa masalah. assuming kalau unsigned int tu 16 bit mungkin la jadi masalah overflow, tapinya kalau dah jawapan bleh cecah ke puluh juta tu dah ok dah tu. so agaknya most probably ada silap pada aturcara.

[Mi-G]

saye buat coding utk process saye mcm ni...

CODE

cout<<"\n\n\nEnter How Many Number Of Fibonacci Sequence Will Be Printed : ";
   cin>>ask;

   while (i < ask)
  {      FirstNum += SecNum;
          cout<<"\nFibonacci number " <<Num_1 <<" is : "  <<FirstNum;
          Num_1++;
          SecNum += FirstNum;
          cout<<"\nFibonacci number " <<Num_1 <<" is : "  <<SecNum;
          Num_1++;

          if (FirstNum % 2 == 0)             // test whether 'FirstNum' is an even number
             sum1 += FirstNum;             // if 'yes' calculate the sum
          else
               if (SecNum % 2 == 0)       // test whether 'SecNum' is an even number
               sum2 += SecNum;           // " "

            
          i += 2;
  }

   sum = sum1 + sum2;
   cout<<"\n\nThe sum of all the even term is : " <<sum;

kalau test display nombor fibonacci bawah 10 - 20 betul ....bawah no. yg besar2 mesti salah....tang mane yang silap tu ek....
jawapn die xla sampai puluh2 juta...tp yg saye dpt gune coding saye ni...ade la dlm 24 juta lebih....ehehehe

[amry]

fragment aturcara tu tak cukup nak check apa yang silap. for the time being try trace dulu. step instruction by instruction dan tengok sama ada flow aturcara tu seperti yang dijangka ke tak. kalau dah tak dapat gak then paste code penuh.

[Mi-G]

sebelum ni xpenah sum nombor besar2 ni...paling kuat pun 100 jer...main pandai2 sendiri je kat umah, ok bro nnt saye check balik.

[offtopic]
tadi tanye lecturer ttg problem 20...same gak die pikir mcm saye...gantikan darab ngan tambah jer..
[/offtopic]

[jEmBaLanG]

Problem#2
baru ari ni aku berpeluang buat math challenge tu..
walaupun dah basi.. tapi aku buat jek lah..

CODE

class Program
    {
        static void Main( string[] args )
        {
            Console.Write( "Enter value: " );
            int valueEntered = 0;

            valueEntered = Convert.ToInt32( Console.ReadLine() );
            Console.WriteLine( "Processing, please wait" );

            FibonacciProblemSolver fibonacciSolver = new FibonacciProblemSolver();
            Stopwatch timer = new Stopwatch();

            timer.Start();
            fibonacciSolver.Process( valueEntered );
            timer.Stop();

            Console.WriteLine( "" );
            Console.WriteLine( "Even Sum: {0}", fibonacciSolver.Sum );
            Console.WriteLine( "Time taken: {0} ms", timer.Elapsed );
        }
    }

FibonacciProblemSolver class

CODE

public class FibonacciProblemSolver
    {
        private Queue m_queue;
        private int m_sum;

        public FibonacciProblemSolver()
        {
        }
        public void Process( int value )
        {
            m_queue = new Queue( (int)value );

            int answer = 0;
            int first = 1;
            int second = 2;

            while ( answer < value )
            {
                if ( first == 1 )
                {
                    m_queue.Enqueue( first );
                }

                if ( second == 2 )
                {
                    m_queue.Enqueue( second );
                }

                answer = first + second;
                m_queue.Enqueue( answer );
                first = second;
                second = answer;
            }

            // reserve queue list for future use. thus use IEnumerator interface to
            // iterate through the queue
            // can slow down the performance a bit, but still acceptable even till 1,000,000 numbers
            IEnumerator enumerator = m_queue.GetEnumerator();
            while ( enumerator.MoveNext() )
            {
                if ( IsEvenNumber( (int)enumerator.Current ) )
                {
                    m_sum += (int)enumerator.Current;
                }
            }
        }
        private bool IsEvenNumber( int value )
        {
            if ( value % 2 == 0 )
                return true;
            return false;
        }

        /// <summary>
        /// Gets the even terms summation
        /// </summary>
        public int Sum
        {
            get
            {
                return m_sum;
            }
        }
        public Queue QueueList
        {
            get { return m_queue; }
        }
    }

[jEmBaLanG]

Problem 3

Berikut adalah jawapan untuk Problem#3. Amry ko tolong test ek.. aku tak tau betul ke tak, tapi tu la jawapan yg dpt.. Kawan2 yg lain pun test gak la.. salah ckp.. aku nak tgk algo aku betui ke tak...
mekacih!!

program terbahagi kepada 3 classes
1. Program
2. LargestPrimeFactorBase
3. LPFQueue

Sungguhpun pakai LPFQueue, actually tak utilise pun penggunaan queue. Mula2 niat aku nak buat analysis between data structures yg terdapat dalam .NET 2.0. Aku mula2 nak buat analysis on Generic Queue, Queue, LinkedList ArrayList and HashTable. Tapi I'll let u all sambungkan.. thats why ada LargestPrimeFactorBase class.

Ini result yg aku perolehi setelah run program kat bawah ni..

What is the largest prime factor of the number 317584931803?
Jawapan: 3919

Program output:

CODE

Data structure type to use: Q (Queue), QG (Queue Generics):
>>q
Enter value:
>>317584931803

Using LPFQueue
Answer:  67 829 1459 3919
Time taken: 00:00:00.0008724 ms

Result kat atas dirunkan di office... kat umah mlm kang kot aku runkan..

Machine Specification: (Office)
Windows XP SP2, .NET Framework 2.0,
Single Intel Pentium 4 3.2Ghz with HT Technology
2GB RAM.

Machine Specification: (Kat rumah) This pc is 5 years old but still ROKKK!!! IDUP AMD!! wuhooo!!! \:D/
Windows XP SP2, .NET Framework 2.0,
AMD Athlon Thunderbird 1.1Ghz
512MB RAM

CODE

class Program
    {
        static void Main( string[] args )
        {
            string text = string.Empty;
            string typeInput = string.Empty;
            ulong value = 0;

            Console.WriteLine( "Data structure type to use: Q (Queue), QG (Queue Generics):" );
            Console.Write( ">>" );
            typeInput = Console.ReadLine();

            LargestPrimeFactorBase lpfbase = GetDataStructureType( typeInput, out text );

            Console.WriteLine( "Enter value:" );
            Console.Write( ">>" );
            string temp = Console.ReadLine();
            ulong.TryParse( temp, out value );

            Console.WriteLine( );
            Console.WriteLine( text );
            Stopwatch timer = new Stopwatch();
            timer.Start();
            lpfbase.Process( value );
            timer.Stop();

            Console.WriteLine( "Answer: {0}", lpfbase.List);
            Console.WriteLine( "Time taken: {0} ms", timer.Elapsed );

        }

        internal static LargestPrimeFactorBase GetDataStructureType(string type, out string text)
        {
            text = string.Empty;
            if ( type == "Q" || type == "q" )
            {
                text = "Using LPFQueue";
                return new LPFQueue();
            }
            if ( type == "QG" || type == "qg" )
            {
                text = "Using Queue Generics";
                return null; // not implemented yet!
            }

            return null;
        }
    }

LargestPrimeFactorBase...

CODE

public class LargestPrimeFactorBase
    {
        public LargestPrimeFactorBase()
        {
        }

        public virtual void Process( ulong value )
        {
        }

        public virtual object Answer
        {
            get
            {
                return 0;
            }
        }
        public virtual string List
        {
            get { return string.Empty; }
        }
    }

LPFQueue...

CODE

public class LPFQueue : LargestPrimeFactorBase
    {
        private Queue m_queue;
        private ulong m_answer = 1;

        public LPFQueue()
        {
        }

        public override void Process( ulong value )
        {
            m_queue = new Queue();

            for ( ulong i = 2; i <  value; i++ )
            {
                if ( value % i == 0 )
                {
                    m_queue.Enqueue( i );
                    m_answer *= i;

                    if ( m_answer == value )
                        break;
                }
            }

            base.Process( value );
        }
        public override object Answer
        {
            get
            {
                return m_answer;
            }
        }
        public override string List
        {
            get
            {
                string list = string.Empty;
                IEnumerator enumerator = m_queue.GetEnumerator();
                while ( enumerator.MoveNext() )
                {
                    list += " " + enumerator.Current;
                }

                return list;

            }
        }
    }

comments are welcomed!

[amry]

[ Solution for Project Euler Problem 3 ]

Input : 317584931803
List : 67 829 1459 3919
Prime List : 67 829 1459 3919
LPF : 3919
Timed : 00:00:00.0023785

Penyelesaian courtesy yang teramat sangat oleh bro jembalang. walaupun dia kata dia pun tak tau camne dia dapat algoritma tersebut dan dia tak ngaku yang dia ada potensi tersembunyi nak jadi ahli matematik, jutaan terima kasih aku ucapkan. aku dah modify sikit2 code dia bagi membetulkan flaw yang telah dikenalpasti.

Ni file program.cs aku:

CODE

using System;
using System.Diagnostics;

namespace EulerProblem3
{
    class Program
    {
        static void Main()
        {
            const ulong max = 317584931803;
            Stopwatch stopwatch = Stopwatch.StartNew();

            LPFQueue lpf = new LPFQueue();
            lpf.Process(max);

            stopwatch.Stop();

            Console.WriteLine("Input      : {0}", max);
            Console.WriteLine("List       : {0}", lpf.ToListString());
            Console.WriteLine("Prime List : {0}", lpf.ToPrimeListString());
            Console.WriteLine("LPF        : {0}", lpf.LargestPrimeNumber);
            Console.WriteLine("Timed      : {0}", stopwatch.Elapsed);
            Console.ReadKey();
        }
    }
}

Dan ini pula file LPFQueue.cs yang aku dah modify dari jembalang punye:

CODE

using System;
using System.Collections.Generic;
using System.Text;

namespace EulerProblem3
{
    public class LPFQueue
    {
        List<ulong> m_list;
        List<ulong> m_primeList;
        ulong m_answer = 1;

        public void Process(ulong value)
        {
            m_list = new List<ulong>();

            for (ulong i = 2; i < value; i++) {
                if (value % i == 0) {
                    m_answer *= i;

                    if (m_answer == value) {
                        m_list.Add(i);
                        break;
                    } else if (m_answer > value) {
                        break;
                    } else {
                        m_list.Add(i);
                    }
                }
            }

            GeneratePrimeList();
        }

        void GeneratePrimeList()
        {
            m_primeList = new List<ulong>();
            foreach (ulong i in m_list) {
                if (i == 2) {
                    m_primeList.Add(i);
                } else {
                    if (IsPrimeNumber(i)) {
                        m_primeList.Add(i);
                    }
                }
            }
        }

        bool IsPrimeNumber(ulong i)
        {
            foreach (ulong j in m_primeList) {
                if (i % j == 0) {
                    return false;
                }
            }

            return true;
        }

        public ulong Answer
        {
            get { return m_answer; }
        }

        public List<ulong> List
        {
            get { return m_list; }
        }

        public ulong LargestPrimeNumber
        {
            get
            {
                if (m_primeList.Count > 0) {
                    return m_primeList[m_primeList.Count - 1];
                } else {
                    throw new Exception("Input dia tu pun prime number daa..");
                }
            }
        }

        public List<ulong> PrimeList
        {
            get { return m_primeList; }
        }

        public string ToListString()
        {
            StringBuilder listBuilder = new StringBuilder();
            foreach (ulong i in m_list) {
                listBuilder.AppendFormat("{0} ", i);
            }

            return listBuilder.ToString();
        }

        public string ToPrimeListString()
        {
            StringBuilder listBuilder = new StringBuilder();
            foreach (ulong i in m_primeList) {
                listBuilder.AppendFormat("{0} ", i);
            }

            return listBuilder.ToString();
        }
    }
}

[amry]

[ Remake: Solution for Project Euler Problem 10 Mega Hyper Ultra Reloaded Version ]

sekiranya dilihat pada saya punya solution 10 yang telah dipos sebelum ni, masa yang diambil bagi menyelesaikan masalah ni ~18 saat. setelah semangat saya membara melihat mr. jembalang pos code dia kat topik ni, maka saya telah review balik sume code2 saya sebelum ni. dan dengan ini sukacitanya saya maklumkan bahawasanya code bagi solution ni saya telah berjaya cutdown masa dia sehinggakan output dia menunjukkan:

Sum: 37550402023
Time: 00:00:00.0426274

Kaedah sieving digunakan dalam aturcara kali ni, dengan BitArray digunakan untuk rekodkan nombor yang telah disievekan. nampak gaya sangat cepat processing BitArray ni, aku rasa underlying dia maybe dia pakai raw bits kot, tu yang boleh laju sampai camtu. tapi anyway tu hanya andaian saya, whatever happens under the hood tidak kutahu.

Codenya seperti berikut:

CODE

using System;
using System.Collections;
using System.Diagnostics;

namespace EulerProblem10
{
    class Program
    {
        static void Main(string[] args)
        {
            Stopwatch watch = new Stopwatch();
            watch.Start();

            BitArray bits = new BitArray(500000, true);
            bits[0] = false;
            
            for (int i = 3; i <= 1000000; i += 2) {
                if (bits[(i - 1) / 2]) {
                    for (int j = i * 3; j <= max; j += i * 2) {
                        int k = (j - 1) / 2;
                        bits[k] = false;
                    }
                }
            }

            ulong sum = 2;
            for (int i = 1; i < 500000; i++) {
                if (bits[i]) {
                    sum += (ulong)i * 2 + 1;
                }
            }

            watch.Stop();
            Console.WriteLine("Sum: {0}", sum);
            Console.WriteLine("Time: {0}", watch.Elapsed);

            Console.WriteLine("Press any key to quit...");
            Console.ReadKey();
        }
    }
}

[amry]

sini, klik jemcm2 method ada bro...

The first rendition requires 1:23 (one minute 23 seconds) to calculate all primes below ten million

bro mbek, tukar la dlm PERL
yg otai2 .net sila2 kan
yg otai2 php pon sila2 kan juga

merujuk kepada cabaran ni, dalam posting2 aku sebelum ni yang berkaitan dengan cabaran tersebut, aku dapat result seperti berikut:

Number of prime numbers: 664579
Timed: 01:15:09.4836447

dan kemudian aku upgrade lagi code aku, menghasilkan result seperti berikut:

1 Thread
Sum: 3203324994356
Time: 00:20:30.2352779

2 Threads
Sum: 3203324994356
Time: 00:10:45.4913160

dan kini, setelah aku update lagi code yang aku guna untuk Problem 10 seperti di atas, aku try lagi untuk mencabar masa 1 minit 23 saat yang dijumpai oleh saudara kureng. so inilah result dia:

Sum: 3203324994356
Time: 00:00:00.4483882

Result yang diperolehi bagi mengira hasiltambah kesemua nombor perdana bawah 10 juta dapat diselesaikan dalam masa kurang sesaat.

[jEmBaLanG]

Problem#3
OK ni nak balas pantun amry..

Setelah dienhancekan/difixkan sebegitu jitu (chewahh) dan pelbagai pandangan dan diskusi telah diadakan dengan amry melalui YM, ini dia result yg diperoleh...

Test asal utk Problem 3 MathChallenge.net adalah dgn menggunakan data 317584931803. Tapi utk memanjangkan lagi masa processing, aku pakai data sendiri iaitu 889338121.
Data yg sama telah dijalankan oleh amry dengan menggunakan algorithmnya yg telah difinetunekan bayekkknye!

Berikut adalah hasil test cases yg telah dijalankan dgn algorithm aku atas dual core notebook amry yg berdedssssuuuutt laju itu

Using LPFQueue
Using LPFQueueTest Data: 889338121
Answer: 7 127048303
Time taken: 00:00:15.6263927 ms

Using Arraylist
Using ArraylistTest Data: 889338121
Answer: 7 127048303
Time taken: 00:00:15.6565636 ms

Using Generic List
Using Generic ListTest Data: 889338121
Answer: 7 127048303
Time taken: 00:00:15.6969279 ms

Using Generic Queue
Using Generic QueueTest Data: 889338121
Answer: 7 127048303
Time taken: 00:00:15.7983956 ms

Aku tambah lagi 3 set of collection class utk buat berbandingan. Tapi disebabkan terlalu panjang, so aku amik ArrayList dan GenericQueue sahaja. Setelah test kat machine aku dan ofc aku, terbukti ArrayList remains the top contender. In most test cases, arraylist will be either on top or second in terms of performance. Aku hanya test semasa result disavekan ke dalam collection masing2. Dalam kes ni, queue memanggil method Enqueue(object) utk save data manakala ArrayList memangil Add(object) utk tujuan yg sama.

CODE

static void Main( string[] args )
        {
            string text = string.Empty;
            string typeInput = string.Empty;
            ulong value = 0;

            Console.WriteLine( "Select Data Structure to use");
            Console.WriteLine( "Q/q - Queue" );
            Console.WriteLine( "GQ/gq - Generic Queue" );
            Console.WriteLine( "AR/ar - ArrayList" );
            Console.WriteLine( "GL/gl - Generic List" );


            typeInput = Console.ReadLine();


            LargestPrimeFactorBase lpfbase = GetDataStructureType( typeInput, out text );
            if ( lpfbase == null )
            {
                Console.WriteLine( "Unknown type, aborting" );
                return;
            }

            Console.WriteLine( "Enter value: (enter T1 or t1 for test data 1. Or T2/t2 for test data 2)" );
            Console.Write( ">>" );
            
            string temp = Console.ReadLine();

            Stopwatch timer = new Stopwatch();

            if ( ulong.TryParse( temp, out value ) )
            {
                Console.WriteLine();
                Console.WriteLine( text );
            }
            else
            {
                if ( temp.ToUpper() == "T1" )
                    value = 13195;

                if (temp.ToUpper() == "T2")
                    value = 317584931803;
            }

            timer.Start();
            lpfbase.Process( value );
            timer.Stop();
            Console.Write( text );
            Console.WriteLine( "Test Data: {0}", value );
            Console.WriteLine( "Answer: {0}", lpfbase.List);
            Console.WriteLine( "Time taken: {0} ms", timer.Elapsed );

        }

        internal static LargestPrimeFactorBase GetDataStructureType(string type, out string text)
        {
            text = string.Empty;
            if ( type.ToUpper() == "Q")
            {
                text = "Using LPFQueue";
                return new LPFQueue();
            }
            if ( type.ToUpper() == "GQ")
            {
                text = "Using Generic Queue";
                return new LPFGenericQueue();
            }
            if ( type.ToUpper() == "AR")
            {
                text = "Using Arraylist";
                return new LPFArrayList();
            }
            if ( type.ToUpper() == "GL" )
            {
                text = "Using Generic List";
                return new LPFGenericList();
            }


            return null;
        }

Code utk ArrayList

CODE

public class LPFArrayList : LargestPrimeFactorBase
    {
        private ArrayList m_list;
        private ulong m_answer = 1;

        public LPFArrayList()
        {
        }
        public override void Process( ulong value )
        {
            m_list = new ArrayList();

            for ( ulong i = 2; i < value; i++ )
            {
                if ( value % i == 0 && i % 2 > 0 )
                {
                    m_answer *= i;
                    if ( m_answer > value )
                        break;

                    if ( ( i < 10 ) || ( i % 5 > 0 ) )
                    {
                        m_list.Add( i );
                    }
                }
            }

            base.Process( value );
        }

        public override object Answer
        {
            get
            {
                return m_answer;
            }
        }
        public override string List
        {
            get
            {
                string list = string.Empty;
                IEnumerator enumerator = m_list.GetEnumerator();
                while ( enumerator.MoveNext() )
                {
                    list += " " + enumerator.Current;
                }

                return list;

            }
        }
    }

code utk LPFGenericQueue, tukar yg berikut sahaja...

CODE

public override void Process( ulong value )
        {
            m_queue = new Queue<ulong>();

            for ( ulong i = 2; i < value; i++ )
            {
                if ( value % i == 0 && i % 2 > 0 )
                {
                    m_answer *= i;
                    if ( m_answer > value )
                        break;

                    if ( ( i < 10 ) || ( i % 5 > 0 ) )
                    {
                        m_queue.Enqueue( i );
                    }
                }
            }

            base.Process( value );

public override string List
        {
            get
            {
                string list = string.Empty;
                IEnumerator enumerator = m_queue.GetEnumerator();
                while ( enumerator.MoveNext() )
                {
                    list += " " + enumerator.Current;
                }

                return list;

            }
        }

[jEmBaLanG]

Input : 317584931803
List : 67 829 1459 3919
Prime List : 67 829 1459 3919
LPF : 3919
Timed : 00:00:00.0023785

aku masih x dpt mengalahkan amry utk Problem 3 apabila menggunakan test data 317584931803 seperti mana yg disyorkan oleh MathChallenge.net

ni hasil dia bila menggunakan ArrayList dgn pertolongan amry utk runkan program aku atas dual core processor machine dia..

Using Arraylist
Using ArraylistTest Data: 317584931803
Answer: 67 829 1459 3919
Time taken: 00:00:00.0049210 ms

Dari segi programming method, cara amry lagi bagus sebab programnya generate dulu prime numbers by calling GeneratePrimeList(). Dgn cara ini, amry dah ada dlm memory a prime numbers ready for other processes (execution dlm memory lagi laju). Kaedah yg aku pakai adalah dgn tidak generate apa2 prime numbers in memory, instead terus buat validation checking. Code aku mungkin lagi pendek dari amry sebab processing takes place only in Process() method. Tetapi pendekatan amry lagi menarik...

Conclusion: Tak semestinya code yg pendek guarantee lagi laju dari code yg panjang