sieve of eratosthenes

Sieve of Erathosthenes : a find of quick ways to generate primes upto generally less than a million . below is the code for it .

what the sieve of eratosthenes does it that it eliminates all the multiples of previously determined primes .

optimization 1: start eliminating numbers  for prime i starting from i*i
optimization 2: i ends at i*i<upper since any composite below upper will atleast have one prime factor below sqrt(upper)
optimization 3 : any prime can be of type 6k+1 or 6k+5 only .

Using these optimization I have coded the following program which on my i-5 machine takes 2.5s to calculate primes upto 9e7.

Permutations

Hey following is a method using backtracking to print all permutations of a number in C++.

// A program using backtracking to generate premutations of 1,n numbers .

#include <cstdio>

#define MAXCANDIDATES 20

void backtrack(int a[],int k,int n);

int is_a_solution(int k,int n);

void process_solution(int a[],int n);

void construct_candidates(int a[],int c[],int k,int n, int *ncandidates);

int main()
{
    int n;
    scanf("%d",&n);
    int a[n+1];
    for(int i=1;i<n;i++)a[i]=0;
    backtrack(a,0,n+1);
    return 0;
}

int is_a_solution(int k,int n)
{
return (k==(n-1));
}

void process_solution(int a[],int n)
{
     printf("{");
     for(int i=1;i<n;i++) printf("%d,",a[i]);
     printf("\b}\n");
}

void construct_candidates(int a[],int c[],int k,int n,int *ncandidates)
{  
     bool in_perm[n];
     for(int i=1;i<n;i++)in_perm[i]=false;
     for(int i=1;i<k;i++)in_perm[a[i]]=true;
   
     *ncandidates =0;
     for(int i=1;i<n;i++){
           if(!in_perm[i]){
                           c[(*ncandidates)++]=i;
           }
   
     }
}
void backtrack(int a[],int k,int n)
{
     int c[MAXCANDIDATES];
     int ncandidates;
   
     if(is_a_solution(k,n)){
             process_solution(a,n);
     }
     else {
          k=k+1;
          construct_candidates(a,c,k,n,&ncandidates);
          for(int i=0;i<ncandidates;i++){
             a[k]=c[i];
             backtrack(a,k,n);
             }
     }    
}