Sieve of Eratosthenes Algorithm

ALGORITHM Sieve(n)

//Implements the sieve of Eratosthenes

//Input: A positive integer > 1

//Output: Array L of all prime numbers less than or equal to n

for p ← 2 to n do A[p] ← p

for p ← 2 to √n do 

if A[p] = 0 //p hasn’t been eliminated on previous passes

j ← p ∗ p

while j ≤ n do

A[j] ← 0 //mark element as eliminated

j ← j + p

//copy the remaining elements of A to array L of the primes

i ← 0

for p ← 2 to n doifA[p] = 0

L[i] ← A[p]

i ← i + 1

return L

Method:

Algorithm to find all the prime numbers less than or equal to a given integer n by Eratosthenes’ method:

1.     Create a list of consecutive integers from 2 to n: (2, 3, 4, …, n).

2.     Initially, let p equal 2, the first prime number.

3.     Starting from p², count up in increments of p and mark each of these numbers greater than or equal to p² itself in the list. These numbers will be p(p+1), p(p+2), p(p+3), etc..

4.     Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this number (which is the next prime), and repeat from step 3.

C  program:

//  C program to print all primes smaller than or equal 

//to n using Sieve of Eratosthenes

#include <stdio.h>

#include <stdlib.h>

void SieveOfEratosthenes(int n)

{

    // Create a integer array "prime[0..n]" and initialize

    // all entries it as 1(true). A value in prime[i] will

    // finally be 0(false) if i is Not a prime, else true.

    int prime[n+1];

    int p,i;

for(i=0;i<=n;i++)

{

    prime[i]=1;

}

    for (p=2; p*p<=n; p++)

    {

        // If prime[p] is not changed, then it is a prime

        if (prime[p] ==1)

        {

            // Update all multiples of p greater than or

            // equal to the square of it

            // numbers which are multiple of p and are

            // less than p^2 are already been marked.

            for ( i=p*p; i<=n; i+= p)

                prime[i] = 0;

        }

    }

    // Print all prime numbers

    for (p=2; p<=n; p++)

       if (prime[p]==1){

          printf("%d ",p);

}

}

int main()

{

    int n;

    printf("Enter the N value\n");

    scanf("%d",&n);

    printf("Following are the prime numbers smaller than or 

equal to %d\n",n);

    SieveOfEratosthenes(n);

    return 0;

}  

Output:

Enter the N value

30

Following are the prime numbers smaller than or equal to 30

2 3 5 7 11 13 17 19 23 29

Read More

SortAnalysis Aglorithm

ALGORITHM SortAnalysis(A[0..n - 1])

//Input: An array A[0..n - 1] of n orderable elements
//Output: The total number of key comparisons made
count ← 0
for i ← 1 to n - 1 do
v ← A[i]
j ← i - 1
while j ≥ 0 and A[j] > v do
count ← count + 1
A[j + 1] ← A[j]
j ← j - 1
A[j + 1] ← v
return count

C program:

#include<stdio.h>
int main(){
int n,v,i,j,count=0,arr[100];
printf("Enter the No element u want to enter\n");
scanf("%d",&n);
printf("Enter the Elements\n");
for(i=0;i<n;i++){
    scanf("%d",&arr[i]);
}
for(i=1;i<n;i++)
{
    v=arr[i];
    j=i-1;
    while(j>=0 && arr[j]>v){
        count++;
        arr[j+1]=arr[j];
        j--;
        arr[j+1]=v;
    }

}
for(i=0;i<n;i++)
{
    printf("%d, ",arr[i]);
}
printf("\nNo of Steps:%d\n",count);
}

Output:

Enter the No element u want to enter
5
Enter the Elements
1
32
54
6
4
1 ,4, 6, 32, 54
No of Steps:5

Read More

Factorial Algorithm

ALGORITHM F(n)

//Computes n! recursively

//Input: A nonnegative integer n

//Output: The value of n!

if n = 0 return 1

else return F (n - 1) ∗ n

C program:

#include <stdio.h>

 int factorial(int c){

     if(c==1){

        return 1;

     }

     else{

 return c*factorial(c-1);

 }

 }

int main()

{

  int c, n, fact = 1;

  printf("Enter a number to calculate its factorial\n");

  scanf("%d", &n);

  fact=factorial(n);

 // for (c = 1; c <= n; c++)

    //fact = fact * c;

  printf("Factorial of %d = %d\n", n, fact);

  return 0;

}

Output:

Enter a number to calculate its factorial

5

Factorial of 5 = 120

Read More

Binary Algorithm

ALGORITHM Binary(n)

//Input: A positive decimal integer n

//Output: The number of binary digits in n’s binary representation

count ← 1
while n > 1 do

count ← count + 1

n ← n/2

return count

Another Way

ALGORITHM BinRec(n)

//Input: A positive decimal integer n

//Output: The number of binary digits in n’s binary representation

if n = 1 return 1

else return BinRec(n/2) + 1

C program:

// Iterative C program to count the number of

// digits in a number in binary form

#include <stdio.h>

int countDigit(long long n)

{

    int count = 0;

    while (n != 0) {

        n = n /2;

        ++count;

    }

    return count;

}

int main(void)

{

    long long n =1024;

    printf("Number of digits : %d",countDigit(n));

   
     return 0;

}

Output:

Number of digits : 11

Read More

MatrixMultiplication Algorithm

ALGORITHM MatrixMultiplication(A[0..n - 1, 0..n - 1], 

B[0..n - 1, 0..n - 1])

//Multiplies two square matrices of order n by the definition-based 

algorithm

//Input: Two n × n matrices A and B

//Output: Matrix C = AB

for i ← 0 to n - 1 do

forj ← 0 to n - 1 do

C[i, j] ← 0.0

for k ← 0 to n - 1 do

C[i, j] ← C[i, j] + A[i, k] ∗ B[k, j]

return C

C program:

#include <stdio.h>

int main()

{

  int m, n, p, q, c, d, k, sum = 0;

  int first[10][10], second[10][10], multiply[10][10];

  printf("Enter number of rows and columns of first matrix\n");  

scanf("%d%d", &m, &n);

  printf("Enter elements of first matrix\n");

  for (c = 0; c < m; c++)

    for (d = 0; d < n; d++)

      scanf("%d", &first[c][d]);

  printf("Enter number of rows and columns of second matrix\n");

  scanf("%d%d", &p, &q);

  if (n != p)

    printf("The matrices can't be multiplied with each other.\n");

  else

  {

    printf("Enter elements of second matrix\n");

    for (c = 0; c < p; c++)

      for (d = 0; d < q; d++)

        scanf("%d", &second[c][d]);

    for (c = 0; c < m; c++) {

      for (d = 0; d < q; d++) {

            multiply[c][d]=0;

        for (k = 0; k < p; k++) {

          multiply[c][d] = multiply[c][d]+ first[c][k]*second[k][d];

        }

    }

    }

    printf("Product of the matrices:\n");

    for (c = 0; c < m; c++) {

      for (d = 0; d < q; d++)

        printf("%d\t", multiply[c][d]);

      printf("\n");

    }

  }

  return 0;

}

Output:

Enter number of rows and columns of first matrix

2

2

Enter elements of first matrix

1

2

3

4

Enter number of rows and columns of second matrix

2

2

Enter elements of second matrix

1

2

3

4

Product of the matrices:

7       10

15      22

Read More

MinDistance Algorithm

ALGORITHM MinDistance(A[0..n - 1])

//Input: Array A[0..n - 1] of numbers

//Output: Minimum distance between two of its elements

dmin ← ∞

for i ← 0 to n - 1 do

forj ← 0 to n - 1 do

ifi = j and |A[i] - A[j]| < dmin

dmin← |A[i] - A[j]|

return dmin

C program:

// C program to Find the minimum// distance between two numbers

#include <stdio.h>

#include <stdlib.h> // for abs() Which calculate the difference between the //location in array 

int minDist(int arr[], int n, int x, int y)

{

   int i, j;

   int min_dist =30000;

   for (i = 0; i < n; i++)

   {

     for (j = i+1; j < n; j++)

     {

         if( (x == arr[i] && y == arr[j] ||

              y == arr[i] && x == arr[j]) && min_dist > abs(i-j))

         {

              min_dist = abs(i-j);

         }

     }

   }

   return min_dist;

}

int main()

{

    int arr[100];

    int n,i;

    int x;

    int y;

printf("Enter the no elements required in array\n ");

scanf("%d",&n);

printf("Enter the elements\n");

for(i=0;i<n;i++)

{

    scanf("%d",&arr[i]);

 }

printf("Enter the elements whose distance u want\n");

scanf("%d %d",&x,&y);

printf("Minimum distance between %d and %d is %d\n",x, y,minDist(arr, n, x, y));

    return 0;

} 

Output:

Enter the no elements required in array

 5

Enter the elements

1

2

3

4

5

Enter the elements whose distance u want

2

5

Minimum distance between 2 and 5 is 3

Read More

Fibonacci Series Algorithm

ALGORITHM F (n)

//Computes the nth Fibonacci number recursively by using its 

definition

//Input: A nonnegative integern

//Output: The nth Fibonacci number

if n ≤ 1 return n

else return F(n - 1) + F(n - 2)

 Other Method :

ALGORITHM Fib(n)

//Computes the nth Fibonacci number iteratively by using its definition
//Input: A nonnegative integer n

//Output: The nth Fibonacci number
F [0] ← 0;
 F [1] ← 1
for i ← 2 to n do
F [i] ← F [i - 1] + F [i - 2]
return F [n]

C program:

#include <stdio.h>

int main()

{

    int i, n, t1 = 0, t2 = 1, nextTerm;

    printf("Enter the number of terms: ");

    scanf("%d", &n);

    printf("Fibonacci Series: ");

    for (i = 1; i <= n; ++i)

    {

        printf("%d, ", t1);

        nextTerm = t1 + t2;

        t1 = t2;

        t2 = nextTerm;

    }

    return 0;

}

Output:

Enter the number of terms: 10

Fibonacci Series: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34

Read More