Euler's Sieve - പ്രൈം നമ്പറിനെക്കുറിച്ച് തന്നെ

കഴിഞ്ഞ പോസ്റ്റില്‍ R. ഇട്ട കമന്റില്‍ നിന്നാണ്‌ പ്രൈം നമ്പറുകള്‍ കണ്ടു പിടിക്കാനുള്ളുഅ ഇറാത്തോസ്തനീസിന്റെ അല്‍ഗോരിതത്തിലെത്തിച്ചേര്‍ന്നത്.
അതിന്റെ സി ഇമ്പ്ലിമെന്റേഷന്‍ വിക്കി പേജിന്റെ അവസാനം External Links ഇല്‍ കൊടുത്തിട്ടുണ്ട്.
അതില്‍ ഫ്ലാഗുകളുടെ അയ്യരുകളിയാണ്‌. ഫ്ലാഗില്ലാതെ എങ്ങിനെ ചെയ്യാം എന്നാണല്ലോ നമ്മുടെ ലക്ഷ്യം തന്നെ.

എന്നാല്‍ പിന്നെ ഒന്നു ശ്രമിച്ചു നോക്കാം എന്നു കരുതി. ഇറാത്തോസ്തനീസിന്റെ അല്‍ഗോരിതത്തിലെത്തിന്റെ ഒന്നു കൂടെ മെച്ചപ്പെടുത്തിയ യുളേഴ്സ് അല്‍ഗോരിതം പരീക്ഷിക്കുന്നതിലാവും രസം. (അല്‍ഗോരിതം വിക്കിയില്‍ നോക്കുക).

ലിസ്റ്റ് ഉപയോഗിച്ച് ചെയ്യുന്നതാണ്‌ രസം. സി യില്‍ ലിസ്റ്റ് ഉപയോഗിക്കന്നത് ആലോചിക്കാനേ വയ്യ. അത് കൊണ്ട് ഒരു ഒബ്ജക്റ്റ് ഓറിയന്റഡ് ലാംഗ്വേജ് ആണ്‌ നല്ലത്. സിഷാര്‍പ്പാവട്ടെ.

സിഷാര്‍പ്പിനു വേണ്ടി അല്‍ഗോരിതം ഇങ്ങനെ മാറ്റിയെഴുതി


A. രണ്ട് മുതല്‍ പരമാവധി സംഖ്യ വരെ ഒരു ലിസ്റ്റിനകത്ത് സ്റ്റോര്‍ ചെയ്യുക. ഇതേ സംഖ്യകള്‍ ഒരു നിരയിലും (Array) സൂക്ഷിക്കുക. (ലിസ്റ്റിനു പേരു intList എന്നും നിരക്കു പേരു intArray എന്നും കൊടുക്കാം )

B.

1. intArray യിലെ ഏറ്റവും ഇടതു വശത്തെ സംഖ്യ മുതല്‍ തുടങ്ങുക. ഇടത് വശത്തെ ആദ്യസംഖ്യ പ്രൈം ആയിരിക്കും. അതിനെ പ്രിന്റ് ചെയ്ത ശേഷം അത് RemoveMultiples എന്ന method നെ വിളിക്കുക.

2.RemoveMultiples ചെയ്യുക എന്താണെന്ന് വെച്ചാല്‍ intArray നിരയിലെ ആദ്യസംഖ്യ എപ്പോഴും പ്രൈം ആയിരിക്കും. ആ സംഖ്യ ഉപയോഗിച്ച് നിരയിലെ മറ്റെല്ലാ സംഖ്യകളെയും ഗുണിക്കുക. ഗുണനഫലമായി കിട്ടുന്ന സംഖ്യകളെ ലിസ്റ്റില്‍ നിന്നും നീക്കം ചെയ്യുക.

3.പുതിയതായി കിട്ടിയ ലിസ്റ്റിനെ വീണ്ടും intArray യിലേക്ക് കോപ്പി ചെയ്യുക. കോപ്പി ചെയ്യുമ്പോള്‍ ഇത് വരെ പ്രിന്റ് ചെയ്ത പ്രൈം നമ്പറുകള്‍ ആവശ്യമില്ല. (അപ്പോഴും intArray യിലെ ഏറ്റവും ഇടത് വശത്തെ നമ്പര്‍ പ്രൈം തന്നെയായിരിക്കും

C. B1 മുതല്‍ B3 വരെ ആവര്‍ത്തിക്കുക - ലിസ്റ്റിലെ അവസാനസംഖ്യ വരെ പരിശോധിക്കപ്പെടും വരെ.

B1 എന്ന സ്റ്റെപ്പില്‍ സംഖ്യ പ്രിന്റ് ചെയ്യുന്നത് ശ്രദ്ധിച്ചല്ലോ അത് കൊണ്ട് കോഡ് ഓടിക്കഴിയുമ്പോഴേക്കും പ്രൈം നമ്പറുകള്‍ എല്ലാം പ്രിന്റ് ചെയ്ത് കഴിഞ്ഞിരിക്കും. കൂടാതെ ഏറ്റവും അവസാനം ലിസ്റ്റില്‍ അവശേഷിക്കുന്നത് പ്രൈം നമ്പറുകള്‍ മാത്രം ആയിരിക്കുകയും ചെയ്യും.

കോഡ് താഴെ കൊടുത്തിരിക്കുന്നു.
calvin@Singularity:~/programming/csharp$ gedit PrintPrime.cs

using System;
using System.Collections;

public class IntegerList{


  private ArrayList intList;
  private int[] intArray;
  private int lastIndex;

  public IntegerList (int iMax) {
      //constructor - will populate list and the array with integers starting from 2  to iMax
      int i;
      intList = new ArrayList();
      intArray = new int[iMax];
      for (i=2;i<=iMax;i++) {
          intList.Add(i);
          intArray[i-2] = i;
      }
      lastIndex = intList.Count;  
  }

  protected void CopyList(int currIndex){
      //copy the items from list to array excluding the items from left which has already got printed.
      int i=0;
      for(i=0;(i+currIndex)<intList.Count;i++){
intArray[i] = (int) intList[(i+currIndex)];
      }
      intArray[i+1] = 0;
  }


  protected void  RemoveMultiples(int iMax ){
      //the  array will contain the all items from list minus the numbers that have already identified as prime
      int iPrime = intArray[0];
int i =0;
      for(i=0; intArray[i]*iPrime<=iMax ; i++){
 Console.WriteLine("Removing {0}, currprime {1}", intArray[i]*iPrime, iPrime);
          intList.Remove(intArray[i]*iPrime);
    
      }

lastIndex=intList.Count;
  }


  public void FindPrime(int iMax){
      int currIndex = 0;
      while (currIndex < lastIndex){
          Console.WriteLine("{0} is a Prime Number", intList[currIndex]);
          RemoveMultiples(iMax);
    currIndex++;
          CopyList(currIndex);
        


      }
  }

  public void PrintAgain(){
Console.WriteLine("\n Printiing the content if intList");
Console.WriteLine("===================================");
      foreach(int intPrime in intList)
      {
          Console.WriteLine("{0} is a prime number",intPrime);
      }

  }

}


  class PrintPrime
  {
      // Main begins program execution.
      public static int Main(String[] args)
      {

 try {
   int iMax = int.Parse(args[0]);
            // Write to console
            Console.WriteLine("Hello All");

           IntegerList il = new IntegerList(iMax);
  Console.WriteLine("List of prime numbers that are < {0} \n", args[0]);
  il.FindPrime(iMax);
  il.PrintAgain();
 }
 catch (System.IndexOutOfRangeException){
  Console.WriteLine("Argument 'Maximum Number' is missing'");
 
 }
 finally{
  Console.WriteLine("Good Bye");
 }

 return 0;
      }
  }

കോഡിലെ ചില പ്രത്യേകതകള്‍ എന്താണ്‌ എന്ന് വെച്ചാല്‍

ക. പരമാവധി സംഖ്യ മുന്‍‌നിശ്ചയിച്ച് ഹാര്‍ഡ്-കോഡ് ചെയ്യുന്നതിനു പകരം കമാന്‍ഡ് ലൈന്‍ ആര്‍ഗ്യുമെന്റ് ആയി പാസ് ചെയ്യുന്നു.
ഖ. എല്ലാം പ്രിന്റ് ചെ‌‌യ്ത ശേഷം, ലിസ്റ്റിലെ സംഖ്യകള്‍ ഒന്നു കൂടെ പ്രിന്റ് ചെയ്യുന്നു.
ഗ. RemoveMultiples സ്റ്റെപ്പില്‍ ഓരോ തവണയും ഏതെല്ലാം സംഖ്യ ഒഴിവാക്കുന്നു എന്ന് പ്രിന്റ് ചെയ്യുന്നു (വെറുതെ കാണാന്‍ വേണ്ടി).
ഘ. പ്രോഗ്രാം റണ്‍ ചെയ്യുന്ന മഹാന്‍ അഥവാ പരമാവധി സംഖ്യ കമാന്‍ഡ് ലൈന്‍ ആര്‍ഗ്യുമെന്റായി കൊടുക്കാന്‍ മറന്നാല്‍ ഒരു യൂസര്‍ ഫ്രണ്ട്ലി എറര്‍ മെസ്സേജ് കാണിക്കും (try-catch-finally ഉപയോഗിച്ച്).

Compile:
യൂണിക്സില്‍ ഇങ്ങനെ Compile ചെയ്യാവുന്നതാണ്‌. (CSharp compiler ആയ cscc ഇന്‍സ്റ്റാള്‍ ചെയ്തിരിക്കണം)
calvin@Singularity:~/programming/csharp$ cscc PrintPrime.cs

Run ചെയ്യാന്‍ (ഉദാഹരണം ആയി 120 വരെ)

calvin@Singularity:~/programming/csharp$ ./a.out 120


Output:

Hello All
List of prime numbers that are 2 is a Prime Number
Removing 4, currprime 2
Removing 6, currprime 2
Removing 8, currprime 2
Removing 10, currprime 2
Removing 12, currprime 2
Removing 14, currprime 2
Removing 16, currprime 2
Removing 18, currprime 2
Removing 20, currprime 2
Removing 22, currprime 2
Removing 24, currprime 2
Removing 26, currprime 2
Removing 28, currprime 2
Removing 30, currprime 2
Removing 32, currprime 2
Removing 34, currprime 2
Removing 36, currprime 2
Removing 38, currprime 2
Removing 40, currprime 2
Removing 42, currprime 2
Removing 44, currprime 2
Removing 46, currprime 2
Removing 48, currprime 2
Removing 50, currprime 2
Removing 52, currprime 2
Removing 54, currprime 2
Removing 56, currprime 2
Removing 58, currprime 2
Removing 60, currprime 2
Removing 62, currprime 2
Removing 64, currprime 2
Removing 66, currprime 2
Removing 68, currprime 2
Removing 70, currprime 2
Removing 72, currprime 2
Removing 74, currprime 2
Removing 76, currprime 2
Removing 78, currprime 2
Removing 80, currprime 2
Removing 82, currprime 2
Removing 84, currprime 2
Removing 86, currprime 2
Removing 88, currprime 2
Removing 90, currprime 2
Removing 92, currprime 2
Removing 94, currprime 2
Removing 96, currprime 2
Removing 98, currprime 2
Removing 100, currprime 2
Removing 102, currprime 2
Removing 104, currprime 2
Removing 106, currprime 2
Removing 108, currprime 2
Removing 110, currprime 2
Removing 112, currprime 2
Removing 114, currprime 2
Removing 116, currprime 2
Removing 118, currprime 2
Removing 120, currprime 2
3 is a Prime Number
Removing 9, currprime 3
Removing 15, currprime 3
Removing 21, currprime 3
Removing 27, currprime 3
Removing 33, currprime 3
Removing 39, currprime 3
Removing 45, currprime 3
Removing 51, currprime 3
Removing 57, currprime 3
Removing 63, currprime 3
Removing 69, currprime 3
Removing 75, currprime 3
Removing 81, currprime 3
Removing 87, currprime 3
Removing 93, currprime 3
Removing 99, currprime 3
Removing 105, currprime 3
Removing 111, currprime 3
Removing 117, currprime 3
5 is a Prime Number
Removing 25, currprime 5
Removing 35, currprime 5
Removing 55, currprime 5
Removing 65, currprime 5
Removing 85, currprime 5
Removing 95, currprime 5
Removing 115, currprime 5
7 is a Prime Number
Removing 49, currprime 7
Removing 77, currprime 7
Removing 91, currprime 7
Removing 119, currprime 7
11 is a Prime Number
13 is a Prime Number
17 is a Prime Number
19 is a Prime Number
23 is a Prime Number
29 is a Prime Number
31 is a Prime Number
37 is a Prime Number
41 is a Prime Number
43 is a Prime Number
47 is a Prime Number
53 is a Prime Number
59 is a Prime Number
61 is a Prime Number
67 is a Prime Number
71 is a Prime Number
73 is a Prime Number
79 is a Prime Number
83 is a Prime Number
89 is a Prime Number
97 is a Prime Number
101 is a Prime Number
103 is a Prime Number
107 is a Prime Number
109 is a Prime Number
113 is a Prime Number

Printiing the content if intList
===================================
2 is a prime number
3 is a prime number
5 is a prime number
7 is a prime number
11 is a prime number
13 is a prime number
17 is a prime number
19 is a prime number
23 is a prime number
29 is a prime number
31 is a prime number
37 is a prime number
41 is a prime number
43 is a prime number
47 is a prime number
53 is a prime number
59 is a prime number
61 is a prime number
67 is a prime number
71 is a prime number
73 is a prime number
79 is a prime number
83 is a prime number
89 is a prime number
97 is a prime number
101 is a prime number
103 is a prime number
107 is a prime number
109 is a prime number
113 is a prime number
Good Bye