两个数之间的半素数个数

Question

我正在解决一个编码问题，我调整了一些现有代码，以便能够计算出存在多少个半素数，直到并包括一定数量。

但是，我卡在了计算两个数字之间唯一半素数的部分，例如10 和 4，即 4、6、9 和 10，即 4。我的答案只是说 10 有 4 个半素数，4 有 1 个半素数，所以它们之间的子素数是 4-1 =3 .这就是我出错的地方。

代码在这里：

public class SemiPrimeRange {
    public static int[] solution(int N, int[] P, int[] Q) {
        int arrSize = P.length;
        int[] arr = new int[arrSize];

        for (int i = 0; i < arr.length; i++) {
            int n = NoSemiPrimes(Q[i]);
            int m = NoSemiPrimes(P[i]);
            arr[i] = n-m;
        }

        for (int i : arr) {
            System.out.println(i);
        }
        return arr;

    }

    public static int NoSemiPrimes(int large) {
        int n = 0;

        boolean[] primeTop = new boolean[large + 1];
        boolean[] semiprimeTop = new boolean[large + 1];
        for (int i = 2; i <= large; i++) {
            primeTop[i] = true;
        }

        for (int i = 2; i * i <= large; i++) {
            if (primeTop[i]) {
                for (int j = i; i * j <= large; j++) {
                    primeTop[i * j] = false;
                }
            }
        }

        int primes = 0;
        for (int i = 2; i <= large; i++) {
            if (primeTop[i])
                primes++;
        }

        for (int i = 0; i < large; i++) {
            semiprimeTop[i] = false;
        }

        for (int i = 0; i <= large; i++) {
            for (int j = i; j <= large; j++) {
                if (primeTop[j]&&primeTop[i]) {
                    if(i*j<=large){
                        semiprimeTop[j*i] = true;
                    }           
                }
            }
        }

        for (int i = 0; i < semiprimeTop.length; i++) {
            System.out.println(semiprimeTop[i]);
        }

        int semiprimes = 0;
        for (int i = 2; i <= large; i++) {
            if (semiprimeTop[i])
                semiprimes++;
        }

        System.out.println("The number of semiprimes <= " + large + " is " + semiprimes);
        return semiprimes;

    }

    public static void main(String[] args) {
        int[] P = { 1, 4, 16 };
        int[] Q = { 26, 10, 20 };
        int N = 26;
        solution(N, P, Q);
    }

Answer 1

如果你想要 y 和 x 之间的半素数数 (y > x), count(y) - count(x) (count(a)是 a 和 1) 之间的半素数数不是正确的公式，因为如果它是半素数，它将省略 x。正确的公式是 count(y) - count(x - 1).

另请注意，您的代码无效，因为它会在 1 和较小的数字之间计数两次。

方法签名应该是

public static int NoSemiPrimes(int small, int large)

并更改循环

int semiprimes = 0;
for (int i = 2; i <= large; i++) {
    if (semiprimeTop[i])
        semiprimes++;
}

到

int semiprimes = 0;
for (int i = small; i <= large; i++) {
    if (semiprimeTop[i])
        semiprimes++;
}

直接计算所需范围内的半素数，而不是使用两次int NoSemiPrimes(int large)。

两个数之间的半素数个数

Number of semi-primes between two numbers

java

algorithm

primes

sieve-of-eratosthenes