java 需要帮助查找第n个正则数

xqkwcwgp  于 2023-05-27  发布在  Java
关注(0)|答案(1)|浏览(125)

问题:
“巴比伦人使用有规律的数字来计时。
在数学中,“正则数”被定义为是60的某个幂的因数(60,3600等)。等价地,我们可以说一个正则数是一个只有2,3和5的素因子的数。前10个常规数字是:
1,2,3,4,5,6,8,9,10,12.
你的任务是找到第n个正规数。”
我的教授要求我们专门使用优先级队列来解决这个问题,我们将测试的最大数字不超过 n = 300。我很无知。
编辑:我显然不是要求完整的代码,我只是需要指针让我开始。

0s0u357o

0s0u357o1#

不知道为什么要使用PriorityQueue,但解决这个问题的一个非常丑陋的蛮力方法是这样的。

import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.stream.Collectors;

public class Driver {

    public static void main(String[] args) {
        Driver driver = new Driver();
        System.out.println(driver.getRegularNumber(30)
                .toString());
    }

    public PriorityQueue<Integer> getRegularNumber(int n) {
        PriorityQueue<Integer> regularNumbers = new PriorityQueue<>();
        int count = 0;
        int current = 1;
        List<Integer> pf;
        List<Integer> apf = Arrays.asList(2, 3, 5);
        while (count < n) {
            // Get the prime factors of the current number.
            // If it is a subset of the allowed prime factors then add it to the Queue.
            pf = primeFactors(current);
            if (apf.containsAll(pf)) {
                regularNumbers.add(current);
                count++;
            }
            current++;
        }
        return regularNumbers;
    }

    public static List<Integer> primeFactors(int n) {
        List<Integer> factors = new ArrayList<>();
        for (int i = 2; i < n; i++) {
            while (n % i == 0) {
                factors.add(i);
                n = n / i;
            }
        }
        if (n > 2) {
            factors.add(n);
        }

        factors = factors.stream()
                .distinct()
                .collect(Collectors.toList());
        return factors;
    }
}

这将产生[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50, 54, 60, 64, 72, 75, 80]作为输出。

相关问题