Finding number of k-prime numbers;

Question

Given a range a to b , and number k, find all the k-prime numbers between a to b [inclusive both]. Definition of k-prime : A number is a k-prime if it has exactly k distinct prime factors.

i.e. a=4, b=10 k=2 the answer is 2. Since the prime factors of 6 are [2,3] and the prime factors of 10 are [2,5].

Now here's my attempt

#include<stdio.h>
#include<stdlib.h>
int main(){
    int numOfInp;
    scanf("%d",&numOfInp);
    int a,b,k;  
    scanf("%d %d %d",&a,&b,&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<=b){
        if(arr[i]==0){
            for(j=i;j<=b;j=j+i){
                arr[j]++;
            }
        }
        if(i>=a && arr[i]==k)
            count++;
        i++;
    }
    printf("%d\n",count);
    free(arr);

    return 0;
}

This problem is taken from Codechef

Here's what I've done, I take an array of size b, and for each number starting from 2, I do the following.

For 2 check if arr[2] is 0, then arr[2]++,arr[4]++,arr[6]++ .... so on.

For 3 check if arr[2] is 0, then arr[3]++,arr[6]++,arr[9]++ .... so on.

Since arr[4] is not zero, leave it.

In the end, the value arr[i] will give me the answer, i.e arr[2] is 1, hence 2 is 1-prime number, arr[6] is 2, hence 6 is 2-prime number.

Questions:

1. What is the complexity of this code, and can it be done in O(n)?
2. Am I using Dynamic Programming here?

Answer 1

The algorithm you are using is know as Sieve of Eratosthenes. It is a well known algorithm for finding prime numbers. Now to answer your questions :

1a) What is the complexity of this code

The complexity of your code is O(n log(log n)).

For and input of a and b the complexity of your code is O(b log log b). The runtime is due to the fact that you first mark b/2 number then b/3 then b/5 and so on. So your runtime is b * (1/2 + 1/3 + 1/5 + 1/7 + 1/11 + ... + 1/prime_closest_to_b). What we have there is a prime harmonic series which grows asymptotically as ln(ln(b+1)) (see here).

Asymptotically the upper bound is:

O(b * (1/2 + 1/3 + 1/5 + 1/7 +..)) = O(b) * O(log(log(b+1))) = O(b*log(log(b))

1b) Can it be done in O(n)

This is tricky. I would say that for all practical purposes an O(n log log n) algorithm is gonna be about as good as any O(n) algorithm, since log(log(n)) grows really really really slow.

Now, if my life depended on it I would try to see if I can find a method to generate all numbers up to n in a way where every operation generates a unique number and tells me how many unique prime divisors it has.

2) Am I using Dynamic Programming here?

Definition of dynamic programming from wikipedia says:

Dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems

The definition is quite broad, so it is unfortunately open to interpretation. I would say that this isn't dynamic programming, because you aren't breaking down your problem into smaller smaller sub-problems and using the results from those sub-problems to find the final answer.