Solution to Count-Semiprimes by codility

28 Jan


Question Name: CountSemiprimes

17 Replies to “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().

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

  5. Hello Sheng, Here is my java solution 🙂 (100)

  6. Hello Sheng, here is my solution in Python

  7. This is my 100% C++ solution.

    Note that we need to prevent overflow when selecting semiprimes

Leave a Reply

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

Please put your code into a <pre>YOUR CODE</pre> section. Thanks and Happy Coding!