求从start到end的质数因子个数为k的所有数的数组（老是超时，还有什么简单算法吗）

Question

最开始使用的算法
/**
*
* @param k质数因子个数
* @param start开始位置
* @param end结束位置
* @return质数因子个数为k的数值组成的数组
*/
public static long[] countKprimes(int k, long start, long end) {
ArrayList kPrimes = new ArrayList<>();
for (long i = start; i <= end; i++) {
long temp = i;
int prime = 2;
int pCount = 0;
while (prime <= temp) {
while (temp % prime == 0) {
pCount++;
temp /= prime;
}
prime++;
}
if (pCount == k) {
kPrimes.add(i);
}
}
return kPrimes.stream().mapToLong(s -> s.longValue()).toArray();
}

第二次尝试的算法

public static long[] countKprimes(int k, long start, long end) {
    ArrayList<Long> kPrimes = new ArrayList<>();
    for (long i = start; i <= end; i++) {
        int t = (int) i;
        int pc = 0;
        while (t % 2 == 0) {
            pc++;
            t /= 2;
        }
        for (int l = 3; l <= Math.sqrt(t); l += 2) {
            while (t % l == 0) {
                pc++;
                t /= l;
            }
        }
        if (t != 1) {
            pc++;
        }
        if (pc == k) {
            kPrimes.add(i);
        }
    }
    return kPrimes.stream().mapToLong(s -> s.longValue()).toArray();
}

两种算法都显示超时，有没有耗时更少的算法

Answer 1

你既然有质数表了
for (int l = 3; l <= Math.sqrt(t); l += 2) {
这里只要对<= Math.sqrt(t)的质数进行判断即可，而不需要每个数字去比较