Saturday, February 20, 2010

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

Thursday, February 18, 2010

പ്രൈം നമ്പര്‍ പ്രിന്റ് ചെയ്യാന്‍

പ്രൈം നമ്പര്‍ പ്രിന്റ് ചെയ്യുന്നത് പ്രോഗ്രാമിങ്ങ് പഠിക്കുന്ന വിദ്യാര്‍ത്ഥികള്‍ക്ക് കിട്ടുന്ന ആദ്യപ്രശ്നങ്ങളിലൊന്നാണ്‌.
സി പ്രോഗ്രാമില്‍ പ്രം നമ്പര്‍ പ്രിന്റ് ചെയ്യാന്‍ ഉള്ള ഒരു ഫംഗ്ഷന്‍ പ്രോഗ്രാം താഴെ കൊടുത്തിരിക്കുന്നു. ഇതില്‍ പ്രൈം നമ്പര്‍ ആണോ അല്ലയോ എന്ന് തിരിച്ചറിയാന്‍ ഉള്ള ലോജിക്കില്‍ ഒരു ഫ്ലാഗ് യൂസ് ചെ‌യ്തിരിക്കുന്നത് ശ്രദ്ധിക്കുക (isPrime).

1. Create file
calvin@Singularity:~/programming$ gedit prime_flag.c




#include<stdio.h>


int prime_or_not(int iNum){

int isPrime = 0;
int jNum =2;

for(jNum=2;jNum<iNum;jNum++)
{
if( iNum%jNum==0)
{
isPrime = 1;
break;
}
}


return isPrime;

}

void main(){

int iNum=2;


printf("\n");
printf("==================================================\n");
printf("Program to print the prime numbers from 1 to 100\n");
printf("==================================================\n");


for(iNum=2;iNum<=100; iNum++)
{
if(!(prime_or_not(iNum)))
{
printf("%d is a prime number\n", iNum);
}


}



printf("\n\n");
}


2. Compile and run
calvin@Singularity:~/programming$gcc prime_flag.c
calvin@Singularity:~/programming$./a.out

3. Output


==================================================
Program to print the prime numbers from 1 to 100
==================================================

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


മെക്കാനിക്കല്‍ ഡിപ്പാര്‍ട്മെന്റിലെ സജിത് ബാബു സാര്‍ ഐ.ഐ.ടി ഇന്റര്‍‌വ്യൂവിനു പോയപ്പോള്‍ ചോദിച്ച ചോദ്യങ്ങളിലൊന്ന് How to write a C program to print prime numbers from 1 to 100 without using any flags എന്നായിരുന്നു. പുള്ളി അന്നാ ചോദ്യം ഞങ്ങള്‍ കുറച്ച് വിദ്യാര്‍ത്ഥികളോട് ചോദിച്ചു. അന്നതിനു എന്തോ ഒരു സൊലൂഷന്‍ ഞാന്‍ കണ്ടു പിടിച്ച് പ്രിന്റ് എടുത്ത് കുറേ ദിവസം നടന്നെങ്കിലും സാറ് സ്ഥലം മാറ്റം കിട്ടിയോ മറ്റോ പോയതിനാല്‍ അത് കൊടുക്കാന്‍ കഴിഞ്ഞില്ല. ആ ലോജിക് ഇപ്പോള്‍ ഓര്‍മയില്ല. വൈല്‍ ലൂപിന്റെ എന്തോ ഒരു കളി ആയിരുന്നു എന്ന് നേരിയ ഓര്‍മ ഉണ്ട്.

ഇന്നിപ്പോള്‍ അത് ഇങ്ങനെ സോള്‍‌വ് ചെയ്യാന്‍ തോന്നി.

1. Create file
calvin@Singularity:~/programming$ gedit prime_no_flag.c


#include<stdio.h>


int prime_or_not(int iNum){


int jNum =2;

for(jNum=2;jNum<iNum;jNum++)
{
if( iNum%jNum==0)
{

break;
}
}

if (jNum<=iNum-1)
return 1;
else
return 0;
}
void main(){

int iNum=2;


printf("\n");
printf("==================================================\n");
printf("Program to print the prime numbers from 1 to 100\n");
printf("Without using any Flags\n");
printf("==================================================\n");


for(iNum=2;iNum<=100; iNum++)
{
if(!(prime_or_not(iNum)))
{
printf("%d is a prime number\n", iNum);
}


}



printf("\n\n");
}



2. Compile and run
calvin@Singularity:~/programming$gcc prime__no_flag.c
calvin@Singularity:~/programming$./a.out

3.Output



==================================================
Program to print the prime numbers from 1 to 100
Without using any Flags
==================================================

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



വ്യത്യാസം ശ്രദ്ധിച്ചു കാണും എന്നു കരുതുന്നു.

ഇതല്ലാതെയും പല തരത്തില്‍ സോള്‍‌വ് ചെയ്യാവുന്നതാണ്‌. എല്ലാം നിങ്ങളുടെ ഇഷ്ടം ;)

CopyLeft Information

Singularity എന്ന ബ്ലോഗില്‍ പ്രസിദ്ധീകരിക്കുന്ന ലേഖനങ്ങള്‍ എല്ലാം പൊതുതാല്പര്യാര്‍ത്ഥം ഉള്ളതാണ്. അവ ലേഖകന്റെ അനുമതി കൂടാതെ തന്നെ വാണിജ്യപരമോ വാണിജ്യേതരമോ ആയ എന്താവശ്യത്തിനും ഏതൊരാള്‍ക്കും എപ്പോഴും എത്ര തവണ വേണമെങ്കിലും മാറ്റങ്ങളോടെയോ അതേ പടിയോ ബ്ലോഗിലോ ഇതരമാധ്യമങ്ങളിലോ സ്വതന്ത്രവും സൌജന്യവുമായി ഉപയോഗിക്കാം. മാറ്റം വരുത്തുന്ന പക്ഷം അതില്‍ ഈ ലേഖകന്‍‍ ഉത്തരവാദിയല്ല. പുനഃപ്രസിദ്ധീകരിക്കുന്ന കുറിപ്പിനൊപ്പം മൂലലേഖനത്തിന്റെ രചയിതാവു് എന്ന സ്ഥാനം ലേഖകനു് നല്‍കുന്നതു് അഭികാമ്യം. എന്നാല്‍ ഇതു് നിബന്ധനയല്ല. മറ്റൊരാളുടെ പേരു് പകരം കൊടുക്കാന്‍ അനുമതിയില്ല. വീണ്ടും ഉപയോഗിക്കുന്ന പക്ഷം ആ വിവരം ലേഖകനെ അറിയിക്കണമെന്നും ഈ പകര്‍പ്പുപേക്ഷാപത്രം ഒപ്പം നല്‍കണമെന്നും താത്പര്യപ്പെടുന്നു.