Solution to Count-Semiprimes by codility

28 Jan


Question Name: CountSemiprimes

10 thoughts on “Solution to Count-Semiprimes by codility

  1. 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?

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

  2. 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

    • 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().

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


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

  3. This is my solution:

  4. 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)

Leave a Reply

Your email address will not be published. Required fields are marked *