logo标签列表

在给定的区间[a..b]内计算半质数的数量。

javaalgorithmperformance
3

我正在解决Codility问题 CountSemiprimes：计算给定区间[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。

编写一个高效的算法，满足以下条件：

  • N是在[1..50,000]范围内的整数；
  • M是在[1..30,000]范围内的整数；
  • 数组P，Q的每个元素都是在[1..N]范围内的整数；P[i] ≤ Q[i]。

我的解决方案

我的当前得分为66％，性能问题是针对大数据集：

  • 大随机数，长度=〜30,000
  • 所有最大范围

测试表明，它应该花费约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来存储半素数。这对于解决一些性能测试非常有帮助。

6
你应该使用像欧拉筛法这样的东西来生成质数。我认为这样会更快。 - marstran
1
@marstran 我已经检查过了。使用for循环到sqrt(n)是找到所有质数 [0...n] 最有效的方法。 - oleg.cherednik
1
这绝对不是找出所有小于n的质数的最有效方法。检查单个值是否为质数更好，但有办法使其更快，比如使用i += 2而不是i++，或者只需检查形式为6*i ± 1的值的可除性。筛法始终是生成质数列表的最佳方法。您已经错误地进行了基准测试。 - phuclv
@phuclv 无论如何，这都不会增加3倍。 - oleg.cherednik
布尔数组似乎很聪明，但我想知道我们是否可以做得更好？将所有半质数放入排序数组中，并使用二进制搜索查找p[i]和q[i]。找到的两个索引之间的差是范围内半质数的数量。你可以试试看。 - Ole V.V.
2
@oleg.cherednik 一个循环到 sqrt(n) 的for循环可能是确定一个数是否为质数的最快方法。但是，生成素数列表的最快方法并不是它。对于这个目的，筛法要快得多。 - marstran
15个回答
4
一份得分100％的Java解决方案如下：

  • 找出质数集合，其中它们的乘积不大于N

  • 从它们中创建半质数，作为0和1的位数组

  • 创建半质数的前缀和

  • 在O(M)的时间内计算从P[i]到Q[i]的查询

整个算法的时间复杂度为O(N * log(log(N)) + M)，根据Codility的测试结果评估。
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;
            }
        }
    }
}
2
您可以预先计算一个大小为N+1的数组A，其中A[i]存储小于或等于i的半质数数量。然后查询p，q可以立即计算：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)。[注意：我猜第一部分的复杂度比O((N/log N)^2)更好，因为内部循环的早期终止，但我没有证明]。使用埃拉托斯特尼筛法计算P中的质数是O(N log log N)。
一个Python版本的该程序在预计算N=50000的A并执行30000个查询时需要0.07秒。在codility上运行时得分100分，并且codility报告检测到该代码的复杂度为O(N log(log(N)) + M)。
1

这是我的 C++ 100% 解决方案，你可以在我的 github 中找到其他答案：


vector<int> getFactArr(int n) {
    vector<int> f(n+1, 0);
    f[1] = 1;
    int i = 2;
    while (i * i <= n) {
        if (f[i] == 0) {
            int k = i * i;
            while (k <= n) {
                if (f[k] == 0)
                    f[k] = i;
                k+=i;
            }
        }
        i++;
    }

    return f;
}

vector<int> solution(int N, vector<int> &P, vector<int> &Q) {
    vector<int> F = getFactArr(N);
    vector<int> prefix_semi_primes(N + 1, 0);

    for (int x = 1; x <= N; x++) {
        if (F[x] > 0 && F[x / F[x]] == 0)
            prefix_semi_primes[x]++;
        prefix_semi_primes[x] += prefix_semi_primes[x - 1];
    }

    const int M = P.size();
    vector<int> ans(M, 0);
    for (int i = 0; i < M; i++) {
        ans[i] = prefix_semi_primes[Q[i]] - prefix_semi_primes[P[i] - 1];
    }

    return ans;
}
1
我的解决方案使用埃拉托色尼筛法，以便将数字N的最小质因数存储在Factor [N]数组中。 然后，如果Factor [N / Factor [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
是的，它可以。您需要选择Python而不是Java作为您使用的语言。这里是证明 https://app.codility.com/demo/results/trainingHSYMM6-UCK/ - 4Rom1
1

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
0

使用通常的筛法得到小于N的所有质数。

使用质数来获取小于N的半素数。可以通过检查任何数字是否有两个质因数来实现。

创建前缀和以存储特定索引处的半素数数量。

最后，通过减去查询结束和开始处的数字来获取半素数计数。

vector<int> solution(int N, vector<int> &P, vector<int> &Q)                     
{                                                                               
  vector<int> sieve(N, 0);                                                      
  for (int prime = 2; prime * prime <= N; ++prime) {                            
    for (int composite = prime * prime; composite <= N; composite += prime) {   
      if (!sieve[composite - 1]) sieve[composite - 1] = prime;                  
    }                                                                           
  }                                                                             
                                                                                
  vector<int> semi_primes;                                                      
  for (int i = 3; i < N; ++i) {                                                 
    const int e = sieve[i];                                                     
    if (e > 0 && !sieve[i / e]) semi_primes.push_back(i + 1);                   
  }                                                                             
  if (semi_primes.empty()) semi_primes.push_back(0);                            
                                                                                
  vector<int> prefix_sums(N + 1, 0);                                            
  for (int i = 1, spi = 0; i <= N; ++i) {                                       
    prefix_sums[i] = ((semi_primes[spi] != i) ? spi : ++spi);                   
  }                                                                             
                                                                                
  int M = P.size();                                                             
  vector<int> semi_prime_counts(M, 0);                                          
  for (int i = 0; i < M; ++i) {                                                 
    semi_prime_counts[i] = prefix_sums[Q[i]] - prefix_sums[P[i] - 1];           
  }                                                                             
                                                                                
  return semi_prime_counts;                                                     
}
0

function solution(N, P, Q) {
      // write your code in JavaScript (Node.js 8.9.4)
    let pr =[];let fn =[]
    for(var i=2;i<=N;i++){
        if(isPrime(i)){
            pr.push(i)
        }
    }
    let spr = [],mul,br=0
    for(var i=0;i<pr.length;i++){
        for(var j=0; j <pr.length;j++){
            mul = pr[i] * pr[j];
            if(mul <= N) {
                spr.push(mul)
            }else{
                br =1;
                break;
            }
        }
        // if(br==1) break;
    }
    let nm = [];
    //let o =0
    for(var i=0;i<=N;i++){
       if(spr.indexOf(i) >=0){
        //    ++o
           nm.push(1)
       }else{
            nm.push(0)
       }

    }

    // spr = Array.from(new Set(spr))
    // spr.sort((a,b)=> a- b)
    let a,b,c
    for(var i =0;i<P.length;i++){
        // a= findme(P[i],spr)
        // b= findme(Q[i],spr)
        // a= nm[P[i]]
        // b= nm[Q[i]]
        c= nm.slice(P[i],Q[i]+1).reduce((a,b)=> a+b)
        // c=c <=0 ? 0 : c+1
        // fn.push(b - a + 1)
        fn.push(c)
    }
    return fn
}

function findme(a,arr){
    for(var i= 0; i< arr.length;i++){
        if(a <= arr[i]) return i;
    }
}

function isPrime(num){
    if (num ===2) return true
    for(var i = 2; i < num; i++)
    if(num % i === 0) return false;
    return num > 1;
}
0
/**
     * https://app.codility.com/demo/results/trainingPBRVXK-28Q/
     * time complexity: O(N * log(log N) + M
     * space complexity: O(2N + N)
     */
public class CountSemiPrime {

    /**
     * 2D array for sieving numbers 1..N
     * 1 - prime, 2 - semiprime, 3 - composite
     */
    public int[][] sieve(int N) {
        int[][] sieve = new int[N+1][1];
        for (int i=1; i<=N; i++) {
            sieve[i][0] = 1; // make prime default
        }
        for (int i=2; i<= N; i++) {
            if (sieve[i][0] == 1) { // if this num is prime, tag its multiples as semi-prime
                int next_number = i + i;
                while (next_number <= N) {
                    sieve[next_number][0] = 2;
                    next_number += i;
                }
            }
            // if this num is semi-prime, tag its multiples as composite
            else if (sieve[i][0] == 2) {
                int next_number = i + i;
                while (next_number <= N) {
                    sieve[next_number][0] = 3;
                    next_number += i;
                }
            }
        }
        return sieve;
    }

    public int[] solution(int N, int[] P, int[] Q) {
        // first, we need to establish prime and semi-prime numbers from 1 to N, in a sieve
        int[][] sieve = sieve(N);
        int[] prefix_sum_of_sieve = new int[sieve.length];

        for (int i=1; i<sieve.length; i++) {
            if (sieve[i][0]==2) {
                prefix_sum_of_sieve[i] = prefix_sum_of_sieve[i-1] + 1;
            }
            else {
                prefix_sum_of_sieve[i] = prefix_sum_of_sieve[i-1];
            }
        }

        int[] results = new int[P.length];
        // we count the semiprime of N from P and Q, for each P & Q from the prefix sum
        for (int i=0; i < P.length; i++) {
            results[i] = prefix_sum_of_sieve[Q[i]] - prefix_sum_of_sieve[P[i]-1];
        }

        return results;
    }
}

希望解释/评论易于理解。
0

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
)

1
你能详细说明一下，而不仅仅是发布代码片段吗？ - Ryan Kozak
0

这是一个有趣的问题。我尝试了一下，得了88%的分数。

这是我的策略：

  • 我使用Eratosthenes筛法获取质数的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）中回答每个查询也是显而易见的优化。

与解决方案无关，但我的任务得分为88％，正确性为100％，性能为80％。我很乐意听取建议和任何我错过的东西。

希望这有所帮助。:)

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接