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

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

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

0s0u357o

0s0u357o1#

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

  1. import java.util.Arrays;
  2. import java.util.List;
  3. import java.util.PriorityQueue;
  4. import java.util.stream.Collectors;
  5. public class Driver {
  6. public static void main(String[] args) {
  7. Driver driver = new Driver();
  8. System.out.println(driver.getRegularNumber(30)
  9. .toString());
  10. }
  11. public PriorityQueue<Integer> getRegularNumber(int n) {
  12. PriorityQueue<Integer> regularNumbers = new PriorityQueue<>();
  13. int count = 0;
  14. int current = 1;
  15. List<Integer> pf;
  16. List<Integer> apf = Arrays.asList(2, 3, 5);
  17. while (count < n) {
  18. // Get the prime factors of the current number.
  19. // If it is a subset of the allowed prime factors then add it to the Queue.
  20. pf = primeFactors(current);
  21. if (apf.containsAll(pf)) {
  22. regularNumbers.add(current);
  23. count++;
  24. }
  25. current++;
  26. }
  27. return regularNumbers;
  28. }
  29. public static List<Integer> primeFactors(int n) {
  30. List<Integer> factors = new ArrayList<>();
  31. for (int i = 2; i < n; i++) {
  32. while (n % i == 0) {
  33. factors.add(i);
  34. n = n / i;
  35. }
  36. }
  37. if (n > 2) {
  38. factors.add(n);
  39. }
  40. factors = factors.stream()
  41. .distinct()
  42. .collect(Collectors.toList());
  43. return factors;
  44. }
  45. }

这将产生[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]作为输出。

展开查看全部

相关问题