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 #include 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 ",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[…

Accepted Answer

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.

Finding number of k-prime numbers;

Solution

Problem