# Codility ‘CountSemiprimes’ Solution

##### Short Problem Definition:

Count the semiprime numbers in the given range [a..b]

SemiPrimes

##### Complexity:

expected worst-case time complexity isÂ O(N*log(log(N))+M);

expected worst-case space complexity is O(N+M)

##### Execution:

First get all semiprimes from an adaptation of the Sieve ofÂ Eratosthenes. Because we will be computing the difference many times a prefix sum is adequate. Get the number of semiprimes up to the point. The index P is decreased by 1 because we want to know all primes that start from P.

##### Solution:
```def sieve(N):
semi = set()
sieve = [True]* (N+1)
sieve[0] = sieve[1] = False

i = 2
while (i*i <= N):
if sieve[i] == True:
for j in xrange(i*i, N+1, i):
sieve[j] = False
i += 1

i = 2
while (i*i <= N):
if sieve[i] == True:
for j in xrange(i*i, N+1, i):
if (j % i == 0 and sieve[j/i] == True):
i += 1

return semi

def solution(N, P, Q):

semi_set = sieve(N)

prefix = []

prefix.append(0) # 0
prefix.append(0) # 1
prefix.append(0) # 2
prefix.append(0) # 3
prefix.append(1) # 4

for idx in xrange(5, max(Q)+1):
if idx in semi_set:
prefix.append(prefix[-1]+1)
else:
prefix.append(prefix[-1])

solution = []

for idx in xrange(len(Q)):
solution.append(prefix[Q[idx]] - prefix[P[idx]-1])

return solution
```

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

• Mikhail Manukhin

Martin,
This solution (analog on C#) gives me 100%,40% result.
Does your code give you the same or better result?

• You probably should optimise the appends to an array. The copies can slow you down.

• Mikhail Manukhin

I do not use dynamic collections at all, simple array is faster than HashSet, anything else is the same as in your solution:
https://codility.com/demo/results/trainingP2XX9H-NJH/
I wonder what is wrong in my solution…
BTW, I think than condition “j % i == 0” in line 17 is redundant in your code because it is always true.

• You are right. It is redundant, I did not notice. xrange is incremented by i and starts at i*i. Thanks!

• Pavle

I don’t think you need j % i == 0 condition on line 17, because you are starting from i*i and incrementing by i, so it’s always going to be divisible by i.