Question: https://codility.com/demo/take-sample-test/count_semiprimes
Question Name: CountSemiprimes
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | def solution(N, P, Q): from math import sqrt # Find out all the primes with Sieve of Eratosthenes prime_table = [False]*2+[True]*(N-1) prime = [] prime_count = 0 for element in xrange(2, int(sqrt(N))+1): if prime_table[element] == True: prime.append(element) prime_count += 1 multiple = element * element while multiple <= N: prime_table[multiple] = False multiple += element for element in xrange(int(sqrt(N))+1, N+1): if prime_table[element] == True: prime.append(element) prime_count += 1 # Compute the semiprimes information semiprime = [0] * (N+1) # Find out all the semiprimes. # semiprime[i] == 1 when i is semiprime, or # 0 when i is not semiprime. for index_former in xrange(prime_count-1): for index_latter in xrange(index_former, prime_count): if prime[index_former]*prime[index_latter] > N: # So large that no need to record them break semiprime[prime[index_former]*prime[index_latter]] = 1 # Compute the number of semiprimes until each position. # semiprime[i] == k means: # in the range (0,i] there are k semiprimes. for index in xrange(1, N+1): semiprime[index] += semiprime[index-1] # the number of semiprimes within the range [ P[K], Q[K] ] # should be semiprime[Q[K]] - semiprime[P[K]-1] question_len = len(P) result = [0]*question_len for index in xrange(question_len): result[index] = semiprime[Q[index]] - semiprime[P[index]-1] return result |
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.
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!
AND http://stackoverflow.com/questions/864603/python-while-loop-condition-evaluation
The disadvantage of a*a is, that it can overflow. But not in Python! (I love that language :D)
But if we use sqrt() in another way, it will be quicker than a*a:
This is my solution:
Thanks for sharing!
wow .this is so smart.
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)
You are *** for me 😀
Thanks! That’s too much for me 🙂
Hello Sheng, Here is my java solution 🙂 (100)
Hello Sheng, here is my solution in Python
This is my 100% C++ solution.
https://app.codility.com/demo/results/trainingGMDSR5-Y5D/
Note that we need to prevent overflow when selecting semiprimes