java - 获取非素数及其低于给定最大值的因数

Question

我需要随机选择一个低于给定最大值的非素数，并返回其所有因子。

我已经将所有非素数及其因子存储在 Map<Integer, Integer[]> 中启动时计算一次。

这是一个实现的想法:

public Pair<Integer, Integer[]> getNonPrimeAndFactors(int maximum)
{
    //Randomly select a non-prime less than maximum
    return new Pair<Integer, Integer[]>(nonPrime, factors.get(nonPrime));
}

我不太确定要使用什么数据结构来选择 Map 中的键随机，同时仍小于 maximum 。选择一个小于最大值的随机数，然后向下迭代调用 factors.hasKey(randomNumber--)有点废话。

我使用的是 Java 7 和 Guava，因此可以从 Google 的集合中进行选择。

Answer 1

通过将键集转换为 SortedSet 并保持头集低于最大值，您可以获得小于最大值的随机键。

当你有这样一个集合时，就可以将其转换为列表并通过索引获取随机元素:

public Pair<Integer, Integer[]> getNonPrimeAndFactors(int maximum) {
    SortedSet<Integer> set = new TreeSet<>(factors.keySet()).headSet(maximum);
    List<Integer> keys = new ArrayList<>(set);
    Integer nonPrime = keys.get(ThreadLocalRandom.current().nextInt(keys.size()));
    return new Pair<Integer, Integer[]>(nonPrime, factors.get(nonPrime));
}