title: Finding number of k-prime numbers;
body: <p>Given a range <code>a</code> to <code>b</code> , and number <code>k</code>, find all the k-prime numbers between <code>a</code> to <code>b</code> [inclusive both]. 
  Definition of k-prime : A number is a k-prime if it has exactly k distinct prime factors. </p>
  
  <p>i.e. <code>a=4</code>, <code>b=10</code> <code>k=2</code> the answer is <code>2</code>. Since the prime factors of 6 are [2,3] and the prime factors of 10 are [2,5].</p>
  
  <p>Now here's my attempt</p>
  
  <pre><code>#include&lt;stdio.h&gt;
  #include&lt;stdlib.h&gt;
  int main(){
      int numOfInp;
      scanf("%d",&amp;numOfInp);
      int a,b,k;  
      scanf("%d %d %d",&amp;a,&amp;b,&amp;k);
      int *arr;
      arr = (int*)calloc(b+1,sizeof(int));
  
      int i=2,j=2,count=0; 
      //Count is the count of distic k prim factors for a particular number
      while(i&lt;=b){
          if(arr[i]==0){
              for(j=i;j&lt;=b;j=j+i){
                  arr[j]++;
              }
          }
          if(i&gt;=a &amp;&amp; arr[i]==k)
              count++;
          i++;
      }
      printf("%d\n",count);
      free(arr);
  
      return 0;
  }
  </code></pre>
  
  <p><strong>This problem is taken from <a href="http://www.codechef.com/JULY13/problems/KPRIME" rel="nofollow">Codechef</a></strong></p>
  
  <p>Here's what I've done, I take an array of size b, and for each number starting from 2, I do the following.</p>
  
  <p>For 2 check if <code>arr[2]</code> is 0, then <code>arr[2]++,arr[4]++,arr[6]++ ....</code> so on.</p>
  
  <p>For 3 check if <code>arr[2]</code> is 0, then <code>arr[3]++,arr[6]++,arr[9]++ ....</code> so on.</p>
  
  <p>Since <code>arr[4]</code> is not zero, leave it.</p>
  
  <p>In the end, the value <code>arr[i]</code> will give me the answer, i.e <code>arr[2]</code> is 1, hence 2 is 1-prime number, <code>arr[6]</code> is 2, hence 6 is 2-prime number.</p>
  
  <p>Questions: </p>
  
  <ol>
  <li>What is the complexity of this code, and can it be done in O(n)?</li>
  <li>Am I using Dynamic Programming here?</li>
  </ol>