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

A Java solution which scores 100% is as follow:

• Find the set of prime numbers which their products is not greater than N

• create semi-prime from them as a bit wise array of 0 and 1

• create a prefix sum of the semi-primes

• calculate the queries from P[i] to Q[i] in O(M)

The whole algorithm is of O(N * log(log(N)) + M) stated by the Codility's test result evaluation.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CountSemiPrime {

    public static void main(String[] args) {
        int[] P = new int[] {1, 4, 16};
        int[] Q = new int[] {26, 10, 20};
        System.out.println( Arrays.toString( new CountSemiPrime().solution( 26, P, Q ) ) );
    }

    public int[] solution(int N, int[] P, int[] Q) {

        Integer[] primes = sieve(N/2+1);

        int[] temp = new int[N+1];
        for (int i = 0; i < primes.length; i++) {
            for (int j = 0; j < primes.length; j++) {
                int semiPrime = primes[i] * primes[j];
                if(semiPrime <= N)
                    temp[semiPrime] = 1;
            }
        }

        int[] prefix = new int[N+1];
        for (int i = 1; i < temp.length; i++) {
            prefix[i] = temp[i] + prefix[i-1];
        }

        int[] retVal = new int[P.length];
        for (int i = 0; i < retVal.length; i++) {
            retVal[i] = prefix[Q[i]] - prefix[P[i]-1];
        }

        return retVal; 
    }


    public Integer[] sieve(int n) {

        boolean[] temp = new boolean[n+1];
        for (int i = 0; i < temp.length; i++) {
            temp[i] = true;
        }
        temp[0] = temp[1] = false;

        int i = 2;
        while (i * i <= n) {
            removeProducts( temp, i );
            i++;
        }

        List<Integer> ret = new ArrayList<>();
        for (int j = 0; j < temp.length; j++) {
            if(temp[j])
                ret.add( j );
        }

        return ret.toArray( new Integer[ret.size()] );
    }

    private void removeProducts(boolean[] temp, int i) {
        for (int j = i*i; j < temp.length; j++) {
            if(temp[j] && j % i == 0) {
                temp[j] = false;
            }
        }
    }
}

You can precompute an array A of size N+1, which stores at A[i] the number of semiprimes less than or equal to i. Then a query p, q can be computed immediately: the number of semiprimes between p and q (inclusive) is A[q] - A[p-1].

This array can be computed efficiently: let P be an array of primes less than or equal to N/2. Then (in java-like pseudocode):

A = new int[N+1]
for (int p : P) {
  for (int q : P) {
      if (p*q > N || q > p) break;
      A[p*q] = 1
  }
}

for (int i = 1; i <= N; i++)
    A[i] += A[i-1]

This works by marking the semiprimes with a 1 in the array, and then taking a cumulative sum. It runs in better than O(N^2) and worse than O(N) time -- there's about N/2logN primes in P, so the first part is O((N/logN)^2), and the summing-up is O(N). [Note: I guess the first part has better complexity than O((N/log N)^2) because of the early termination of the inner loop, but I've not proved that]. Computing the primes in P is O(N log log N) using the sieve of Erastothenes.

A Python version of this program takes 0.07s to precompute A for N=50000, and to perform 30000 queries. It gets a perfect score (100) when run on codility, and codility reports that it detects the code to be have complexity O(N log(log(N)) + M).

My solution uses Sieve of Eratosthenes such that smallest prime factor of number N is stored in the array Factor[N]. Then if Factor[N/Factor[N]] = 0, we have a semi prime number incrementing a sum scan. The entry r of the returned array will then be: A[r]=Inclusive_scan[Q[r]]-Inclusive_scan[P[r]-1].

Here the corresponding python code (100% task score):

def solution(N, P, Q):
 A=len(P)*[0]
 if N<4:
     return A
#Minimum prime factor of n stored in Factor[n]
 Factor = [0] * (N + 1)
 i = 2
 while (i * i <= N):
  if (Factor[i] == 0):
   k = i * i
   while (k <= N):
    if (Factor[k] == 0):
     Factor[k] = i;
    k += i
  i += 1
#Count semi prime numbers and store 
#sum scan in array Incluse_scan   
 Incluse_scan=[0] * (N + 1)
 cnt_semi=0
 for k in range(4,N+1):
     if Factor[k]!=0:
         d=int(k/Factor[k])
         if Factor[d]==0:
             cnt_semi+=1                 
     Incluse_scan[k]=cnt_semi   
#Do the difference of semi prime counters
 for r in range(0,len(P)):
     if(P[r]<=4):
       min_inclusive=0
     else:
       min_inclusive=P[r]-1 
     A[r]=Incluse_scan[Q[r]]-Incluse_scan[min_inclusive] 
 return A

Ruby 100% solution

require 'prime'
require 'set'

def solution(n, p, q)
    primes = Prime::EratosthenesGenerator.new.take_while {|i| i <= n/2 }
    sqrt = Math.sqrt(n)
    semiprimes = primes.each_with_index.inject(Set.new) do |acc, (e,i)|
      break acc if e > sqrt.to_i
      primes[i..-1].each{ |pr| e*pr > n ? break : acc << e*pr }
      acc
    end
    offsets = semiprimes.sort.each_with_index.inject([]) {|acc,(el,i)| acc[el] = i+1;acc  }

    p.each_with_index.inject([]) do |acc, (el,i)|
      next acc << 0 unless offsets[el..q[i]]

      left =  offsets[el..q[i]].detect{|a| a}
      next acc << 0 unless left

      right = offsets[el..q[i]].reverse_each.detect{|a| a}

      acc << ((left..right).size)
    end
end

this is my 100% solution in C++. you can find other answers in my github in cpp:

vector<int> getFactArr(int n) {
    vector<int> f(n+1, 0);
    f[1] = 1;
    int i = 2;
    while (i * i <= n) {
        if (f[i] == 0) {
            int k = i * i;
            while (k <= n) {
                if (f[k] == 0)
                    f[k] = i;
                k+=i;
            }
        }
        i++;
    }

    return f;
}

vector<int> solution(int N, vector<int> &P, vector<int> &Q) {
    vector<int> F = getFactArr(N);
    vector<int> prefix_semi_primes(N + 1, 0);

    for (int x = 1; x <= N; x++) {
        if (F[x] > 0 && F[x / F[x]] == 0)
            prefix_semi_primes[x]++;
        prefix_semi_primes[x] += prefix_semi_primes[x - 1];
    }

    const int M = P.size();
    vector<int> ans(M, 0);
    for (int i = 0; i < M; i++) {
        ans[i] = prefix_semi_primes[Q[i]] - prefix_semi_primes[P[i] - 1];
    }

    return ans;
}

This was an interesting problem. I tried it and got 88% score.

Here is my strategy:

• I used Sieve of Eratosthenes for getting a BitSet for primes.
• Now I looped over that BitSet and added all the primes in a primeList.
• My strategy for finding semi-primes was a bit interesting and I reached to this strategy incrementally.

private static boolean isSemiPrime(int n) {
    if(n==1 || n==0 || primeBitSet.get(n))
        return false;
    int firstFactor = findFirstFactor(n);
    if(firstFactor==0 || firstFactor==1)
        return false;
    return isPrime(n / firstFactor);
}

private static int findFirstFactor(int n) {

    for (int i = 0; i < primeList.size(); i++) {
        if (n % primeList.get(i) == 0)
            return primeList.get(i);
    }
    // should never be the case
    return 0;
}

I'm not very sure why I got 88% score. (What I'm missing)

But the most interesting and worth noting part was the strategy to check whether a given number is Semi-prime or not:

• Find the first prime factor of the given number
• Then checking that the quotient of the given number and the first-prime-factor is a prime or not.
• If it is prime, then the given number is a semi-prime, otherwise the given number is not a semi prime.

Note that I also did a very naive form of book-keeping where I made a cumulative array which stores the total number of semi-primes till index x. One time filling this array and answering each of the query in O(1) is again obvious optimization.

Not related to the solution, but my Task Score was 88%, Correctness 100% and Performance 80%. I'll be happy to hear suggestions and anything that I missed.

Hope this helps. :)

Here the Javascript version of the solution, but it is 55%:

function solution(N, P, Q) {

  function isPrime(num) {
    for(var i = 2; i < num; i++)
      if(num % i === 0) return false;
    return num > 1;
  }

  const min = Math.min(...P)
  const max = Math.max(...Q)
  const A = []
  for(let i=min;i<max;i++) {
      for(let j=min;j<max;j++) {
          if (isPrime(i) && isPrime(j)) {
              const prod = j * i
              if (prod > max) break
              if (A.includes(prod)) continue
              A.push(j * i)
          }
      }
  }

  const result = []
  for(let i=0;i<P.length;i++) {
      for(let j=P[i];j<=Q[i];j++) {
          result[i] = result[i] || 0
          if (A.includes(j)) {
              result[i]++
          }
      }
  }
  return result
}

I would like to mention that the method you use for finding primes is inefficient.

Your code:

private static List<Integer> getPrimes(int max) {
    List<Integer> primes = new ArrayList<>(max / 2);

**    for (int i = 0; i < max; i++)
**        if (isPrime(i))
**            primes.add(i);

    return primes;
}

private static boolean isPrime(int val) {
    if (val <= 1)
        return false;
    if (val <= 3)
        return true;

**    for (int i = 2, sqrt = (int)Math.sqrt(val); i <= sqrt; i++)
**        if (val % i == 0)
**            return false;

    return true;
}

I have marked the lines to pay attention to. I would do something like this:

private static List<Integer> getPrimes(int max) {
    List<Integer> primes = new ArrayList<>(max / 2);
    primes.add(2);

    for (int i = 3; i < max; i++)
        if (isPrime(i, primes))
            primes.add(i);

    return primes;
}

private static boolean isPrime(int val, List<Integer> primes) {
    int sqrtv = Math.sqrt(val);
    for (int i = 0; i < primes.length(); i++)
    {
        int prime = primes.get(i);
        if (val % primes.get(i) == 0)
        {
            return false;
        } else if (prime > sqrtv) {
            return true;
        }
    }

    return true;
}

This plays on the fact that:

1. the only call to isPrime is from getPrimes. getPrimes will always call val in ascending order.
2. by the time isPrime is called with the parameter val, getPrimes has already got a list of all primes that are smaller than val.
3. there's no point in dividing with non-primes when determining primes. If we already know that a number 'a' is not divisible by 2, then why bother with dividing it by 4, 6, 8 or 10? If we know it isn't divisible by 3, then it won't be divisible by 9... so all of the non-prime checks are filtered by using the previously calculated primes only to perform the checking.

Here is my 100% in c++. I'm using prefixSum. Time complexity O(N * log(log(N)) + M).

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

vector<int> solution(int N, vector<int> &P, vector<int> &Q)
{
    vector<bool> sieve(N, true);
    vector<int> ret;
    sieve[0] = sieve[1] = false;
    int i = 2;

    while (i * i <= N)
    {
        if (sieve[i])
        {
            int k = i * i;
            while (k <= N)
            {
                sieve[k] = false;
                k += i;
            }
        }
        i++;
    }

    vector<int> prefixSum(N + 1, 0);
    
    for (int i = 2; i <= sqrt(N); i++)
        if (sieve[i])
            for (int j = i; j <= N; j++)
            {
                if (j * i > N)
                    break;

                if (sieve[j])
                    prefixSum[j * i]++;
            }

    int carry;
    for (unsigned int i = 5; i < prefixSum.size(); i++)
    {
        carry = prefixSum[i - 1];
        prefixSum[i] += carry;
    }

    for (unsigned int i = 0; i < P.size(); i++)
        ret.push_back(prefixSum[Q[i]] - prefixSum[P[i] - 1]);

    return ret;
}

A 100% solution broken down. https://app.codility.com/demo/results/trainingGVNHKU-MA5/

Firstly use the sieve of Eratosthenes to workout what is prime.

def get_sieve(n):
    # Use the sieve or Eratosthenes to produce an array of primes 
    # where factor[n] == 0 indicates a prime number
    factors = [0] * (n+1)
    i=2
    i2 = i*i
    while (i2 <= n):
        if not factors[i]:
            k = i2
            while k <= n:
                if not factors[k]:
                    factors[k] = i
                k += i
        i += 1
        i2 = i*i
    return factors

Next, determine if the number is semi prime. If both its factors are prime its semiprime.

def is_semi_prime(n, factors):
    if factors[n]: # Check its not a prime
        for r in range(int(n**.5)+1, 1, -1):
            if not n%r:
                d = n//r
                return (not factors[d]) and (not factors[r])
    return False

Then scan the range up to N numbers to count slope of increasing semi primes. simply measure the slope within a slice to see how many semi primes occur during that slice.

def solution(N, P, Q):
    # produce a slope of increasing semi primes
    factors = get_sieve(N)
    slope = [0] * (N+1)
    for i in range(1, N+1):
        slope[i] = slope[i-1] + is_semi_prime(i, factors) # Auto casting!! :-)
    # Optimus Prime!
    # print(list(enumerate(slope)))
    return [slope[Q[j]] - slope[P[j]-1] for j in range(len(P))]

https://github.com/niall-oc/things/blob/master/codility/count_semiprimes.py and more at https://github.com/niall-oc/things/blob/master/codility/

I took a slightly different approach. The other efficient solutions in this thread builds a regular Sieve of Eratosthenes (F) with a twist of recording the smallest prime factor in the slot, so semiprimes are those x for which F[x] > 0 and F[x // F[x]] == 0, i.e. dividing by the smallest prime factor yields another prime number.

My approach is a little slower but does not use division, and builds an interesting intermediate: a sieve that computes exactly how many factors make up the prime factorization of the number (and zeros at the primes). For each prime p, I would increment the sieve at position 2p, 3p, 4p,... but also count a factor for p^2, 2p^2, 3p^2..., p^3, 2p^3, 3p^3, 4p^3,... and so forth. The slot for 16 stores the value 4 (prime factorization: 2*2*2*2), because the slot gets hit by visits from 2, 2^2, 2^3 and 2^4.

Then the semiprimes are those positions having exactly 2 prime factors.

After that I build a prefix count of semiprimes with which to answer the queries in constant time.

def solution(N, P, Q):
    num_factors = [0] * (N+1)
    for i in range(2, N+1):
        if num_factors[i] == 0:
            # Count visits to multiples of i by adding i each time
            add_visit = i+i
            while add_visit < N+1:
                num_factors[add_visit] += 1
                add_visit += i
            # But squares of prime count as 2 factors, cubes count as 3 etc,
            # so also run visits for multiples of the squares, cubes, etc. 
            power_prime = i*i
            while power_prime < N+1:
                visit = power_prime
                while visit < N+1:
                    num_factors[visit] += 1
                    visit += power_prime
                power_prime *= i
    semiprime_prefix_count = [0] * (N+1)
    for i in range(1, N+1):
        semiprime_prefix_count[i] = semiprime_prefix_count[i-1]
        if num_factors[i] == 2:
            semiprime_prefix_count[i] += 1
    results = []
    for p, q in zip(P, Q):
        results.append(semiprime_prefix_count[q] - semiprime_prefix_count[p-1])
    #print(list(zip(range(N+1),num_factors)))
    #print(list(zip(range(N+1),semiprime_prefix_count)))
    return results

Use the usual sieve to get the prime numbers up to N.

Use the prime number to get semi-prime numbers up to N. You can do this by checking any number for two prime factors.

Create prefix sums to store the number of semi-primes up to a particular index.

Finally, get the semi prime counts by subtracting the numbers at the query end and start.

vector<int> solution(int N, vector<int> &P, vector<int> &Q)                     
{                                                                               
  vector<int> sieve(N, 0);                                                      
  for (int prime = 2; prime * prime <= N; ++prime) {                            
    for (int composite = prime * prime; composite <= N; composite += prime) {   
      if (!sieve[composite - 1]) sieve[composite - 1] = prime;                  
    }                                                                           
  }                                                                             
                                                                                
  vector<int> semi_primes;                                                      
  for (int i = 3; i < N; ++i) {                                                 
    const int e = sieve[i];                                                     
    if (e > 0 && !sieve[i / e]) semi_primes.push_back(i + 1);                   
  }                                                                             
  if (semi_primes.empty()) semi_primes.push_back(0);                            
                                                                                
  vector<int> prefix_sums(N + 1, 0);                                            
  for (int i = 1, spi = 0; i <= N; ++i) {                                       
    prefix_sums[i] = ((semi_primes[spi] != i) ? spi : ++spi);                   
  }                                                                             
                                                                                
  int M = P.size();                                                             
  vector<int> semi_prime_counts(M, 0);                                          
  for (int i = 0; i < M; ++i) {                                                 
    semi_prime_counts[i] = prefix_sums[Q[i]] - prefix_sums[P[i] - 1];           
  }                                                                             
                                                                                
  return semi_prime_counts;                                                     
} 

function solution(N, P, Q) {
      // write your code in JavaScript (Node.js 8.9.4)
    let pr =[];let fn =[]
    for(var i=2;i<=N;i++){
        if(isPrime(i)){
            pr.push(i)
        }
    }
    let spr = [],mul,br=0
    for(var i=0;i<pr.length;i++){
        for(var j=0; j <pr.length;j++){
            mul = pr[i] * pr[j];
            if(mul <= N) {
                spr.push(mul)
            }else{
                br =1;
                break;
            }
        }
        // if(br==1) break;
    }
    let nm = [];
    //let o =0
    for(var i=0;i<=N;i++){
       if(spr.indexOf(i) >=0){
        //    ++o
           nm.push(1)
       }else{
            nm.push(0)
       }

    }

    // spr = Array.from(new Set(spr))
    // spr.sort((a,b)=> a- b)
    let a,b,c
    for(var i =0;i<P.length;i++){
        // a= findme(P[i],spr)
        // b= findme(Q[i],spr)
        // a= nm[P[i]]
        // b= nm[Q[i]]
        c= nm.slice(P[i],Q[i]+1).reduce((a,b)=> a+b)
        // c=c <=0 ? 0 : c+1
        // fn.push(b - a + 1)
        fn.push(c)
    }
    return fn
}

function findme(a,arr){
    for(var i= 0; i< arr.length;i++){
        if(a <= arr[i]) return i;
    }
}

function isPrime(num){
    if (num ===2) return true
    for(var i = 2; i < num; i++)
    if(num % i === 0) return false;
    return num > 1;
}

/**
     * https://app.codility.com/demo/results/trainingPBRVXK-28Q/
     * time complexity: O(N * log(log N) + M
     * space complexity: O(2N + N)
     */
public class CountSemiPrime {

    /**
     * 2D array for sieving numbers 1..N
     * 1 - prime, 2 - semiprime, 3 - composite
     */
    public int[][] sieve(int N) {
        int[][] sieve = new int[N+1][1];
        for (int i=1; i<=N; i++) {
            sieve[i][0] = 1; // make prime default
        }
        for (int i=2; i<= N; i++) {
            if (sieve[i][0] == 1) { // if this num is prime, tag its multiples as semi-prime
                int next_number = i + i;
                while (next_number <= N) {
                    sieve[next_number][0] = 2;
                    next_number += i;
                }
            }
            // if this num is semi-prime, tag its multiples as composite
            else if (sieve[i][0] == 2) {
                int next_number = i + i;
                while (next_number <= N) {
                    sieve[next_number][0] = 3;
                    next_number += i;
                }
            }
        }
        return sieve;
    }

    public int[] solution(int N, int[] P, int[] Q) {
        // first, we need to establish prime and semi-prime numbers from 1 to N, in a sieve
        int[][] sieve = sieve(N);
        int[] prefix_sum_of_sieve = new int[sieve.length];

        for (int i=1; i<sieve.length; i++) {
            if (sieve[i][0]==2) {
                prefix_sum_of_sieve[i] = prefix_sum_of_sieve[i-1] + 1;
            }
            else {
                prefix_sum_of_sieve[i] = prefix_sum_of_sieve[i-1];
            }
        }

        int[] results = new int[P.length];
        // we count the semiprime of N from P and Q, for each P & Q from the prefix sum
        for (int i=0; i < P.length; i++) {
            results[i] = prefix_sum_of_sieve[Q[i]] - prefix_sum_of_sieve[P[i]-1];
        }

        return results;
    }
}

Hope the explanation / comments are easy to understand.