java - 计算给定范围 [a..b] 中的半素数

Question

我正在解决 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。

为以下假设编写一个有效的算法:

• 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 以保存数组的半素数。它帮助我解决了几个性能测试。

Answer 1

100%的Java解决方案如下:

• 找出其乘积不大于N

  的素数集

• 从它们创建半素数作为 0 和 1 的位元数组

• 创建半素数的前缀和

• 在O(M)

  中计算从P[i]到Q[i]的查询/li>

整个算法的复杂度为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;
            }
        }
    }
}