我正在解决Codility问题CountSemiprimes: Count the semiprime numbers in the given range [a..b]。
素数是一个正整数X，它具有两个不同的除数：1和X.前几个素数整数是2,3,5,7,11和13。
半素是一个自然数，它是两个（不一定是不同的）素数的乘积。前几个半全数是4,6,9,10,14,15,21,22,25,26。
给出两个非空数组P和Q，每个数组由M个整数组成。这些数组表示有关指定范围内的半数的查询。
查询K要求您查找范围内的半参数（P [K]，Q [K]），其中1≤P[K]≤Q[K]≤N。
为以下假设编写有效的算法：
我目前的得分为66％，问题在于大数据集的性能：
测试说，它应该需要大约2秒，但我的解决方案需要7秒。
这是我目前的解决方案
class Solution {
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;
}
private static boolean[] getSemiPrimes(int N) {
List<Integer> primes = getPrimes(N);
boolean[] semiPrimes = new boolean[N + 1];
for (int i = 0; i < primes.size(); i++) {
if (primes.get(i) > N)
break;
for (int j = i; j < primes.size(); j++) {
if (primes.get(j) > N || N / primes.get(i) < primes.get(j))
break;
int semiPrime = primes.get(i) * primes.get(j);
if (semiPrime <= N)
semiPrimes[semiPrime] = true;
}
}
return semiPrimes;
}
public static int[] solution(int N, int[] P, int[] Q) {
boolean[] semiPrimes = getSemiPrimes(N);
int[] res = new int[P.length];
for (int i = 0; i < res.length; i++)
for (int j = P[i]; j <= Q[i]; j++)
if (semiPrimes[j])
res[i]++;
return res;
}
}
关于提高绩效的任何想法？我的最后一个是删除Set持有阵列的半素数。它帮助我解决了几项性能测试。
您可以预先计算大小为N + 1的数组A，该数组A在A [i]处存储小于或等于i的半数。然后可以立即计算查询p, q：p和q（包括）之间的半参数的数量是A[q] - A[p-1]。
可以有效地计算该数组：令P是小于或等于N / 2的素数数组。然后（在类似java的伪代码中）：
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]
这通过在数组中使用1标记半参数，然后获取累积和来起作用。它运行时优于O（N ^ 2）且比O（N）时间更差 - N/2logN中有P素数，所以第一部分是O（（N / logN）^ 2），总结是上）。 [注意：我猜第一部分比O（（N / log N）^ 2）具有更好的复杂性，因为内循环的提前终止，但我没有证明]。使用Erastothenes的筛子计算P中的素数是O（N log log N）。
该程序的Python版本需要0.07秒才能为A预先计算N=50000，并执行30000次查询。当在codility上运行时它获得满分（100），并且codility报告它检测到代码具有复杂度O（N log（log（N））+ M）。
这是一个有趣的问题。我试了一下，获得了88％的分数。
这是我的策略：
BitSet。BitSet，并在primeList中添加了所有素数。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;
}我不太清楚为什么我得到88％的分数。 （我错过了什么）
但最有趣和值得注意的部分是检查给定数字是否为半素数的策略：
请注意，我还做了一个非常天真的簿记形式，我制作了一个累积数组，存储了半素数的总数，直到指数x。一次填充此数组并回答O(1)中的每个查询再次显而易见的优化。
与解决方案无关，但我的Task Score为88％，Correctness为100％，Performance为80％。我很乐意听到我错过的建议和任何建议。
希望这可以帮助。 :)
const isSemiPrime = (num) => {
let cnt = 0
for (let i = 2; cnt < 2 && i * i <= num; ++i) {
while (num % i == 0) {
num /= i
++cnt
}
}
if (num > 1)++cnt
return cnt == 2 ? true : false
}
console.log(
[4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, 55].filter(isSemiPrime)
.length
)我的解决方案使用了Eratosthenes的Sieve，使得数字N的最小素因子存储在数组因子[N]中。然后，如果因子[N /因子[N]] = 0，我们有一个半素数递增和扫描。然后返回数组的入口r为：A [r] = Inclusive_scan [Q [r]] - Inclusive_scan [P [r] -1]。
这里是相应的python代码（100％任务分数）：
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％解决方案
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
获得100％得分的Java解决方案如下：
N的素数集P[i]到Q[i]的O(M)的查询整个算法是由Codility的测试结果评估所述的O(N * log(log(N)) + M)。
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;
}
}
}
}