title: count distinct prime factors
body: <p>I have to count number of distinct prime factors over 2 to 100000, Is there any fast method than what I am doing ?
  i.e.. 2 has 1 distinct prime factor 2
  10 has 2 distinct prime factor (2,5)
  12 has 2 distinct prime factor (2,3)
  My code :-</p>
  
  <pre><code>#include&lt;stdio.h&gt;
  #include&lt;math.h&gt;
  typedef unsigned long long ull;
  char prime[100000]={0};
  int P[10000],fact[100000],k;
  
  void sieve()
  {
      int i,j;
      P[k++]=2;
      for(i=3;i*i&lt;1000;i+=2)    
      {
              if(!prime[i])
              {
                      P[k++]=i;
                      for(j=i*i;j&lt;100000;j+=i+i)    
                              prime[j] = 1;
              }
      }
      for(i=1001;i&lt;100000;i+=2)    
              if(!prime[i])
                      P[k++]=i;
  }
  
  int calc_fact() {
    int root,i,count,j;
    fact[1]=fact[2]=fact[3]=1;
    for(i=4;i&lt;=100000;i++) {
       count=0;
       root=i/2+1;
       for(j=0;P[j]&lt;=root;j++) {
          if(i%P[j]==0)count++;
       }
       if(count==0) fact[i]=1;
       else fact[i]=count;
    }
   return 0;
  }
  int main(){
   int i;
   sieve();
   calc_fact(); 
   for(i=1;i&lt;10000;i++) printf("%d  ,",fact[i]);
   return 0;
  }
  </code></pre>