Tuesday 30 April 2013

PROGRAM FOR FINDING THE PRIME FACTOR OF A NUMBER

The prime factors of a positive integer are the prime numbers that divide that integer exactly.
for example :-





Here is the source code for finding the prime factors of any number inputted by the user. Here you should note that that to increase the range I have used long data type to store number given by user.

Source code :-
/**********************************************************************************/
#include<stdio.h>
#include<conio.h>

int main()
{
    long num,i,a;
    clrscr();
    printf("ENTER THE NUMBER : ");
    scanf("%ld",&num);
    a=num;
    for(i=2;i<=a;i++)
    {
        if((num%i)==0)
        {
            printf("%ld\t",i);
            num/=i;
            i=1;
        }
    }
    getch();
    return 1;
}
/*********************************************************************************/
Output :-


PROGRAM TO FIND REVERSE OF A NUMBER

This program prompts user to enter a number and then stores the reverse of this number in another variable and then prints it.
Suppose for example, if user entered 5689, then the reverse of this number will be 9865.




Source code 1 :-
/****************************************************************************/
#include<stdio.h>
#include<conio.h>

int main()
{
    long num,rev=0;
    clrscr();

    printf("ENTER A NUMBER : ");
    scanf("%ld",&num);

    while(num)
    {
        rev=(rev*10)+num%10;
        num/=10;
    }
    printf("REVERSE = %ld",rev);

    getch();
    return 1;
}
/*****************************************************************************/

If the user just wants the reverse of the number then you can also store the number inputted by user as a string and then print the reverse of the string. The same thing I have used in the following program.

Source code 2 :-
/*****************************************************************************/
#include<stdio.h>
#include<conio.h>
#include<string.h>
int main()
{
    char num[50];
    int i;
    clrscr();
    printf("ENTER THE NUMBER : ");
    gets(num);

    printf("\nREVERSE OF THE NUMBER IS : \n");

    for(i=strlen(num)-1;i>=0;i--)
        printf("%c",num[i]);

    getch();
    return 1;
}
/******************************************************************************/

 By using the second code the following output is also possible (this output is not possible if we use source code 1) :-

PROGRAM TO FIND ALL THE PRIME NUMBERS WITHIN GIVEN RANGE

prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself. A simple but slow method of verifying the primality of a given number n is known as trial division. It consists of testing whether n is a multiple of any integer between 2 and \sqrt{n}.
This is what I have done in my C program to check whether a number is prime or not. The following program finds all the prime numbers within a given range.

Source Code :-
/******************************************************************************/
//PROGRAM TO FIND ALL THE PRIME NUMBERS WITHIN GIVEN RANGE

#include<stdio.h>
#include<conio.h>
#include<math.h>

int main()
{
long ll,ul,i,j;
clrscr();

printf("ENTER THE LOWER LIMIT : ");
scanf("%ld",&ll);

printf("ENTER THE UPPER LIMIT : ");
scanf("%ld",&ul);

for(i=ll;i<=ul;i++)
{
if(i==1)
i++;

for(j=2;j<=sqrt(i);j++)
{
if(i%j==0)
{
goto lavish;
}
}
printf("%ld\t",i);
lavish : ;
}

getch();
return 1;
}

/****************************************************************************/
Output:-




PASCAL'S TRIANGLE


One of the most interesting Number Patterns is Pascal's Triangle (named after Blaise Pascal, a famous French Mathematician and Philosopher).

To build the triangle, start with "1" at the top, then continue placing numbers below it in a triangular pattern.

Each number is just the two numbers above it added together (except for the edges, which are all "1").

(Here I have highlighted that 1+3 = 4)


So Pascal's Triangle could also be an "n choose k" triangle like this:


Note that the top row is row zero and also the leftmost column is zero.



SOURCE CODE:-
/***********************************************************************/
#include<stdio.h>
#include<conio.h>

double nCr(int,int);
double factorial(int);

int main()
{
int r,i,j;
clrscr();
printf("ENTER THE NUMBER OF ROWS : ");
scanf("%d",&r);

for(i=0;i<r;i++)
{
for(j=0;j<=i;j++)
{
if(i==j)
{
printf("1\t");
}
else
{
printf("%0.0lf\t",nCr(i,j));
}
}
printf("\n");
}

getch();
return 1;
}


double nCr(int i,int j)
{
return factorial(i)/(factorial(j)*factorial(i-j));
}

double factorial(int n)
{
double fact=1;
int i=1;
for(i=1;i<=n;i++)
fact*=i;

return fact;
}

/*********************************************************************/


H.C.F. AND L.C.M. - SIMPLE C PROGRAM

H.C.F.
The highest common factor (H.C.F.) of two or more given numbers is the greatest number which divides each of given numbers exactly without leaving any remainder.

L.C.M.
The least common multiple (L.C.M.) of two given numbers is that lowest number which is divisible exactly by each of the given numbers.

Note:-
Product of two numbers = product of their H.C.F. and L.C.M.


Source code for finding H.C.F. and L.C.M. through a C program:-
/********************************************************************************/

#include<stdio.h>
#include<conio.h>

int main()
{
long num1,num2,hcf,lcm,div,r;
clrscr();
printf("ENTER TWO NUMBERS : ");
scanf("%ld%ld",&num1,&num2);

hcf=num1>num2?num2:num1;
div=num1>num2?num1:num2;
r=div%hcf;

while(r)
{
div=hcf;
hcf=r;
r=div%hcf;
}

lcm=(num1*num2)/hcf;
printf("hcf = %ld\t\tlcm = %ld",hcf,lcm);
getch();
return 1;
}
/****************************************************************************/

DIVISORS OF A NUMBER

divisor of an integer n, also called a factor of n, is an integer which divides n without leaving a remainder.

Here is a very simple C program to find all the divisors of a number inputted by the user.

/********************************************************************************/

#include<stdio.h>
#include<conio.h>

int main()
{
long num,i;
clrscr();
printf("ENTER A NUMBER : ");
scanf("%ld",&num);

for(i=1;i<=num;i++)
{
if(num%i==0)
{
printf("%ld\t",i);
}
}
getch();
return 1;
}
/*******************************************************************************/

Monday 29 April 2013

FIBONACCI SERIES


The Fibonacci Sequence is a very interesting and fast growing series.

You can find each term by adding two preceding terms of the sequence provided that the first two terms are 0 and 1;
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 
610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 
28657, 46368, 75025, 121393, 196418, 317811, ...
The next number is found by adding up the two numbers before it.
  • The 2 is found by adding the two numbers before it (1+1)
  • Similarly, the 3 is found by adding the two numbers before it (1+2),
  • And the 5 is (2+3),
  • and so on!
Here I have two different programs for finding the nth term of fibonacci series.
In the first program you can find the nth fibonacci term with the limitations of range. But to fix this limitation I have a very interesting program, which can find even the 50th fibonacci term. 

First program:-
/***************************************************************/
#include<stdio.h>
#include<conio.h>

int main()
{
int num,i;
double a=0,b=1,c;
clrscr();
printf("ENTER THE TERM NUMBER : ");
scanf("%d",&num);

for(i=0;i<num;i++)
{
c=a+b;
if(i==num-3)
{
printf("%0.0lf",c);
break;
}
a=b;
b=c;
}
getch();
return 1;
}


/***************************************************************/




Program 2:-
/***************************************************************/
#include<stdio.h>
#include<conio.h>
#define max 2000

int arr1[max],arr2[max],arr3[max];

void fun(void);

int main()
{
int num,i,j,tag=0;
clrscr();
for(i=0;i<max;i++)
arr1[i]=arr2[i]=arr3[i]=0;

arr2[max-1]=1;

printf("ENTER THE TERM : ");
scanf("%d",&num);

for(i=0;i<num;i++)
{
fun();

if(i==num-3)
break;

for(j=0;j<max;j++)
arr1[j]=arr2[j];

for(j=0;j<max;j++)
arr2[j]=arr3[j];

}

for(i=0;i<max;i++)
{
if(tag||arr3[i])
{
tag=1;
printf("%d",arr3[i]);
}
}


getch();
return 1;
}

void fun(void)
{
int i,temp;
for(i=0;i<max;i++)
arr3[i]=arr1[i]+arr2[i];

for(i=max-1;i>0;i--)
{
if(arr3[i]>9)
{
temp=arr3[i];
arr3[i]%=10;
arr3[i-1]+=(temp/10);
}
}
}

/***************************************************************/


Note that the second program gives accurately the 100th term of series. 
Though the first program also gives some value but it is not correct. It gives correct values only upto certain limited terms.

Tuesday 23 April 2013

ENTER JUMBLED UP ALPHABETS AND FIND ALL POSSIBLE MEANINGFUL ENGLISH WORDS THROUGH A SIMPLE C PROGRAM



Recently, while reviewing some of the file handling concepts, an interesting thing clicked my mind, that what if I enter jumbled up alphabets, and a C program can give me all the possible meaningful words. Really, this thing sounds awesome. So right at that moment I hanged up my mind, trying to get solution to this problem. I also stuck on to this problem, as a mischievous thought came in my mind that during some baby-step hacking of social engineering, how-so-ever if you manage to get the alphabets involved in your friend’s facebook password (but not the actual sequence of the alphabets) then you can easily get the actual password, through this C program, provided you have a versatile pass-list.
In my source code, I have extensively used file handling concepts of C. The concept I have used is very easy to understand, I have not at all involved any major complexity regarding algorithm, except the function definition, which I used just to compare two strings, although you could have accomplished this task using pre-defined functions in string.h header file, but defining your own function is a better option, and it will also build up your algorithm development capabilities.
I just prompted the user to enter a string, which is actually the jumbled up characters, and scanned a string from my text file that contains all the English words, then I compared length of both the strings, and if both the strings have equal length, then I called the function to compare the strings. If the strings are identical then I used fprintf function to again write the correct meaningful English word to another text file. I repeated this process till I reached the end-of-file which I used to scan English words. And simply we are done with our job.


SOURCE CODE :-
/***************************************************************************************/
#include<stdio.h>
#include<conio.h>
#include<stdio.h>

int fun(char*,char*);
int main()
{
                FILE*p1,*p2;
                int flag=0;
                char name1[130],name2[130];
                clrscr();
                p1=fopen("d:/c/a.txt","r");
                /*a.txt is a file that contains all the meaningful English words*/
                p2=fopen("d:/c/b.txt","w");
/*b.txt is a file that will contains the English words that can possibly be formed using jumbled characters entered by user*/
                rewind(p1);
                rewind(p2);
                if(p1&&p2)
                {
                                printf("ENTER JUMBLED WORDS IN LOWER CASE : ");
                                scanf("%s",name2);

                                while(!feof(p1))
                                {
                                                flag=0;

                                                printf("searching...\n");
                                                fscanf(p1,"%s",name1);

                                                if(strlen(name1)==strlen(name2))
                                                {
                                                                flag=fun(name1,name2);
                                                }
                                                if(flag)
                                                {
                                                                fprintf(p2,"%s\n",name1);
                                                }
                                }
                }
                else
                {
                                printf("FILE OPERATION WAS UNSUCCESSFUL");
                }
                getch();
                return 1;
}

int fun(char name1[130],char name2[130])
{
                int i,length=strlen(name1),count=0,j,k;
                char temp;

                for(i=0,j=length-1;i<length;i++)
                {
                                for(k=0;k<=j;k++)
                                {
                                                if((name1[i]==name2[k])&&j>=0)
                                                {
                                                                count++;

                                                                temp=name2[k];
                                                                name2[k]=name2[j];
                                                                name2[j]=temp;
                                                                j--;

                                                                break;
                                                }

                                }
                }

                if(count==length)
                {
                                printf("%s\n",name1);
                                return 1;
                }
                else
                {
                                return 0;
                }
}
/*******************************************************************************************/



Sunday 21 April 2013

QUICK SORT

Quicksort, is a sorting algorithm developed by Tony Hoare that, on average, makes O(n log n) comparisons to sort n items. In the worst case, it makes O(n2) comparisons, though this behavior is rare. Quick Sort is well known as ’the best practical sorting algorithm'. It is used on the principle of divide-and-conquer. It is often faster in practice than other O(n log n) algorithms.

  • Pick an element, called a pivot, from the list.
  • Partition the list so that all elements which are less than the pivot come before the pivot, and elements greater than the pivot come after it. For instance,
      A[1...i]  A[pivot]  A[j-+ 1...n]
  ◟  ◝◜ ◞  ◟ ◝◜  ◞  ◟   ◝◜   ◞
≤ A [pivot]           ≥ A[pivot]
  • Recursively repeat those operations to sort the sublists of lesser elements and of greater elements.







Time Complexity
The performance of Quick Sort always depends on the position of selected pivot. A bad pivot could lead to poor performance, for instance, selecting position 1 as the pivot produces a recursion tree of height n. Conversely, a good pivot would operate at best performance of O(⋅ log n) of tree height Θ(log n), pivot at the middle of the list, for instance.

SOURCE CODE #1:-

/******************************************************************************/

//RECURSIVE QUICK SORT THROUGH A SINGLE FUNCTION

#include<stdio.h>
#include<conio.h>

void quicksort(int*,int,int);

int main()
{
int n,i,*arr;
clrscr();

printf("ENTER THE MAXIMUM NUMBER OF ELEMENTS");
scanf("%d",&n);

printf("ENTER THE DATA ELEMENTS THAT YOU WANT TO SORT");
for(i=0;i<n;i++)
scanf("%d",&arr[i]);

quicksort(arr,0,n-1);

for(i=0;i<n;i++)
printf("%d\t",arr[i]);

getch();
return 1;
}

void quicksort(int*arr,int a,int b)
{
int i=a+1,j=b,tmp;

if(i>j)
return;

while(i<=j)
{
for(;arr[i]<arr[a]&&i<=b;i++);
for(;arr[j]>arr[a]&&j>=a;j--);

if(i<=j)
{
tmp=arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
}

tmp=arr[a];
arr[a]=arr[j];
arr[j]=tmp;

quicksort(arr,a,j-1);
quicksort(arr,j+1,b);
}
/*****************************************************************************/




SOURCE CODE #2:-
/*****************************************************************************/
#include<stdio.h>
#include<conio.h>


void quicksort(int *,int,int);
int qsort(int*,int,int);

int flag=0,abc;

int main()
{
int i,j,ploc,min,n,arr[50];
clrscr();

printf("enter the max no of elements of array\n");
scanf("%d",&n) ;
abc=n;

printf("enter the data of array\n");
for(i=0;i<n;i++)
scanf("%d",&arr[i]);

quicksort(arr,0,n-1);


for(i=0;i<n;i++)
printf("%d\t",arr[i]);

getch();
return 1;
}


void quicksort(int*arr,int min,int max)
{
int ploc;
while(max>min)
{
ploc=qsort(arr,min,max);
quicksort(arr,min,ploc-1);
quicksort(arr,ploc+1,max);
if(flag>abc)
return;
}
}


int qsort(int *arr,int min,int max)
{
int ploc,j,tmp;
ploc=min;
for(j=ploc+1;j<=max;)
if(arr[j]<arr[min])
{
ploc++;
tmp=arr[ploc];
arr[ploc]=arr[j];
arr[j]=tmp;
j=ploc+1;
}
else
j++;


tmp=arr[min];
arr[min]=arr[ploc];
arr[ploc]=tmp;
//printf("Lavish\n");
flag++;

return ploc;
}



/*******************************************************************************/


Thursday 18 April 2013

MERGE SORT


Conceptually, a merge sort works as follows
  1. Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
  2. Repeatedly merge sublists to produce new sublists until there is only 1 sublist remaining. This will be the sorted list.

The following figures will clearly illustrate the working of merge sort:-



IMPLEMENTATION OF MERGE SORT USING LINKED LIST

Here each number, that the user is prompted to input is stored in a node of the linked list, and then the list is divided, and then a recursive function is called to implement the merging.

/***********************************************************************************************************///MERGE SORT
//SORTING A LINK LIST
//RECURSIVE DEFINITION


#include<stdio.h>
#include<conio.h>

struct Node
{
int val;
struct Node*next;
};

typedef struct Node node;

void printlist(node*);
node*makenode(int);
node*mergesort(node*);
node*divide(node*);
node*merge(node*,node*);

int main()
{
int i,tmp;
node*start,*nn,*last;
clrscr();
start=last=NULL;

while(1)
{
printf("enter the data part of the node:");
scanf("%d",&tmp);

if(tmp==0)
break;

nn=makenode(tmp);

if(start)
{
last->next=nn;
last=nn;
}
else
{
start=last=nn;
}
}
start=mergesort(start);

printlist(start);
getch();
return 1;
}


node*mergesort(node*start)
{
node*nh;
if(start&&start->next)
{

nh=divide(start);
start=mergesort(start);
nh=mergesort(nh);
start=merge(start,nh);
}
return start;
}

node*divide(node*start)
{
node*ptr1,*ptr2,*start2=NULL;
if(start->next)
{
ptr1=start;
ptr2=start->next->next;
while(ptr2)
{
ptr1=ptr1->next;
ptr2=ptr2->next;
if(ptr2)
ptr2=ptr2->next;
}
start2=ptr1->next;
ptr1->next=NULL;
}
return start2;
}

node*merge(node*s1,node*s2)
{
node*s3,*l3,*tmp;
s3=l3=NULL;
while(s1&&s2)
{
if(s1->val<s2->val)
{
tmp=s1;
s1=s1->next;
}
else
{
tmp=s2;
s2=s2->next;
}
if(!s3)
s3=tmp;
else
l3->next=tmp;
l3=tmp;
}
if(s1)
{
if(!s3)
s3=s1;
else
l3->next=s1;
}
if(s2)
{
if(!s3)
s3=s2;
else
l3->next=s2;
}
return s3;
}


void printlist(node*start)
{
while(start)
{
printf("%d\t",start->val);
start=start->next;
}
}


node*makenode(int tmp)
{
node*nn;
nn=(node*)malloc(sizeof(node));
nn->val=tmp;
nn->next=NULL;
return nn;
}
/*******************************************************************************/



IMPLEMENTATION OF MERGE-SORT USING ARRAYS

/*****************************************************************************/
//MERGE SORT

#include<stdio.h>
#include<conio.h>

void mergesort(int*,int ,int);
void merge(int *,int ,int);

//int b[20];

int main()
{
//clrscr();
int arr[20];
int i,j,n;
clrscr();
printf("ENTER THE NUMBER OF ELEMENTS OF ARRAY:");
scanf("%d",&n);
printf("enter the data of array:\n");
for(i=0;i<n;i++)
scanf("%d",&arr[i]);

mergesort(arr,0,n-1);

for(i=0;i<n;i++)
printf("%d\t",arr[i]);

getch();
return 1;
}

void mergesort(int *arr,int i,int j)
{
int mid;
if(i>=j)
return;
else
{
mid=(i+j)/2;
mergesort(arr,i,mid);
mergesort(arr,mid+1,j);
merge(arr,i,j);
}
}

void merge(int *arr,int i,int j)
{
int start=i;
int mid,k,l=i,b[20];
mid=(i+j)/2;

k=mid+1;

while(k<=j&&i<=mid)
{

if(arr[i]<arr[k])
b[l++]=arr[i++];
else
b[l++] =arr[k++];
}

if(i>mid)
while(k<=j)
b[l++]=arr[k++];
else if(k>j)
while(i<=mid)
b[l++]=arr[i++];

for(l=start;l<=j;l++)
arr[l]=b[l];
}

/****************************************************************************/