# Solution to Count-Semiprimes by codility

28 Jan

Question Name: CountSemiprimes

### 17 Replies to “Solution to Count-Semiprimes by codility”

1. Max says:

Great thinking! I came out with a similar reasoning on paper, but the double for is a very simple and easy way to calculate semiprimes, I was thinking of a clever way to it and there it is! All in all, I’ve found this problem much simpler than the previous, don’t you think?

• Sheng says:

Another possibility is: we gone through the previous question, get used to this kind of problems, and solve this with less effort.

2. Martin says:

I still haven’t figured the first question. But I refuse to look at your solution before I do :D. Mine for this question. I should learn to pre-allocate arrays as you do

I hope I will be able to solve all of them soon, as you did!
I believe that the use of

is preferred to

• Sheng says:

Pre-allocation will save you a loooooot of time. I tried.
But I did not try the “a*a <= N” and “a <= sqrt(N)”. “a <= sqrt(N)” only needs the sqrt() computation once, while “a*a <= N” will take the multiplication for many times. So I uesed sqrt().

• Sheng says:

UPDATE: you are right! “a*a <= N” is better!

• Martin says:

The disadvantage of a*a is, that it can overflow. But not in Python! (I love that language :D)

• Sheng says:

But if we use sqrt() in another way, it will be quicker than a*a:

3. Andrew says:

This is my solution:

• Sheng says:

Thanks for sharing!

• Mahdi says:

wow .this is so smart.

4. micropentium6 says:

Almost as same as Andrew’s solution: find the smallest prime divisor for every composite number, which was explained in 11.1. Factorization. Then, use this info to populate semiprime end at natural number i. Then we could find out the results for range search in O(1)

5. Ardi Nusawan says:

You are *** for me ðŸ˜€

• Sheng says:

Thanks! That’s too much for me ðŸ™‚

6. LarryJung says:

Hello Sheng, Here is my java solution ðŸ™‚ (100)

7. InJuKim says:

8. S Sathish Babu says:

Hello Sheng, here is my solution in Python

9. Luiz doleron says:

This is my 100% C++ solution.
https://app.codility.com/demo/results/trainingGMDSR5-Y5D/

Note that we need to prevent overflow when selecting semiprimes