获取 non-prime 个数字及其低于给定最大值的因数

Question

我需要随机选择一个低于给定最大值的 non-prime 个数字，以及 return 它的所有因子。

我已经将所有 non-prime 及其因子存储在 Map<Integer, Integer[]> 中，该 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 的 collections 可供选择。

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));
}

Answer 2

生成一个小于最大值的随机数，通过查看 table 检查它是否为非素数。如果是质数从头开始，即生成一个新的随机数。

因为非素数比素数更频繁，所以这个过程不会花很长时间。

获取 non-prime 个数字及其低于给定最大值的因数

Get a non-prime number and its factors below a given maximum

java

collections

guava