count distinct prime factors

Question

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 :-

#include<stdio.h>
#include<math.h>
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<1000;i+=2)    
    {
            if(!prime[i])
            {
                    P[k++]=i;
                    for(j=i*i;j<100000;j+=i+i)    
                            prime[j] = 1;
            }
    }
    for(i=1001;i<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<=100000;i++) {
     count=0;
     root=i/2+1;
     for(j=0;P[j]<=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<10000;i++) printf("%d  ,",fact[i]);
 return 0;
}

Answer 1

You can easily adapt the sieve of Erasthotenes to count the number of prime factors a number has.

Here's an implementation in C, along with some tests:

#include <stdio.h>

#define N 100000

static int factorCount[N+1];

int main(void)
{
    int i, j;

    for (i = 0; i <= N; i++) {
        factorCount[i] = 0;
    }

    for (i = 2; i <= N; i++) {
        if (factorCount[i] == 0) { // Number is prime
            for (j = i; j <= N; j += i) {
                factorCount[j]++;
            }
        }
    }

    printf("2 has %i distinct prime factors\n", factorCount[2]);
    printf("10 has %i distinct prime factors\n", factorCount[10]);
    printf("11111 has %i distinct prime factors\n", factorCount[11111]);
    printf("12345 has %i distinct prime factors\n", factorCount[12345]);
    printf("30030 has %i distinct prime factors\n", factorCount[30030]);
    printf("45678 has %i distinct prime factors\n", factorCount[45678]);

    return 0;
}

Answer 2

You can definitely do better by making a sieve of Eratosthenes.

In Python

N = 100000
M = int(N**.5)                         # M is the floor of sqrt(N)
nb_of_fact = [0]*N
for i in xrange(2,M):
    if nb_of_fact[i] == 0:             # test wether i is prime
        for j in xrange(i,N,i):        # loop through the multiples of i
            nb_of_fact[j] += 1
for i in xrange(M,N):
    if nb_of_fact[i] == 0:
        nb_of_fact[i] = 1

At the end of the loop, nb_of_fact[i] is the number of prime factors of i (in particular it is 1 if and only if i is prime).

Older wrong version

N = 100000
nb_of_fact = [1]*N
for i in xrange(2,N):
    if nb_of_fact[i] == 1:             # test wether i is prime
        for j in xrange(2*i,N,i):      # loop through the multiples of i
            nb_of_fact[j] += 1