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].
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int N, int[] P, int[] Q) {
int[] result = new int[P.length];
int[] flags = new int[N + 1];
flags[0] = 1;
return result;
}
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int N, int[] P, int[] Q) {
int[] result = new int[P.length];
int[] flags = new int[N + 1];
flags[0] = 1;
flags[1] = 1;
for (int i = 2; i * i <= N; i++) {
if (flags[i] == 1) {
continue;
}
}
return result;
}
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int N, int[] P, int[] Q) {
int[] result = new int[P.length];
int[] flags = new int[N + 1];
// 1: No prime
flags[0] = 1;
flags[1] = 1;
for (int i = 2; i * i <= N; i++) {
if (flags[i] == 1) {
continue;
}
}
return result;
}
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int N, int[] P, int[] Q) {
int[] result = new int[P.length];
int[] flags = new int[N + 1];
// 1: No prime, 2: SemiPrime
flags[0] = 1;
flags[1] = 1;
for (int i = 2; i * i <= N; i++) {
if (flags[i] == 1) {
continue;
}
}
return result;
}
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int N, int[] P, int[] Q) {
int[] result = new int[P.length];
int[] flags = new int[N + 1];
// 1: No prime, 2: SemiPrime
flags[0] = 1;
flags[1] = 1;
for (int i = 2; i * i <= N; i++) {
if (flags[i] == 1) {
continue;
}
int k = i * i;
while (k <= N) {
if (flags[i] == 0 && flags[k /ui])
}
}
return result;
}
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int N, int[] P, int[] Q) {
int[] result = new int[P.length];
int[] flags = new int[N + 1];
// 1: No prime, 2: SemiPrime
flags[0] = 1;
flags[1] = 1;
for (int i = 2; i * i <= N; i++) {
if (flags[i] == 1) {
continue;
}
int k = i * i;
while (k <= N) {
if (flags[i] == 0 && flags[k / i] == 0) {
flags[k] = 2;
} else {
flags[k] = 1;
}
k = k + i;
}
}
return result;
}
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int N, int[] P, int[] Q) {
int[] result = new int[P.length];
int[] flags = new int[N + 1];
// 1: No prime, 2: SemiPrime
flags[0] = 1;
flags[1] = 1;
for (int i = 2; i * i <= N; i++) {
if (flags[i] == 1) {
continue;
}
int k = i * i;
while (k <= N) {
if (flags[i] == 0 && flags[k / i] == 0) {
flags[k] = 2;
} else {
flags[k] = 1;
}
k = k + i; // Next multiple numb
}
}
return result;
}
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int N, int[] P, int[] Q) {
int[] result = new int[P.length];
int[] flags = new int[N + 1];
// 1: No prime, 2: SemiPrime
flags[0] = 1;
flags[1] = 1;
for (int i = 2; i * i <= N; i++) {
if (flags[i] == 1) {
continue;
}
int k = i * i;
while (k <= N) {
if (flags[i] == 0 && flags[k / i] == 0) {
flags[k] = 2;
} else {
flags[k] = 1;
}
k = k + i; // Next multiple number.
}
}
return result;
}
private int[] getCheckNumbers(int N) {
}
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int N, int[] P, int[] Q) {
int[] result = new int[P.length];
int[] flags = new int[N + 1];
// 1: No prime, 2: SemiPrime
flags[0] = 1;
flags[1] = 1;
for (int i = 2; i * i <= N; i++) {
if (flags[i] == 1) {
continue;
}
int k = i * i;
while (k <= N) {
if (flags[i] == 0 && flags[k / i] == 0) {
flags[k] = 2;
} else {
flags[k] = 1;
}
k = k + i; // Next multiple number.
}
}
return result;
}
private int[] getCheckNumbers(int N) {
int[] flags = new int[N + 1];
// 1: No prime, 2: SemiPrime
flags[0] = 1;
flags[1] = 1;
for (int i = 2; i * i <= N; i++) {
if (flags[i] == 1) {
continue;
}
int k = i * i;
while (k <= N) {
if (flags[i] == 0 && flags[k / i] == 0) {
flags[k] = 2;
} else {
flags[k] = 1;
}
k = k + i; // Next multiple number.
}
}
}
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int N, int[] P, int[] Q) {
int[] result = new int[P.length];
int[] flags = getCheckNumbers(N);
}
return result;
}
private int[] getCheckNumbers(int N) {
int[] flags = new int[N + 1];
// 1: No prime, 2: SemiPrime
flags[0] = 1;
flags[1] = 1;
for (int i = 2; i * i <= N; i++) {
if (flags[i] == 1) {
continue;
}
int k = i * i;
while (k <= N) {
if (flags[i] == 0 && flags[k / i] == 0) {
flags[k] = 2;
} else {
flags[k] = 1;
}
k = k + i; // Next multiple number.
}
}
}
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int N, int[] P, int[] Q) {
int[] result = new int[P.length];
int[] flags = getCheckNumbers(N);
}
return result;
}
private int[] getCheckNumbers(int N) {
int[] flags = new int[N + 1];
// 1: No prime, 2: SemiPrime
flags[0] = 1;
flags[1] = 1;
for (int i = 2; i * i <= N; i++) {
if (flags[i] == 1) {
continue;
}
int k = i * i;
while (k <= N) {
if (flags[i] == 0 && flags[k / i] == 0) {
flags[k] = 2;
} else {
flags[k] = 1;
}
k = k + i; // Next multiple number.
}
}
return flags;
}
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int N, int[] P, int[] Q) {
int[] result = new int[P.length];
int[] flags = getCheckNumbers(N);
}
return result;
}
private int[] getCheckNumbers(int N) {
int[] flags = new int[N + 1];
flags[0] = 1;
flags[1] = 1;
for (int i = 2; i * i <= N; i++) {
if (flags[i] == 1) {
continue;
}
int k = i * i;
while (k <= N) {
if (flags[i] == 0 && flags[k / i] == 0) {
flags[k] = 2;
} else {
flags[k] = 1;
}
k = k + i; // Next multiple number.
}
}
return flags;
}
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int N, int[] P, int[] Q) {
int[] result = new int[P.length];
int[] flags = getCheckNumbers(N);
}
return result;
}
// 1: No prime, 2: SemiPrime
private int[] getCheckNumbers(int N) {
int[] flags = new int[N + 1];
flags[0] = 1;
flags[1] = 1;
for (int i = 2; i * i <= N; i++) {
if (flags[i] == 1) {
continue;
}
int k = i * i;
while (k <= N) {
if (flags[i] == 0 && flags[k / i] == 0) {
flags[k] = 2;
} else {
flags[k] = 1;
}
k = k + i; // Next multiple number.
}
}
return flags;
}
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int N, int[] P, int[] Q) {
int[] result = new int[P.length];
int[] flags = getCheckNumbers(N);
int[] preSum = new int[N + 1];
for (int i = 2; i <= N; i++)
return result;
}
// 1: No prime, 2: SemiPrime
private int[] getCheckNumbers(int N) {
int[] flags = new int[N + 1];
flags[0] = 1;
flags[1] = 1;
for (int i = 2; i * i <= N; i++) {
if (flags[i] == 1) {
continue;
}
int k = i * i;
while (k <= N) {
if (flags[i] == 0 && flags[k / i] == 0) {
flags[k] = 2;
} else {
flags[k] = 1;
}
k = k + i; // Next multiple number.
}
}
return flags;
}
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int N, int[] P, int[] Q) {
int[] result = new int[P.length];
int[] flags = getCheckNumbers(N);
int[] preSum = new int[N + 1];
for (int i = 2; i <= N; i++) {
int semiPrimeCount = 0;
if (flags[i] == 2) {
semiPrimeCount++;
}
preSum[i] = semiPrimeCount;
}
return result;
}
private int[]
// 1: No prime, 2: SemiPrime
private int[] getCheckNumbers(int N) {
int[] flags = new int[N + 1];
flags[0] = 1;
flags[1] = 1;
for (int i = 2; i * i <= N; i++) {
if (flags[i] == 1) {
continue;
}
int k = i * i;
while (k <= N) {
if (flags[i] == 0 && flags[k / i] == 0) {
flags[k] = 2;
} else {
flags[k] = 1;
}
k = k + i; // Next multiple number.
}
}
return flags;
}
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int N, int[] P, int[] Q) {
int[] result = new int[P.length];
int[] flags = getCheckNumbers(N);
int[] preSum = new int[N + 1];
for (int i = 2; i <= N; i++) {
int semiPrimeCount = 0;
if (flags[i] == 2) {
semiPrimeCount++;
}
preSum[i] = semiPrimeCount;
}
return result;
}
private int[] getPreSum(int N) {
}
// 1: No prime, 2: SemiPrime
private int[] getCheckNumbers(int N) {
int[] flags = new int[N + 1];
flags[0] = 1;
flags[1] = 1;
for (int i = 2; i * i <= N; i++) {
if (flags[i] == 1) {
continue;
}
int k = i * i;
while (k <= N) {
if (flags[i] == 0 && flags[k / i] == 0) {
flags[k] = 2;
} else {
flags[k] = 1;
}
k = k + i; // Next multiple number.
}
}
return flags;
}
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int N, int[] P, int[] Q) {
int[] result = new int[P.length];
int[] flags = getCheckNumbers(N);
int[] preSum = new int[N + 1];
for (int i = 2; i <= N; i++) {
int semiPrimeCount = 0;
if (flags[i] == 2) {
semiPrimeCount++;
}
preSum[i] = semiPrimeCount;
}
return result;
}
private int[] getPreSum(int N) {
int[] flags = getCheckNumbers(N);
int[] preSum = new int[N + 1];
for (int i = 2; i <= N; i++) {
int semiPrimeCount = 0;
if (flags[i] == 2) {
semiPrimeCount++;
}
preSum[i] = semiPrimeCount;
}
return preSum;
}
// 1: No prime, 2: SemiPrime
private int[] getCheckNumbers(int N) {
int[] flags = new int[N + 1];
flags[0] = 1;
flags[1] = 1;
for (int i = 2; i * i <= N; i++) {
if (flags[i] == 1) {
continue;
}
int k = i * i;
while (k <= N) {
if (flags[i] == 0 && flags[k / i] == 0) {
flags[k] = 2;
} else {
flags[k] = 1;
}
k = k + i; // Next multiple number.
}
}
return flags;
}
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int N, int[] P, int[] Q) {
int[] result = new int[P.length];
int[] preSum = getPreSum(N);
return result;
}
private int[] getPreSum(int N) {
int[] flags = getCheckNumbers(N);
int[] preSum = new int[N + 1];
for (int i = 2; i <= N; i++) {
int semiPrimeCount = 0;
if (flags[i] == 2) {
semiPrimeCount++;
}
preSum[i] = semiPrimeCount;
}
return preSum;
}
// 1: No prime, 2: SemiPrime
private int[] getCheckNumbers(int N) {
int[] flags = new int[N + 1];
flags[0] = 1;
flags[1] = 1;
for (int i = 2; i * i <= N; i++) {
if (flags[i] == 1) {
continue;
}
int k = i * i;
while (k <= N) {
if (flags[i] == 0 && flags[k / i] == 0) {
flags[k] = 2;
} else {
flags[k] = 1;
}
k = k + i; // Next multiple number.
}
}
return flags;
}
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int N, int[] P, int[] Q) {
int[] result = new int[P.length];
int[] preSum = getPreSum(N);
for (int idx = 0; idx < P.length; idx++) {
result[idx] = preSum[Q[i]]
}
return result;
}
private int[] getPreSum(int N) {
int[] preSum = new int[N + 1];
int[] flags = getCheckNumbers(N);
for (int i = 2; i <= N; i++) {
int semiPrimeCount = 0;
if (flags[i] == 2) {
semiPrimeCount++;
}
preSum[i] = semiPrimeCount;
}
return preSum;
}
// 1: No prime, 2: SemiPrime
private int[] getCheckNumbers(int N) {
int[] flags = new int[N + 1];
flags[0] = 1;
flags[1] = 1;
for (int i = 2; i * i <= N; i++) {
if (flags[i] == 1) {
continue;
}
int k = i * i;
while (k <= N) {
if (flags[i] == 0 && flags[k / i] == 0) {
flags[k] = 2;
} else {
flags[k] = 1;
}
k = k + i; // Next multiple number.
}
}
return flags;
}
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int N, int[] P, int[] Q) {
int[] result = new int[P.length];
int[] preSum = getPreSum(N);
for (int idx = 0; idx < P.length; idx++) {
result[idx] = preSum[Q[idx]] - preSum[P[idx] - 1];
}
return result;
}
private int[] getPreSum(int N) {
int[] preSum = new int[N + 1];
int[] flags = getCheckNumbers(N);
for (int i = 2; i <= N; i++) {
int semiPrimeCount = 0;
if (flags[i] == 2) {
semiPrimeCount++;
}
preSum[i] = semiPrimeCount;
}
return preSum;
}
// 1: No prime, 2: SemiPrime
private int[] getCheckNumbers(int N) {
int[] flags = new int[N + 1];
flags[0] = 1;
flags[1] = 1;
for (int i = 2; i * i <= N; i++) {
if (flags[i] == 1) {
continue;
}
int k = i * i;
while (k <= N) {
if (flags[i] == 0 && flags[k / i] == 0) {
flags[k] = 2;
} else {
flags[k] = 1;
}
k = k + i; // Next multiple number.
}
}
return flags;
}
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int N, int[] P, int[] Q) {
int[] result = new int[P.length];
int[] preSum = getPreSum(N);
for (int idx = 0; idx < P.length; idx++) {
result[idx] = preSum[Q[idx]] - preSum[P[idx] - 1];
}
return result;
}
private int[] getPreSum(int N) {
int[] preSum = new int[N + 1];
int[] flags = getCheckNumbers(N);
for (int i = 2; i <= N; i++) {
int semiPrimeCount = 0;
if (flags[i] == 2) {
semiPrimeCount++;
}
preSum[i] = semiPrimeCount;
}
return preSum;
}
// 1: No prime, 2: SemiPrime
private int[] getCheckNumbers(int N) {
int[] flags = new int[N + 1];
flags[0] = 1;
flags[1] = 1;
for (int idx = 2; idx * idx <= N; idx++) {
if (flags[i] == 1) {
continue;
}
int k = idx * idx;
while (k <= N) {
if (flags[idx] == 0 && flags[k / idx] == 0) {
flags[k] = 2;
} else {
flags[k] = 1;
}
k = k + i; // Next multiple number.
}
}
return flags;
}
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int N, int[] P, int[] Q) {
int[] result = new int[P.length];
int[] preSum = getPreSum(N);
for (int idx = 0; idx < P.length; idx++) {
result[idx] = preSum[Q[idx]] - preSum[P[idx] - 1];
}
return result;
}
private int[] getPreSum(int N) {
int[] preSum = new int[N + 1];
int[] flags = getCheckNumbers(N);
for (int i = 2; i <= N; i++) {
int semiPrimeCount = 0;
if (flags[i] == 2) {
semiPrimeCount++;
}
preSum[i] = semiPrimeCount;
}
return preSum;
}
// 1: No prime, 2: SemiPrime
private int[] getCheckNumbers(int N) {
int[] flags = new int[N + 1];
flags[0] = 1;
flags[1] = 1;
for (int idx = 2; idx * idx <= N; idx++) {
if (flags[i] == 1) {
continue;
}
int multiple = idx * idx;
while (k <= N) {
if (flags[idx] == 0 && flags[k / idx] == 0) {
flags[k] = 2;
} else {
flags[k] = 1;
}
k = k + i; // Next multiple number.
}
}
return flags;
}
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int N, int[] P, int[] Q) {
int[] result = new int[P.length];
int[] preSum = getPreSum(N);
for (int idx = 0; idx < P.length; idx++) {
result[idx] = preSum[Q[idx]] - preSum[P[idx] - 1];
}
return result;
}
private int[] getPreSum(int N) {
int[] preSum = new int[N + 1];
int[] flags = getCheckNumbers(N);
for (int i = 2; i <= N; i++) {
int semiPrimeCount = 0;
if (flags[i] == 2) {
semiPrimeCount++;
}
preSum[i] = semiPrimeCount;
}
return preSum;
}
// 1: No prime, 2: SemiPrime
private int[] getCheckNumbers(int N) {
int[] flags = new int[N + 1];
flags[0] = 1;
flags[1] = 1;
for (int idx = 2; idx * idx <= N; idx++) {
if (flags[i] == 1) {
continue;
}
int multiple = idx * idx;
while (multiple <= N) {
if (flags[idx] == 0 && flags[multiple / idx] == 0) {
flags[multiple] = 2;
} else {
flags[multiple] = 1;
}
multiple = multiple + idx; // Next multiple number.
}
}
return flags;
}
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int N, int[] P, int[] Q) {
int[] result = new int[P.length];
int[] preSum = getPreSum(N);
for (int idx = 0; idx < P.length; idx++) {
result[idx] = preSum[Q[idx]] - preSum[P[idx] - 1];
}
return result;
}
private int[] getPreSum(int N) {
int[] preSum = new int[N + 1];
int[] flags = getCheckNumbers(N);
for (int idx = 2; idx <= N; idx++) {
int semiPrimeCount = 0;
if (flags[idx] == 2) {
semiPrimeCount++;
}
preSum[idx] = semiPrimeCount;
}
return preSum;
}
// 1: No prime, 2: SemiPrime
private int[] getCheckNumbers(int N) {
int[] flags = new int[N + 1];
flags[0] = 1;
flags[1] = 1;
for (int idx = 2; idx * idx <= N; idx++) {
if (flags[i] == 1) {
continue;
}
int multiple = idx * idx;
while (multiple <= N) {
if (flags[idx] == 0 && flags[multiple / idx] == 0) {
flags[multiple] = 2;
} else {
flags[multiple] = 1;
}
multiple = multiple + idx; // Next multiple number.
}
}
return flags;
}
}
Solution.java:36: error: cannot find symbol if (flags[i] == 1) { ^ symbol: variable i location: class Solution 1 error
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int N, int[] P, int[] Q) {
int[] result = new int[P.length];
int[] preSum = getPreSum(N);
for (int idx = 0; idx < P.length; idx++) {
result[idx] = preSum[Q[idx]] - preSum[P[idx] - 1];
}
return result;
}
private int[] getPreSum(int N) {
int[] preSum = new int[N + 1];
int[] flags = getCheckNumbers(N);
for (int idx = 2; idx <= N; idx++) {
int semiPrimeCount = 0;
if (flags[idx] == 2) {
semiPrimeCount++;
}
preSum[idx] = semiPrimeCount;
}
return preSum;
}
// 1: No prime, 2: SemiPrime
private int[] getCheckNumbers(int N) {
int[] flags = new int[N + 1];
flags[0] = 1;
flags[1] = 1;
for (int idx = 2; idx * idx <= N; idx++) {
if (flags[dxi] == 1) {
continue;
}
int multiple = idx * idx;
while (multiple <= N) {
if (flags[idx] == 0 && flags[multiple / idx] == 0) {
flags[multiple] = 2;
} else {
flags[multiple] = 1;
}
multiple = multiple + idx; // Next multiple number.
}
}
return flags;
}
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int N, int[] P, int[] Q) {
int[] result = new int[P.length];
int[] preSum = getPreSum(N);
for (int idx = 0; idx < P.length; idx++) {
result[idx] = preSum[Q[idx]] - preSum[P[idx] - 1];
}
return result;
}
private int[] getPreSum(int N) {
int[] preSum = new int[N + 1];
int[] flags = getCheckNumbers(N);
for (int idx = 2; idx <= N; idx++) {
int semiPrimeCount = 0;
if (flags[idx] == 2) {
semiPrimeCount++;
}
preSum[idx] = semiPrimeCount;
}
return preSum;
}
// 1: No prime, 2: SemiPrime
private int[] getCheckNumbers(int N) {
int[] flags = new int[N + 1];
flags[0] = 1;
flags[1] = 1;
for (int idx = 2; idx * idx <= N; idx++) {
if (flags[idx] == 1) {
continue;
}
int multiple = idx * idx;
while (multiple <= N) {
if (flags[idx] == 0 && flags[multiple / idx] == 0) {
flags[multiple] = 2;
} else {
flags[multiple] = 1;
}
multiple = multiple + idx; // Next multiple number.
}
}
return flags;
}
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int N, int[] P, int[] Q) {
int[] result = new int[P.length];
int[] preSum = getPreSum(N);
for (int idx = 0; idx < P.length; idx++) {
result[idx] = preSum[Q[idx]] - preSum[P[idx] - 1];
}
return result;
}
private int[] getPreSum(int N) {
int[] preSum = new int[N + 1];
int[] flags = getCheckNumbers(N);
for (int idx = 2; idx <= N; idx++) {
if (flags[idx] == 2) {
semiPrimeCount++;
}
preSum[idx] = semiPrimeCount;
}
return preSum;
}
// 1: No prime, 2: SemiPrime
private int[] getCheckNumbers(int N) {
int[] flags = new int[N + 1];
flags[0] = 1;
flags[1] = 1;
for (int idx = 2; idx * idx <= N; idx++) {
if (flags[idx] == 1) {
continue;
}
int multiple = idx * idx;
while (multiple <= N) {
if (flags[idx] == 0 && flags[multiple / idx] == 0) {
flags[multiple] = 2;
} else {
flags[multiple] = 1;
}
multiple = multiple + idx; // Next multiple number.
}
}
return flags;
}
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int N, int[] P, int[] Q) {
int[] result = new int[P.length];
int[] preSum = getPreSum(N);
for (int idx = 0; idx < P.length; idx++) {
result[idx] = preSum[Q[idx]] - preSum[P[idx] - 1];
}
return result;
}
private int[] getPreSum(int N) {
int[] preSum = new int[N + 1];
int[] flags = getCheckNumbers(N);
int semiPrimeCount = 0;
for (int idx = 2; idx <= N; idx++) {
if (flags[idx] == 2) {
semiPrimeCount++;
}
preSum[idx] = semiPrimeCount;
}
return preSum;
}
// 1: No prime, 2: SemiPrime
private int[] getCheckNumbers(int N) {
int[] flags = new int[N + 1];
flags[0] = 1;
flags[1] = 1;
for (int idx = 2; idx * idx <= N; idx++) {
if (flags[idx] == 1) {
continue;
}
int multiple = idx * idx;
while (multiple <= N) {
if (flags[idx] == 0 && flags[multiple / idx] == 0) {
flags[multiple] = 2;
} else {
flags[multiple] = 1;
}
multiple = multiple + idx; // Next multiple number.
}
}
return flags;
}
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int N, int[] P, int[] Q) {
int[] result = new int[P.length];
int[] preSum = getPreSum(N);
for (int idx = 0; idx < P.length; idx++) {
result[idx] = preSum[Q[idx]] - preSum[P[idx] - 1];
}
return result;
}
private int[] getPreSum(int N) {
int[] preSum = new int[N + 1];
int[] flags = getCheckNumbers(N);
int semiPrimeCount = 0;
for (int idx = 2; idx <= N; idx++) {
if (flags[idx] == 2) {
semiPrimeCount++;
}
preSum[idx] = semiPrimeCount;
}
return preSum;
}
// 1: No prime, 2: SemiPrime
private int[] getCheckNumbers(int N) {
int[] flags = new int[N + 1];
flags[0] = 1;
flags[1] = 1;
for (int idx = 2; idx * idx <= N; idx++) {
if (flags[idx] == 1) {
continue;
}
int multiple = idx * idx;
while (multiple <= N) {
if (flags[idx] == 0 && flags[multiple / idx] == 0) {
flags[multiple] = 2;
} else {
flags[multiple] = 1;
}
multiple = multiple + idx; // Next multiple number.
}
}
return flags;
}
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int N, int[] P, int[] Q) {
int[] result = new int[P.length];
int[] preSum = getPreSum(N);
for (int idx = 0; idx < P.length; idx++) {
result[idx] = preSum[Q[idx]] - preSum[P[idx] - 1];
}
return result;
}
private int[] getPreSum(int N) {
int[] preSum = new int[N + 1];
int[] flags = getCheckNumbers(N);
int semiPrimeCount = 0;
for (int idx = 2; idx <= N; idx++) {
if (flags[idx] == 2) {
semiPrimeCount++;
}
preSum[idx] = semiPrimeCount;
}
return preSum;
}
// 1: No prime, 2: SemiPrime
private int[] getCheckNumbers(int N) {
int[] flags = new int[N + 1];
flags[0] = 1;
flags[1] = 1;
for (int idx = 2; idx * idx <= N; idx++) {
if (flags[idx] == 1) {
continue;
}
int multiple = idx * idx;
while (multiple <= N) {
if (flags[idx] == 0 && flags[multiple / idx] == 0) {
flags[multiple] = 2;
} else {
flags[multiple] = 1;
}
multiple = multiple + idx; // Next multiple number.
}
}
return flags;
}
}
The solution obtained perfect score.