Task
A prime is a positive integer X that has exactly two distinct divisors: 1 and X. The first few prime integers are 2, 3, 5, 7, 11 and 13.
A semiprime is a natural number that is the product of two (not necessarily distinct) prime numbers. The first few semiprimes are 4, 6, 9, 10, 14, 15, 21, 22, 25, 26.
You are given two non-empty arrays P and Q, each consisting of M integers. These arrays represent queries about the number of semiprimes within specified ranges.
Query K requires you to find the number of semiprimes within the range (P[K], Q[K]), where 1 ≤ P[K] ≤ Q[K] ≤ N.
…
Write a function:
vector<int> solution(int N, vector<int> &P, vector<int> &Q);that, given an integer N and two non-empty arrays P and Q consisting of M integers, returns an array consisting of M elements specifying the consecutive answers to all the queries.
…
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..50,000];
- M is an integer within the range [1..30,000];
- each element of arrays P, Q is an integer within the range [1..N];
- P[i] ≤ Q[i].
Solution
- We only need to search for factors up to the square root of N, as the smallest factor will be less than or equal to this.
- When updating the sieve with a new potential factor, we can start from the square of that factor as smaller multiples will be found already
#include <cassert>
#include <math.h>
#include <vector>
vector<int> solution(int N, vector<int> &P, vector<int> &Q) {
vector<int> result(P.size());
// array of smallest factor of numbers
int factors[N + 1];
for (int fact = 0; fact <= N; fact++) {
factors[fact] = 0;
}
// only need to go up to sq root as smallest factor will be <= sq root of number
int largest = ceil(sqrt(N));
for (int fact = 2; fact <= largest; fact++) {
// unfound factors only
if (factors[fact] == 0) {
// can start from sq of factor as smallest factors of values less than that will already be found
int mult = fact * fact;
while (mult <= N) {
if (factors[mult] == 0) {
// found smallest factor
factors[mult] = fact;
}
mult += fact;
}
}
} // for
// partSums = partial sum of number of semiprimes
int partSums[N + 1];
partSums[0] = partSums[1] = 0;
int countSemi = 0; // count of number of semiprimes found so far
for (int fact = 2; fact <= N; fact++) {
int nextFact = factors[fact];
if (nextFact != 0) {
// not prime
if (factors[nextFact] == 0) {
// smallest factor is prime, what about other
nextFact = fact / nextFact;
if (factors[nextFact] == 0) {
countSemi++;
}
}
}
partSums[fact] = countSemi;
}
// now do result
for (ulong expr = 0; expr < P.size(); expr++) {
result[expr] = partSums[Q[expr]] – partSums[P[expr] – 1];
}
return result;
}Notes
- The check at line 21 is not needed because you don’t have to store the smallest factor, any factor will do
- The check at line 37 is redundant because all the factors stored are prime
Test Function
This code tests the solution
void check(int N, vector<int> P, vector<int> Q, const vector<int> expected) {
vector<int> res = solution(N, P, Q);
assert(expected.size() == res.size());
for (ulong i = 0; i < res.size(); i++) {
assert(expected[i] == res[i]);
}
}
int main() {
check(26, {1, 4, 16}, {26, 10, 20}, {10, 4, 0});
check(1, {1}, {1}, {0});
check(4, {1, 2, 3, 4, 1, 2, 3, 1, 2, 1}, {4, 4, 4, 4, 3, 3, 3, 2, 2, 1}, {1, 1, 1, 1, 0, 0, 0, 0, 0, 0});
check(50, {1, 2, 3, 4, 10}, {50, 49, 48, 40, 30}, {17, 17, 16, 15, 7});
}Results
Codility Results
| Correctness | 100% |
| Performance | 100% |
| Time Complexity | O(N * log(log(N)) + M) |