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.
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] = 20The number of semiprimes within each of these ranges is as follows:
- (1, 26) is 10,
- (4, 10) is 4,
- (16, 20) is 0.
Write a function:
class Solution { public int[] solution(int N, int[] P, 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.
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] = 20the function should return the values [10, 4, 0], as explained above.
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 and Q is an integer within the range [1..N];
- P[i] ≤ Q[i].
using System;
// you can also use other imports, for example:
using System.Collections.Generic;
using System.Linq;
// you can write to stdout for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");
class Solution {
public int[] solution(int n, int[] p, int[] q) {
n = q.Max();
bool[] isSemi = GetSemiprimes(n);
var semiSoFar = new int[n+1]; //prefix sum - number of semiprime number so far incl curr el
for (int i=4; i<=n; i++)
semiSoFar[i] = semiSoFar[i-1] + (isSemi[i] ? 1 : 0);
var semiCount = new int[p.Length];
for (int i=0; i<p.Length; i++)
{
semiCount[i] = semiSoFar[q[i]] - semiSoFar[p[i]-1];
}
return semiCount;
}
private bool[] GetSemiprimes(int n)
{
var isComposite = new bool[n+1];
for(int i=2; i<=n; i++) //0 - ignore; 1,2 -prime
{
if (!isComposite[i]) //i is a prime number
{
for(int k=i*i; k<=n; k += i) //start from prime*prime (optimization), add prime (*)
isComposite[k] = true;
}
}
var isSemiprime = new bool[n+1];
//check each composite number and detect semiprime numbers
for(int i=2; i<=n; i++)
{
if (!isComposite[i]) //i is a prime number
{
for(int k=i*i; k<=n; k += i) //k is a composite number
if (!isComposite[k/i])
isSemiprime[k] = true;
}
}
return isSemiprime;
}
}
using System;
//using System.Collections.Generic;
using System.Linq;
class Solution {
public int[] solution(int n, int[] p, int[] q) {
n = q.Max();
bool[] isSemi = GetSemiprimes(n);
var semiSoFar = new int[n+1]; //prefix sum - number of semiprime number so far incl curr el
for (int i=4; i<=n; i++)
semiSoFar[i] = semiSoFar[i-1] + (isSemi[i] ? 1 : 0);
var semiCount = new int[p.Length];
for (int i=0; i<p.Length; i++)
{
semiCount[i] = semiSoFar[q[i]] - semiSoFar[p[i]-1];
}
return semiCount;
}
private bool[] GetSemiprimes(int n)
{
var isComposite = new bool[n+1];
for(int i=2; i<=n; i++) //0 - ignore; 1,2 -prime
{
if (!isComposite[i]) //i is a prime number
{
for(int k=i*i; k<=n; k += i) //start from prime*prime (optimization), add prime (*)
isComposite[k] = true;
}
}
var isSemiprime = new bool[n+1];
//check each composite number and detect semiprime numbers
for(int i=2; i<=n; i++)
{
if (!isComposite[i]) //i is a prime number
{
for(int k=i*i; k<=n; k += i) //k is a composite number
if (!isComposite[k/i])
isSemiprime[k] = true;
}
}
return isSemiprime;
}
}
using System;
using System.Linq;
class Solution {
public int[] solution(int n, int[] p, int[] q) {
n = q.Max();
bool[] isSemi = GetSemiprimes(n);
var semiSoFar = new int[n+1]; //prefix sum - number of semiprime number so far incl curr el
for (int i=4; i<=n; i++)
semiSoFar[i] = semiSoFar[i-1] + (isSemi[i] ? 1 : 0);
var semiCount = new int[p.Length];
for (int i=0; i<p.Length; i++)
{
semiCount[i] = semiSoFar[q[i]] - semiSoFar[p[i]-1];
}
return semiCount;
}
private bool[] GetSemiprimes(int n)
{
var isComposite = new bool[n+1];
for(int i=2; i<=n; i++) //0 - ignore; 1,2 -prime
{
if (!isComposite[i]) //i is a prime number
{
for(int k=i*i; k<=n; k += i) //start from prime*prime (optimization), add prime (*)
isComposite[k] = true;
}
}
var isSemiprime = new bool[n+1];
//check each composite number and detect semiprime numbers
for(int i=2; i<=n; i++)
{
if (!isComposite[i]) //i is a prime number
{
for(int k=i*i; k<=n; k += i) //k is a composite number
if (!isComposite[k/i])
isSemiprime[k] = true;
}
}
return isSemiprime;
}
}
using System;
using System.Linq;
class Solution {
public int[] solution(int n, int[] p, int[] q) {
n = q.Max();
bool[] isSemi = GetSemiprimes(n);
var semiSoFar = new int[n+1]; //prefix sum - number of semiprime number so far including current element
for (int i=4; i<=n; i++)
semiSoFar[i] = semiSoFar[i-1] + (isSemi[i] ? 1 : 0);
var semiCount = new int[p.Length];
for (int i=0; i<p.Length; i++)
{
semiCount[i] = semiSoFar[q[i]] - semiSoFar[p[i]-1];
}
return semiCount;
}
private bool[] GetSemiprimes(int n)
{
var isComposite = new bool[n+1];
for(int i=2; i<=n; i++) //0 - ignore; 1,2 -prime
{
if (!isComposite[i]) //i is a prime number
{
for(int k=i*i; k<=n; k += i) //start from prime*prime (optimization), add prime (*)
isComposite[k] = true;
}
}
var isSemiprime = new bool[n+1];
//check each composite number and detect semiprime numbers
for(int i=2; i<=n; i++)
{
if (!isComposite[i]) //i is a prime number
{
for(int k=i*i; k<=n; k += i) //k is a composite number
if (!isComposite[k/i])
isSemiprime[k] = true;
}
}
return isSemiprime;
}
}
using System;
using System.Linq;
class Solution {
public int[] solution(int n, int[] p, int[] q) {
n = q.Max();
bool[] isSemi = GetSemiprimes(n);
var semiSoFar = new int[n+1]; //prefix sum - number of semiprime numbers so far including current element
for (int i=4; i<=n; i++) //4 is a first semiprime number
semiSoFar[i] = semiSoFar[i-1] + (isSemi[i] ? 1 : 0);
var semiCount = new int[p.Length];
for (int i=0; i<p.Length; i++)
semiCount[i] = semiSoFar[q[i]] - semiSoFar[p[i]-1];
return semiCount;
}
private bool[] GetSemiprimes(int n)
{
var isComposite = new bool[n+1]; //false - prime; true - composite
for(int i=2; i<=n; i++) //0 - ignore; 1,2 -prime
{
if (!isComposite[i]) //i is a prime number
{
for(int k=i*i; k<=n; k += i) //start from prime*prime (optimization), add prime (*2,3,4,..)
isComposite[k] = true;
}
}
var isSemiprime = new bool[n+1];
//check each composite number and detect semiprime numbers (=prime1*prime2)
for(int i=2; i<=n; i++)
{
if (!isComposite[i]) //i is a prime number
{
for(int k=i*i; k<=n; k += i) //k is a composite number
if (!isComposite[k/i]) //simmetric multiplier is a prime number
isSemiprime[k] = true;
}
}
return isSemiprime;
}
}
using System;
using System.Linq;
class Solution {
public int[] solution(int n, int[] p, int[] q) {
n = q.Max();
bool[] isSemi = GetSemiprimes(n);
var semiSoFar = new int[n+1]; //prefix sum - number of semiprime numbers so far including current element
for (int i=4; i<=n; i++) //4 is a first semiprime number
semiSoFar[i] = semiSoFar[i-1] + (isSemi[i] ? 1 : 0);
var semiCount = new int[p.Length];
for (int i=0; i<p.Length; i++)
semiCount[i] = semiSoFar[q[i]] - semiSoFar[p[i]-1];
return semiCount;
}
private bool[] GetSemiprimes(int n)
{
var isComposite = new bool[n+1]; //false - prime; true - composite
for(int i=2; i<=n; i++) //0 - ignore; 1,2 -prime
{
if (!isComposite[i]) //i is a prime number
{
for(int k=i*i; k<=n; k += i) //start from prime*prime (optimization), add prime (*2,3,4,..)
isComposite[k] = true;
}
}
var isSemiprime = new bool[n+1];
//check each composite number and detect semiprime numbers (=prime1*prime2)
for(int i=2; i<=n; i++)
{
if (!isComposite[i]) //i is a prime number
{
for(int k=i*i; k<=n; k += i) //k is a composite number
if (!isComposite[k/i]) //simmetric multiplier is also a prime number
isSemiprime[k] = true;
}
}
return isSemiprime;
}
}
using System;
using System.Linq;
class Solution {
public int[] solution(int n, int[] p, int[] q) {
n = q.Max();
bool[] isSemi = GetSemiprimes(n);
var semiSoFar = new int[n+1]; //prefix sum - number of semiprime numbers so far including current element
for (int i=4; i<=n; i++) //4 is a first semiprime number
semiSoFar[i] = semiSoFar[i-1] + (isSemi[i] ? 1 : 0);
var semiCount = new int[p.Length];
for (int i=0; i<p.Length; i++)
semiCount[i] = semiSoFar[q[i]] - semiSoFar[p[i]-1];
return semiCount;
}
private bool[] GetSemiprimes(int n)
{
var isComposite = new bool[n+1]; //false - prime; true - composite
for(int i=2; i<=n; i++) //0 - ignore; 1,2 -prime
{
if (!isComposite[i]) //i is a prime number
{
for(int k=i*i; k<=n; k += i) //start from prime*prime (optimization), add prime (*2,3,4,..)
isComposite[k] = true;
}
}
var isSemiprime = new bool[n+1];
//check each composite number and detect semiprime numbers (=prime1*prime2)
for(int i=2; i<=n; i++)
{
if (!isComposite[i]) //i is a prime number
{
for(int k=i*i; k<=n; k += i) //k is a composite number
if (!isComposite[k/i]) //simmetric multiplier is also a prime number
isSemiprime[k] = true;
}
}
return isSemiprime;
}
}
using System;
using System.Linq;
class Solution {
public int[] solution(int n, int[] p, int[] q) {
n = q.Max();
bool[] isSemi = GetSemiprimes(n);
var semiSoFar = new int[n+1]; //prefix sum - number of semiprime numbers so far including current element
for (int i=4; i<=n; i++) //4 is a first semiprime number
semiSoFar[i] = semiSoFar[i-1] + (isSemi[i] ? 1 : 0);
var semiCount = new int[p.Length];
for (int i=0; i<p.Length; i++)
semiCount[i] = semiSoFar[q[i]] - semiSoFar[p[i]-1];
return semiCount;
}
private bool[] GetSemiprimes(int n)
{
var isComposite = new bool[n+1]; //false - prime; true - composite
for(int i=2; i<=n; i++) //0 - ignore; 1,2 -prime
{
if (!isComposite[i]) //i is a prime number
{
for(int k=i*i; k<=n; k += i) //start from prime*prime (optimization), add prime (*2,3,4,..)
isComposite[k] = true;
}
}
var isSemiprime = new bool[n+1];
//check each composite number and detect semiprime numbers (=prime1*prime2)
for(int i=2; i<=n; i++)
{
if (!isComposite[i]) //i is a prime number
{
for(int k=i*i; k<=n; k += i) //k is a composite number
if (!isComposite[k/i]) //simmetric multiplier is also a prime number
isSemiprime[k] = true;
}
}
return isSemiprime;
}
}
The following issues have been detected: runtime errors.
large random, length = ~30,000
tested program terminated unexpectedly
Unhandled Exception: System.IndexOutOfRangeException: Array index is out of range. at Solution.GetSemiprimes (Int32 n) [0x00000] in <filename unknown>:0 at Solution.solution (Int32 n, System.Int32[] p, System.Int32[] q) [0x00000] in <filename unknown>:0 at SolutionWrapper.run (System.String input, System.String output) [0x00000] in <filename unknown>:0 at SolutionWrapper.Main (System.String[] args) [0x00000] in <filename unknown>:0 [ERROR] FATAL UNHANDLED EXCEPTION: System.IndexOutOfRangeException: Array index is out of range. at Solution.GetSemiprimes (Int32 n) [0x00000] in <filename unknown>:0 at Solution.solution (Int32 n, System.Int32[] p, System.Int32[] q) [0x00000] in <filename unknown>:0 at SolutionWrapper.run (System.String input, System.String output) [0x00000] in <filename unknown>:0 at SolutionWrapper.Main (System.String[] args) [0x00000] in <filename unknown>:0
large random, length = ~30,000
tested program terminated unexpectedly
Unhandled Exception: System.IndexOutOfRangeException: Array index is out of range. at Solution.GetSemiprimes (Int32 n) [0x00000] in <filename unknown>:0 at Solution.solution (Int32 n, System.Int32[] p, System.Int32[] q) [0x00000] in <filename unknown>:0 at SolutionWrapper.run (System.String input, System.String output) [0x00000] in <filename unknown>:0 at SolutionWrapper.Main (System.String[] args) [0x00000] in <filename unknown>:0 [ERROR] FATAL UNHANDLED EXCEPTION: System.IndexOutOfRangeException: Array index is out of range. at Solution.GetSemiprimes (Int32 n) [0x00000] in <filename unknown>:0 at Solution.solution (Int32 n, System.Int32[] p, System.Int32[] q) [0x00000] in <filename unknown>:0 at SolutionWrapper.run (System.String input, System.String output) [0x00000] in <filename unknown>:0 at SolutionWrapper.Main (System.String[] args) [0x00000] in <filename unknown>:0
Unhandled Exception: System.IndexOutOfRangeException: Array index is out of range. at Solution.GetSemiprimes (Int32 n) [0x00000] in <filename unknown>:0 at Solution.solution (Int32 n, System.Int32[] p, System.Int32[] q) [0x00000] in <filename unknown>:0 at SolutionWrapper.run (System.String input, System.String output) [0x00000] in <filename unknown>:0 at SolutionWrapper.Main (System.String[] args) [0x00000] in <filename unknown>:0 [ERROR] FATAL UNHANDLED EXCEPTION: System.IndexOutOfRangeException: Array index is out of range. at Solution.GetSemiprimes (Int32 n) [0x00000] in <filename unknown>:0 at Solution.solution (Int32 n, System.Int32[] p, System.Int32[] q) [0x00000] in <filename unknown>:0 at SolutionWrapper.run (System.String input, System.String output) [0x00000] in <filename unknown>:0 at SolutionWrapper.Main (System.String[] args) [0x00000] in <filename unknown>:0