Best Fit algorithm implementation with Binary search Tree

Hey Guys ,
Since last two days , I was busy in an assignment based on the topic of Bin packing problem .
So in this post I am going to explain you about the Bin Packing and Implementing it with best fit algorithm.

So what is actually bin packing ??

It is simply putting a given number of objects into bins of given or maybe variable size so that minimum number of bins are used . It is a real life problem . Bin picking is used various aspects of daily problems.For example suppose there are many number of trucks and ith truck has a capacity of size Mi . Now you have to transport N objects of varying sizes via these trucks . The question is that you have to use minimum number of trucks possible .

If you go through this wikipedia link , you will read that bin packing is a Combinatorial N-P Hard problem . If you aren't familiar with the two big words in the previous line  don't worry , Most of us  too ,aren't familiar with  them . First let me tell you about what does Combinatorial means . It is actually derived from the word Combinatorics  . Combinatorics is a branch of High level Mathematics . In layman terms , the motto of Combinatorics  is to determine how many things are of a kind without actually counting them.

Now what is N-P hard problem ??

It is a very hard term for me  to define . For the layman answer I will post this answer of Quora 

"

To keep things simple, let's just talk about problems with "yes/no" answers.

For some problems we can describe a step-by-step procedure to solve them, and we know that if we use that procedure, it won't take so long that there's no hope of success. For example: "Are there at least ten red houses in your neighborhood?" We can take a walk and count every red house we pass, and eventually we'll either count to ten or walk through the whole neighborhood without seeing ten red houses.

The collection of all of these problems is called "P", and in addition to being able to solve each of them easily enough, we can also fairly easily check the way it was answered. But checking isn't the same as finding an answer -- often it seems easier -- so we have a different name for the group of "problems we can check easily enough", and that name is "NP".

What we don't know is whether being able to check the answer fast enough also means we can find a fast enough way to solve it. Some problems seem harder. For example: "If we only have ten colors to choose from, could we paint everybody's house in the neighborhood so that nobody's house is the same color as any of their friends' houses?" It seems a lot more complicated. The color I choose for my house might wind up deciding the color for somebody on the other side of town whom I've never met. After fifty people have picked their colors, we might find out that there are two friends who'd have to have the same color because of their other friends; then we'd have to back up and start over! But if somebody suggests what colors we should paint everybody's houses, we can still check easily enough to see if their idea works: just go around and ask each person if their house would be the same color as any of their friends' houses.

So we have these hard problems, and we're still not sure if we'll ever find a way to solve them fast enough. This group of hard problems are called "NP-hard". Some are so big and complicated that they're not even in NP: if somebody gives you an answer, you still couldn't come up with a fast enough way to check it. Because we know those are too hard, we use the name "NP-complete" to mean "NP-hard but still in NP", when we want to talk about problems that seem really hard, but aren't so complicated that we couldn't check an answer if we had it.

And the big question nobody has figured out yet is, "Are all the NP-complete problems actually only as hard as the P problems?" (We think they're harder, but we aren't sure.) If you can come up with a good enough way to solve one of those NP-complete problems -- the ones we only know how to check quickly enough -- then you'd become pretty famous for it!"

Moving further towards the problem :

So by now you know that bin packing problem is such that you can't easily check whether the solution is optimum or not .

There are several algorithms which provide a solution for the bin packing .

They are devided in 2 parts :

1. Online Algorithm :

                                 These algorithms are used where items arrive at run time  i.e one at a time . Each item must be put into a bin before considering the next item . These algorithms include : 

a) Next Fit

b) First Fit

c) Best Fit

2.Offline Algorithm : Here we have all the items at once and then we have to find the optimum solution for it . Mainly, First Fit decreasing algorithm is used for these types of problems.

I will be explaining the Online Algorithms in this post .

a) Next Fit :

This algo checks the  every element  before putting them into bins that whether it fits in the same bin as the last item . Uses only if it does not.

 Here is the code below : 

#include <iostream>

using namespace std;

 

// Returns number of bins required using next fit

// online algorithm

int nextFit(int weight[], int n, int c)

{

   // Initialize result (Count of bins) and remaining

   // capacity in current bin.

   int res = 0, bin_rem = c;

 

   // Place items one by one

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

   {

       // If this item can't fit in current bin

       if (weight[i] > bin_rem)

       {

          res++;  // Use a new bin

          bin_rem = c - weight[i];

       }

       else

         bin_rem -= weight[i];

   }

   return res;

}

int main()

{

    int weight[] = {2, 5, 4, 7, 1, 3, 8};

    int c = 10;

    int n = sizeof(weight) / sizeof(weight[0]);

    cout << "Number of bins required in Next Fit : "

         << nextFit(weight, n, c);

    return 0;

}

Number of bins required in Next Fit : 4

b) First Fit:
When processing the next item, see if it fits in the same bin as the last item. Start a new bin only if it does not.

#include <iostream> using namespace std;   // Returns number of bins required using first fit // online algorithm int firstFit(int weight[], int n, int c) {     // Initialize result (Count of bins)     int res = 0;       // Create an array to store remaining space in bins     // there can be at most n bins     int bin_rem[n];       // Place items one by one     for (int i=0; i<n; i++)     {         // Find the first bin that can accommodate         // weight[i]         int j;         for (j=0; j<res; j++)         {             if (bin_rem[j] >= weight[i])             {                 bin_rem[j] = bin_rem[j] - weight[i];                 break;             }         }           // If no bin could accommodate weight[i]         if (j==res)         {             bin_rem[res] = c - weight[i];             res++;         }     }     return res; }   // Driver program int main() {     int weight[] = {2, 5, 4, 7, 1, 3, 8};     int c = 10;     int n = sizeof(weight) / sizeof(weight[0]);     cout << "Number of bins required in First Fit : "          << firstFit(weight, n, c);     return 0; }Output:

Number of bins required in First Fit : 4

c) Best Fit:
The idea is to places the next item in the *tightest* spot. That is, put it in the bin so that smallest empty space is left.

// C++ program to find number of bins required using // Best fit algorithm. #include <bits/stdc++.h> using namespace std;   // Returns number of bins required using best fit // online algorithm int bestFit(int weight[], int n, int c) {     // Initialize result (Count of bins)     int res = 0;       // Create an array to store remaining space in bins     // there can be at most n bins     int bin_rem[n];       // Place items one by one     for (int i=0; i<n; i++)     {         // Find the best bin that ca\n accomodate         // weight[i]         int j;           // Initialize minimum space left and index         // of best bin         int min = c+1, bi = 0;           for (j=0; j<res; j++)         {             if (bin_rem[j] >= weight[i] &&                     bin_rem[j] - weight[i] < min)             {                 bi = j;                 min = bin_rem[j] - weight[i];             }         }           // If no bin could accommodate weight[i],         // create a new bin         if (min==c+1)         {             bin_rem[res] = c - weight[i];             res++;         }         else // Assign the item to best bin             bin_rem[bi] -= weight[i];     }     return res; }   // Driver program int main() {     int weight[] = {2, 5, 4, 7, 1, 3, 8};     int c = 10;     int n = sizeof(weight) / sizeof(weight[0]);     cout << "Number of bins required in Best Fit : "          << bestFit(weight, n, c);     return 0; }

Implementing the best fit using a binary search tree gives a proper optimum solution for bin packing .

Below is the code :

#include <iostream>
#include<malloc.h>
using namespace std;

int count =0; // count of the number of bins de leted

int count_of_bins = 0; // it is the count of bins still  present in the Tree and has been used atleast once
// we will use the flag value of each node to alculate count_of_bins

struct node {

int size; // This will store the size of the bins
int flag; // this flag will check whether the bin has been used at least once or not . If used , flag =1 else flag =0
struct node  *left; // pointer to the left node
struct node *right; // pointer to the right node

};


struct node *Create_New_Node(int block_size,int flagval)  // This function will create a new bin of the capacity of the provided size
{

struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->size = block_size ; temp->flag = flagval;
temp->left = temp->right = NULL;

return temp;

}



/* For Inserting a new bin in the tree */
struct node* insert(int block_size,int flag, struct node *Root){

//cout<<flag<<endl;
if(Root==NULL) return Create_New_Node( block_size,flag);
if(block_size<=Root->size)
{
Root->left = insert(block_size,flag,Root->left) ;
}
if(block_size>Root->size)
{
Root->right = insert(block_size,flag,Root->right) ;
}
return Root;

}
/* Searching a particular bin by its size */

struct node* search(struct node* root, int block_size)
{
    // Base Cases: root is null or size is present at root
    if (root == NULL || root->size == block_size)
       return root;
   
    // size is greater than root's size
    if (root->size < block_size)
       return search(root->right, block_size);

    // size is smaller than root's size
    return search(root->left, block_size);
}



/*  For the inorder traversal of the Binary Search Tree */

void inorder(struct node *Root)
{
    if (Root != NULL)
    {
        inorder(Root->left);
        printf("%d ", Root->size);
        inorder(Root->right);
    }
}


void count_of_used_bins(struct node *Root)
{
    if (Root != NULL)
    {
        count_of_used_bins(Root->left);


if(Root->flag==1)
{
//cout<<Root->size<<"  ";
count_of_bins++;
}
     
       count_of_used_bins(Root->right);
    }
}



struct node * minValueNode(struct node* node)
{
    struct node* current = node;

    /* loop down to find the leftmost leaf */
    while (current->left != NULL)
        current = current->left;

    return current;
}

/*  This function deletes the  bin of that particular size
   and returns the new Root */

// to have a better understanding visit : http://quiz.geeksforgeeks.org/binary-search-tree-set-2-delete/
struct node* deleteNode(struct node* Root, int block_size)
{
    // base case
    if (Root == NULL) return Root;

    // If the size to be deleted is smaller than the Root's size,
    // then it lies in left subtree
    if (block_size < Root->size)
        Root->left = deleteNode(Root->left, block_size);

    // If the size to be deleted is greater than the Root's size,
    // then it lies in right subtree
    else if (block_size > Root->size)
        Root->right = deleteNode(Root->right, block_size);

    // if size is same as Root's size, then This is the node
    // to be deleted
    else
    {
        // node with only one child or no child
        if (Root->left == NULL)
        {
            struct node *temp = Root->right;
            free(Root);
            return temp;
        }
        else if (Root->right == NULL)
        {
            struct node *temp = Root->left;
            free(Root);
            return temp;
        }

        // node with two children: Get the inorder successor (smallest
        // in the right subtree)
        struct node* temp = minValueNode(Root->right);

        // Copy the inorder successor's content to this node
        Root->size = temp->size;

        // Delete the inorder successor
        Root->right = deleteNode(Root->right, temp->size);
    }
    return Root;
}


/* This function finds that bin which will have optimum capacity for the required file*/


void findClosestNode(struct node *root, int value, int *min){
    if(!root)
{
  int required_node_size = value + *min;
int size_left = *min;
return ;

}
    int diff = root->size - value;
 
    if((*min > diff)&&(diff>=0)){
        *min = diff;
    }
    /* Case 1 : Look for in left subtree */
 
    if(root->size > value)
        findClosestNode(root->left, value, min);
    else
    /* Case 2 : Look for in right subtree */
        findClosestNode(root->right, value, min);
}
 


int main()
{
int num_of_bins;
cout<<"input the number of bins : ";
cin>>num_of_bins;
cout<<endl;
int num_of_files;
int arr[num_of_bins];
int maxsize = 0; //this will be used to find  the maximum size  available among  the bins
struct node *Root  = NULL;

cout<<"input the size of first bin:  ";
cin>>arr[0]; // creating the Root of the binary search tree
if(arr[0]>maxsize){maxsize = arr[0];}
Root = insert(arr[0],0,Root);
int i;
for(i=1;i<num_of_bins;i++)
{
cout<<"input the size of  bin no .  "<<(i+1)<<": ";
cin>>arr[i];cout<<endl;
if(arr[i]>maxsize){maxsize = arr[i];}
Root = insert(arr[i],0,Root);
}
maxsize = maxsize + 100000 ; //inceasing the max size by 100000
int maxcopy = maxsize;
cout<<"the initial inorder set of bin size is : ";
inorder(Root);cout<<endl;
cout<<"input the number of files : ";
cin>>num_of_files;
cout<<endl;
int barr[num_of_files];



for(i=0;i<num_of_files;i++)
{
maxcopy = maxsize;
cout<<"input the size of  file no .  "<<(i+1)<<": ";
cin>>barr[i];cout<<endl;
findClosestNode(Root,barr[i],&maxcopy);
if(maxcopy!=0)
{
int ans = barr[i] + maxcopy;

Root = deleteNode(Root,ans);
Root = insert(maxcopy,1,Root);
}
if(maxcopy==0){
Root = deleteNode(Root,barr[i]);
count++;
}

}
count_of_used_bins(Root);
cout<<endl;
cout<<"ans is "<<count<<endl;
cout<<"othe one is : "<<count_of_bins<<endl;
cout<<"Number of Bins used are : "<<(count_of_bins + count )<<endl;
cout<<"the final inorder set of bin size is : ";
inorder(Root);cout<<endl;

return 1;
}

My encounter with ZIO

Hey friends , this time I am gonna tell you about ZIO .
Most of you might be familiar with it . However In this post I am gonna talk about ZIO .

What is it ???

Many of us( Indians :) ) would be familiar with science olympiad , math olympiad . There is a similar olympiad in the field of Computer Science . It is better called as Indian Computing Olympiad .

 The Indian Computing Olympiad is a nationwide competition organized annually by IARCS(Indian Association For Research in Computer Science ). The goal of the competition is to identify school students with outstanding skills in algorithms and computer programming. This competition is open for all students upto class 12.

The  Indian Computing Olympiad is used to select the team of four students to represent India at the International Olympiad for Informatics  (IOI). IOI is one of the twelve international Science Olympiads held annually. 

The IOI is held in two subsequent rounds :
1. (ZOI)The Zonal Informatics Olympiad (ZIO) is a written exam. held at centres across the country. 

2. The Zonal Computing Olympiad (ZCO), a programming contest.

Students selected  in INOI are trained for IOI .

for further info you can refer to this link of IOI


Yesterday I came thorugh some past year subjective questions  of ZIO . 
Believe me , those questions where so interesting and mind freaking as well as tough . The questions use your algorithmic skills and problem skills . If you have free time to kill , I would suggest  you to go through the previous year papers and try to solve them . 
I would write one of such questions here :

A binary string of length N is a sequence of 0s and 1s. For example, 01010 is a binary string of length 5. For a string A we write Ai to refer to the letter at the i th position. Positions are numbered starting from 1. For example, if A = 01010 then A1 = 0 and A4 = 1. Let A be a string of length N. We say that a string B is a substring of A if B = Ai A(i+1)...Aj for some 1 ≤ i ≤ j ≤ N. So, 1 is a substring of A = 01010, since 1 = A2. The string 101 is a substring of A because 101 = A2, A3 ,A4. In this problem you have to count the number of binary strings of length N which contain 11011 as a substring. Take, for example, N = 6. We have 4 binary sequences of length 6 which contain 11011 as a substring. They are 011011, 111011, 110110 and 110111. Therefore, the answer for N = 6 is 4. Your task is to report the answer for three values of N.
 (a) N = 9: How many binary strings of length 9 contain 11011 as a substring?
 (b) N = 10: How many binary strings of length 10 contain 11011 as a substring?
 (c) N = 11: How many binary strings of length 11 contain 11011 as a substring?
for answers   visit here . 
Don't think it as simple as it seems :) 

Thank you :) 

Rotating a point counter clockwise using rotation matrix

First of all you need to know what is a rotation matrix :

A rotation matrix is a matrix that is used to perform a rotation in Euclidean space. For matrix. rotates points in the XY-Cartesian plane counter-clockwise through an angle θ about the origin of the Cartesian coordinate system.
For example : to rotate through 180 degree ,









This above given matrix is called as rotation matrix . This matrix multiplication will give the new position of the initial point(or vector ) after rotation.


// rotate p by theta degrees CCW w.r.t origin (0, 0)
point rotate(point p, double theta) {
double rad = DEG_to_RAD(theta);
// multiply theta with PI / 180.0
return point(p.x * cos(rad) - p.y * sin(rad),

p.x * sin(rad) + p.y * cos(rad)); }

Finding Prime Factors

Hello Everyone ,
   
In this post we will know how to find prime factors of a given number in a efficient way .
I assume that you know about the algorithm "Sieve of Eratosthenes" , if not then click here .
In this method we have the list of prime numbers generated from the above named algorithm.
Suppose we have a number N . A better way to find prime factors of this number is to express this number N as : N = PF x N'  , where PF is a prime factor and N' = N/PF . We keep doing so until N!=1
To speed up the process  even further, we utilize the divisibility property that there is no divisor greater than √N so we only repeat the process of finding prime factors until P F ≤ √N Stopping at √N entails a special case: If (current PF)^2  >N and N is still not 1 , then N is the last prime factor The code below takes in an  integer N and returns the list of prime factors.

#include <bitset>
#include<iostream>
#include<stdio.h>
#include<vector>
#define ll long long
using namespace std;
long long int _sieve_size;
bitset<10000010> bs;
vector<long long int> primes;

void sieve(long long int upperbound)
{
  // create list of primes in [0..upperbound]
 _sieve_size = upperbound + 1; // add 1 to include upperbound
 bs.set(); // set all bits to 1
 bs[0] = bs[1] = 0;// except index 0 and 1
 for (long long int  i = 2; i <= _sieve_size; i++)
 {
  if (bs[i])
  {
   // cross out multiples of i starting from i * i!
   for (long long int j = i * i; j <= _sieve_size; j += i)
   {
    bs[j] = 0;
   }
   primes.push_back((long long int)i);
   // add this prime to the list of primes
  }
 }
}


vector<ll int> primeFactors(ll N)
{
    vector<ll int>factors;
    ll PF_idx = 0 ,PF = primes[PF_idx];
    while(PF*PF<=N)   //stop at sqrt N
    {
        while(N%PF==0)
        {
            N = N/PF;
            factors.push_back(PF); // storing the prime factors in the vetors
        }
        PF = primes[++PF_idx];
    }
    if(N!=1){factors.push_back(N); }// in case when N is a prime
    return factors;
}
int main()
{


 sieve(10000000);
 vector<ll int>r = primeFactors(2147483647);
 for(vector<ll int>::iterator i = r.begin();i!= r.end();i++)
 {
    printf("> %lld\n", *i); // worst case as  2147483647 is a prime
 }

r = primeFactors(136117223861LL); // slower
 for(vector<ll int>::iterator i = r.begin();i!= r.end();i++)
 {
   printf("# %lld\n", *i);
 }

 r = primeFactors(36);  // faster,
  for(vector<ll int>::iterator i = r.begin();i!= r.end();i++)
 {
   printf("! %lld\n", *i);
 }

}

Computing Binomial Coefficients i.e C(n,k)

There are many problems where we have to compute C(n,k) i.e  ( (n!)/( (n-k)! *(k!) ) ).
However,
computing C(n, k) can be a challenge when n and/or  k are large. There are several tricks
like: Making k smaller (if k > n − k, then we set k = n − k) because n C k = n C (n−k) .
 During intermediate computations, we divide the numbers first before multiply it with the
 next number; or use BigInteger technique (last resort as BigInteger operations are slow).
But there is another method to which we all are familiar but don't actually remember .
We can use  Pascal’s Triangle, a triangular array of binomial coefficients. The leftmost and
rightmost entries at each row are always 1. The inner values are the sum of two values directly
 above it, as shown for row n = 5 below : The value of ith entry of line number n is C(n,i);

          1               n= 0
        1   1             n= 1
      1   2   1           n= 2
    1   3   3   1         n = 3
   1  4   6   4   1       n = 4
 1  5   10  10  5   1     n = 5

The value of ith entry of line number n is C(n,i).
The below given code implements the formation of the pascal's triangle using a 2D array of size n*n.
The time complexity is of O(n^2) ,  but it's better than the general method of computing C(n,k) using multiplication.

#include<iostream>
#include<stdio.h>
using namespace std;

void printPascal(int n)
{
  int arr[n][n];
  for (int line = 0; line <= n; line++)
  {
    // Every line has number of integers equal to line number
    for (int i = 0; i <= line; i++)
    {
      // First and last values in every row are 1
      if (line == i || i == 0)
           arr[line][i] = 1;
      else // Other values are sum of values just above and left of above
           arr[line][i] = arr[line-1][i-1] + arr[line-1][i];
      printf("%d ", arr[line][i]);
    }
    printf("\n");
  }
}
int main()
{
  printPascal(5);
}
output :

1  
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1 
1 5 10 10 5 1 

See this  triangle for understanding the above given code.

After going through the above topic ,  go through this link , and  first try to solve this question using bit shift operator (<<) . Why are you getting wrong answer ? Try using pow() function.You would be getting correct answer . To know the difference  between pow(2,n ) and  1<<n , go through This Link

Thank you and keep coding :)

Bitset in STL and Algorithms for finding Prime numbers

Hello  Guys ,
   Let's talk about the mathematics used in coding contests , like checking for prime numbers, finding prime factors , LCM , GCD ,Factorials  e.t.c
In this post I will be talking about an easy method to check whether a number is prime or not . For this I will be using  the famous  algorithm " Sieve of Eratosthenes" invented by Eratosthenes of Alexandria.

Before moving further I would like you to know what is 'bitset' . If you are familiar with this , you can jump to the next topic .

A bitset stores bits (elements with only two possible values: 0 or 1 , i.e true or false ). It  is an array of bool but each Boolean value is not stored separately instead bitset optimizes the space such that each bool takes 1 bit space only, so space taken by bitset bs is less than that of bool bs[N] and vector bs(N)  i.e  each element occupies only one bit (which, on most systems, is eight times less than the smallest elemental type: char).
Due to this single bit , the operation performed on bitset is faster than that of array and vector . We can access the element of bitset just like an index of an array or vector . But there is a major difference between bitset and array .
bitset starts its indexing backward that is for 10110, 0 are at 0th and 3rd indices whereas 1 are at 1st 2nd and 4th indices.

The following code explains most of the basic member functions of bitset and there usage :

#include<iostream>
#include<bitset>
#define M 32
using namespace std;
int main()
{

// default constructor initializes with all bits 0
    bitset<M> bset1;
     // bset2 is initialized with bits of 20
    bitset<M> bset2(20);

    // bset3 is initialized with bits of specified binary string
    bitset<M> bset3(string("1100"));

    // cout prints exact bits representation of bitset
    cout << bset1 << endl;  // 00000000000000000000000000000000
    cout << bset2 << endl;  // 00000000000000000000000000010100
    cout << bset3 << endl;  // 00000000000000000000000000001100
    cout << endl;

    // declaring set8 with capacity of 8 bits

    bitset<8> set8;    // 00000000

    // setting first bit (or 6th index)
    set8[1] = 1;    // 00000010
    set8[4] = set8[1];   //  00010010
    cout << set8 << endl;

    // count function returns number of set bits in bitset
    int numberof1 = set8.count();

    // size function returns total number of bits in bitset
    // so there difference will give us number of unset(0)
    // bits in bitset
    int numberof0 = set8.size() - numberof1;
    cout << set8 << " has " << numberof1 << " ones and "
         << numberof0 << " zeros\n";

    // test function return 1 if bit is set else returns 0
    cout << "bool representation of " << set8 << " : ";
    for (int i = 0; i < set8.size(); i++)
        cout << set8.test(i) << " ";

    cout << endl;

    // any function returns true, if atleast 1 bit
    // is set
    if (!set8.any())
        cout << "set8 has no bit set.\n";

    if (!bset1.any())
        cout << "bset1 has no bit set.\n";

    // none function returns true, if none of the bit
    // is set
    if (!bset1.none())
        cout << "bset1 has all bit set\n";

    // bset.set() sets all bits
    cout << set8.set() << endl;

    //  bset.set(pos, b) makes bset[pos] = b
    cout << set8.set(4, 0) << endl;

    // bset.set(pos) makes bset[pos] = 1  i.e. default
    // is 1
    cout << set8.set(4) << endl;

    // reset function makes all bits 0
    cout << set8.reset(2) << endl;
    cout << set8.reset() << endl;

    // flip function flips all bits i.e.  1 <-> 0
    // and  0 <-> 1
    cout << set8.flip(2) << endl;
    cout << set8.flip() << endl;

    // Converting decimal number to binary by using bitset
    int num = 100;
    cout  << "\nDecimal number: " << num
         << "  Binary equivalent: " << bitset<8>(num);
  cout<<endl;
    return 0;
}

Output :

00000000000000000000000000000000
00000000000000000000000000010100
00000000000000000000000000001100

00010010
00010010 has 2 ones and 6 zeros
bool representation of 00010010 : 0 1 0 0 1 0 0 0
bset1 has no bit set.
11111111
11101111
11111111
11111011
00000000
00000100
11111011

Decimal number: 100 Binary equivalent: 01100100


Now coming back to our initial discussion regarding  prime numbers :

First, this Sieve algorithm sets all numbers in the range to be ‘probably prime’ but set
numbers 0 and 1 to be not prime. Then, it takes 2 as prime and crosses out all multiples
of 2 starting from 2 × 2 = 4, 6, 8, 10, . . . until the multiple is greater than N. Then it takes
the next non-crossed number 3 as a prime and crosses out all multiples of 3 starting from
3 × 3 = 9, 12, 15, . . .. Then it takes 5 and crosses out all multiples of 5 starting from 5 × 5 =
25, 30, 35, . . .. And so on . . .. After that, whatever left uncrossed within the range [0..N]
are primes. This algorithm does approximately (N× (1/2 + 1/3 + 1/5 + 1/7 + . . . + 1/last
prime in range ≤ N)) operations. The time complexity is of roughly O(N log log N).
Generating a list of primes ≤ 10K using the sieve is fast , we opt to use sieve for smaller
 primes and for the larger prime numbers we use other methods which I will be discussing later .
 The code is as follows:

#include <bitset>
#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;
long long int _sieve_size;
bitset<10000010> bs; // 10^7 should be enough for most cases
vector<long long int> primes; // compact list of primes in form of vector<int>

void sieve(long long int upperbound)
{  
  // create list of primes in [0..upperbound]
_sieve_size = upperbound + 1; // add 1 to include upperbound
bs.set(); // set all bits to 1
bs[0] = bs[1] = 0;// except index 0 and 1
for (long long int  i = 2; i <= _sieve_size; i++)
{
if (bs[i])
{
// cross out multiples of i starting from i * i!
for (long long int j = i * i; j <= _sieve_size; j += i)
{
bs[j] = 0;
}
primes.push_back((int)i);
// add this prime to the list of primes
}
}
}

bool isPrime(long long int N)
{
// a good enough deterministic prime tester
if (N <= _sieve_size) return bs[N];
// O(1) for small primes
cout<<(int)primes.size()<<endl;
for (int i = 0; i < (int)primes.size(); i++)

if (N % primes[i] == 0) return false;
return true;
// it takes longer time if N is a large prime!
}
// note: only work for N <= (last prime in vector  "primes")^2
// inside int main()
int main()
{


sieve(10000000);
// can go up to 10^7 (need few seconds)

printf("%d\n", isPrime(2147483647));
// 10-digits prime
printf("%d\n", isPrime(136117223861LL));
// not a prime, 104729*1299709
//How are we checking this for number which are > 10^7 ??
//Actually we cn check upto prime numbers < (10^7)^2!!! using this method
//because to check whether a number is prime number or not , all we need to check whether
// the number has any factor less than (number)^(0.5) or not

}

Thank you.Keep Coding :)