Codility and other programming lessons: Lesson 9: CountSemiprimes - (Count Semiprimes)
Lesson 9: CountSemiprimes
https://codility.com/programmers/lessons/9
We use Sieve of Eratosthenes to find prime numbers less than and equal to N.
Then we check each k (P[i] <= k <= Q[i]) is a semiprime or not
by using these prime numbers one by one.
https://github.com/styro103/CountSemiprimes/blob/master/CountSemiPrimes.java
https://www.martinkysel.com/codility-countsemiprimes-solution/
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.
Static Range query: use prefix sum.
Java solution: https://github.com/acprimer/Codility/blob/master/src/Lesson9/CountSemiprimes.java
int check(int k, int N, char* sieve, int* next_prime)
{
//if k is less than 4 or a prime number,
//it is never a semiprime
if (k < 4 || sieve[k] == 1){
return 0;
}
//check if k is a semiprime.
int num = 2;
while (num * num <= k){
num = next_prime[num];
if (k > num && k % num == 0 && k / num <= N && sieve[k / num] == 1){
return 1;
}
num++;
}
return 0;
}
struct Results solution(int N, int P[], int Q[], int M)
{
//compute the prime number
int size = sizeof(char) * (N + 1);
char* sieve = (char*)alloca(size);
memset(sieve, 0x01, size);
int i, j, k;
i = 2;
sieve[0] = sieve[1] = 0;
while(i * i <= N){
if (sieve[i]){
k = i * i;
while(k <= N){
sieve[k] = 0;
k += i;
}
}
i++;
}
//the next prime number
int* next_prime = (int*)alloca(sizeof(int) * (N + 1));
next_prime[N] = sieve[N] == 1 ? N : -1;
for (i = N - 1; i >= 0; i--){
if (sieve[i]){
next_prime[i] = i;
}
else {
next_prime[i] = next_prime[i + 1];
}
}
struct Results result;
result.A = (int*)malloc(sizeof(int) * M);
result.M = M;
//start finding semiprime for each.
for (i = 0; i < M; i++){
int cnt = 0;
for (j = P[i]; j <= Q[i]; j++){
if (check(j, N, sieve, next_prime)){
cnt++;
}
}
result.A[i] = cnt;
}
return result;
}
https://github.com/acprimer/Codility/blob/master/src/Lesson9/CountSemiprimes.java
Let's use the sieve algorithm also to find semiprime numbers. Then use the prefix sum of the occurrence of semiprime numbers from 0 to N, so that we can count the number of semiprime numbers in a constant time.
This strategy gives the O(N*log(log(N))+M) time complexity. As the sieve algorithm is used both for finding prime numbers and subprime numbers, These parts have the O(2* N*log(log(N))) => O(N*log(log(N))) time complexity.
The part to make an array of prefix sum is the O(N) time complexity. Then so far, it is still O(N*log(log(N)) + N) => O(N*log(log(N)).
To compute the return value, as the number of semiprime between P[i] and Q[i] can be found in a constant time and we repeat it M times, the time complexity will be O(M).
Adding this to O(N*log(log(N)), the O(N*log(log(N) + M) time complexity is what we have in this solution.
http://codility-lessons.blogspot.com/2015/03/lesson-9-countsemiprimes.html
Read full article from Codility and other programming lessons: Lesson 9: CountSemiprimes - (Count Semiprimes)
Lesson 9: CountSemiprimes
https://codility.com/programmers/lessons/9
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 zero-indexed 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.
For example, consider an integer N = 26 and arrays P, Q such that:
P[0] = 1 Q[0] = 26
P[1] = 4 Q[1] = 10
P[2] = 16 Q[2] = 20
The number of semiprimes within each of these ranges is as follows:
- (1, 26) is 10,
- (4, 10) is 4,
- (16, 20) is 0.
Assume that the following declarations are given:
struct Results {
int * A;
int M;
};
Write a function:
struct Results solution(int N, int P[], int Q[], int M);
that, given an integer N and two non-empty zero-indexed arrays P and Q consisting of M integers, returns an array consisting of M elements specifying the consecutive answers to all the queries.
For example, given an integer N = 26 and arrays P, Q such that:
P[0] = 1 Q[0] = 26
P[1] = 4 Q[1] = 10
P[2] = 16 Q[2] = 20
the function should return the values [10, 4, 0], as explained above.
First, let's implement a simple solution. We use Sieve of Eratosthenes to find prime numbers less than and equal to N.
Then we check each k (P[i] <= k <= Q[i]) is a semiprime or not
by using these prime numbers one by one.
https://github.com/styro103/CountSemiprimes/blob/master/CountSemiPrimes.java
public int [] solution(int N, int [] P, int [] Q)
{
if (N<4) return new int [P.length]; //If Max Number is Less Than 4, Return Array of Zeroes (4 is First Semiprime)
int M = P.length; //Number of Queries
int [] semiRanges = new int [M]; //Array of Semiprime Counts Between Ranges
int [] semisCount = getSemis(N); //Get Count of Semiprimes of Each Number Up to Max
for (int k=0; k<M; k++) //Loop Through Queries
semiRanges[k] = (Q[k]<4) ? 0 : semisCount[Q[k]] - semisCount[P[k]-1]; //Subtract Counts to Get Semiprimes Count Between Range
return semiRanges; //Return Array of Semiprimes Between Ranges
}
int [] getSemis(int N)
{
int [] sieve = sifter(N); //Get Array of Minimum Prime Factors
int [] rsc = new int [N+1]; //Array of Counts of Semiprimes
int sc = 0; //Semiprimes Count
//Arrays.fill(rsc, 0); //Automatic Initialization to 0 in Java
for (int i=4; i<rsc.length; i++) //Loop From 4 To One More Than Max Number
{
if (sieve[i]!=0 && sieve[i/sieve[i]]==0) sc++; //If Semiprime, Increase Count
rsc[i] = sc; //Set Count of Semiprimes at Integer
}
return rsc; //Return Array of Counts of Semiprimes
}
int [] sifter (int N) //Get Array of Minimum Prime Factors
{
int [] sieve = new int [N+1]; //Array of Minimum Prime Factors
//Arrays.fill(sieve, 0); //Automatic Initialization to 0 in Java
for (int i=2; i<=Math.sqrt(N); i++) //Loop From 2 till Max Number
{
if (sieve[i]==0) //If Prime Number
{
for (int j=i*i; j<=N; j+=i) //Find All Multiples
if (sieve[j]==0) sieve[j] = i; //If Prime Factor Isn't Listed, Update
}
}
return sieve; //Return Array of Minimum Prime Factors
}
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.
Static Range query: use prefix sum.
Java solution: https://github.com/acprimer/Codility/blob/master/src/Lesson9/CountSemiprimes.java
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): semi.add(j) i += 1 return semidef 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 solutionint check(int k, int N, char* sieve, int* next_prime)
{
//if k is less than 4 or a prime number,
//it is never a semiprime
if (k < 4 || sieve[k] == 1){
return 0;
}
//check if k is a semiprime.
int num = 2;
while (num * num <= k){
num = next_prime[num];
if (k > num && k % num == 0 && k / num <= N && sieve[k / num] == 1){
return 1;
}
num++;
}
return 0;
}
struct Results solution(int N, int P[], int Q[], int M)
{
//compute the prime number
int size = sizeof(char) * (N + 1);
char* sieve = (char*)alloca(size);
memset(sieve, 0x01, size);
int i, j, k;
i = 2;
sieve[0] = sieve[1] = 0;
while(i * i <= N){
if (sieve[i]){
k = i * i;
while(k <= N){
sieve[k] = 0;
k += i;
}
}
i++;
}
//the next prime number
int* next_prime = (int*)alloca(sizeof(int) * (N + 1));
next_prime[N] = sieve[N] == 1 ? N : -1;
for (i = N - 1; i >= 0; i--){
if (sieve[i]){
next_prime[i] = i;
}
else {
next_prime[i] = next_prime[i + 1];
}
}
struct Results result;
result.A = (int*)malloc(sizeof(int) * M);
result.M = M;
//start finding semiprime for each.
for (i = 0; i < M; i++){
int cnt = 0;
for (j = P[i]; j <= Q[i]; j++){
if (check(j, N, sieve, next_prime)){
cnt++;
}
}
result.A[i] = cnt;
}
return result;
}
https://github.com/acprimer/Codility/blob/master/src/Lesson9/CountSemiprimes.java
| boolean[] notPrime, semi; | |
| public void seivee(int n) { | |
| for (int i = 2; i * i <= n; i++) { | |
| if (notPrime[i]) continue; | |
| for (int k = i * i; k <= n; k += i) { | |
| notPrime[k] = true; | |
| } | |
| } | |
| } | |
| public void semi(int n) { | |
| for (int i = 2; i * i <= n; i++) { | |
| if (notPrime[i]) continue; | |
| for (int k = i * i; k <= n; k += i) { | |
| if (!notPrime[k / i]) semi[k] = true; | |
| } | |
| } | |
| } | |
| public int[] solution(int N, int[] P, int[] Q) { | |
| notPrime = new boolean[N + 1]; | |
| seivee(N); | |
| semi = new boolean[N + 1]; | |
| semi(N); | |
| int[] sum = new int[N + 1]; | |
| for (int i = 1; i <= N; i++) { | |
| sum[i] = sum[i - 1]; | |
| if (semi[i]) sum[i]++; | |
| } | |
| for (int i = 0; i < P.length; i++) { | |
| P[i] = sum[Q[i]] - sum[P[i] - 1]; | |
| } | |
| return P; | |
| } |
This strategy gives the O(N*log(log(N))+M) time complexity. As the sieve algorithm is used both for finding prime numbers and subprime numbers, These parts have the O(2* N*log(log(N))) => O(N*log(log(N))) time complexity.
The part to make an array of prefix sum is the O(N) time complexity. Then so far, it is still O(N*log(log(N)) + N) => O(N*log(log(N)).
To compute the return value, as the number of semiprime between P[i] and Q[i] can be found in a constant time and we repeat it M times, the time complexity will be O(M).
Adding this to O(N*log(log(N)), the O(N*log(log(N) + M) time complexity is what we have in this solution.
http://codility-lessons.blogspot.com/2015/03/lesson-9-countsemiprimes.html
Read full article from Codility and other programming lessons: Lesson 9: CountSemiprimes - (Count Semiprimes)
