查找不小于N的最小正则数 [英] Find the smallest regular number that is not less than N

问题描述

常规数字是均分60的幂的数字.例如，60 ² = 3600 = 48×75，因此48和75都是60的幂的因数.因此，它们也是正数.

Regular numbers are numbers that evenly divide powers of 60. As an example, 60² = 3600 = 48 × 75, so both 48 and 75 are divisors of a power of 60. Thus, they are also regular numbers.

这是的扩展，向上取整为2的下一个幂.

我有一个整数值 N ，它可能包含大素数，我想将其四舍五入为仅包含小素数(2、3和5)的数字

I have an integer value N which may contain large prime factors and I want to round it up to a number composed of only small prime factors (2, 3 and 5)

示例:

• f(18) == 18 == 21 * 32
• f(19) == 20 == 22 * 51
• f(257) == 270 == 21 * 33 * 51

• f(18) == 18 == 21 * 32
• f(19) == 20 == 22 * 51
• f(257) == 270 == 21 * 33 * 51

找到满足此要求的最小号的有效方法是什么?

What would be an efficient way to find the smallest number satisfying this requirement?

涉及的值可能很大，所以我想避免枚举从1开始的所有常规数字或维护所有可能值的数组.

The values involved may be large, so I would like to avoid enumerating all regular numbers starting from 1 or maintaining an array of all possible values.

推荐答案

好的，希望第三次是这里的魅力.一种针对p的初始输入的递归分支算法，其中N是每个线程中正在构建"的数字.此处的NB 3a-c是作为单独的线程启动的，或通过其他方式(准)异步完成的.

Okay, hopefully third time's a charm here. A recursive, branching algorithm for an initial input of p, where N is the number being 'built' within each thread. NB 3a-c here are launched as separate threads or otherwise done (quasi-)asynchronously.

1. 计算p之后的第二大幂2，称为R.N = p.

1. Calculate the next-largest power of 2 after p, call this R. N = p.

N> R吗?退出该线程. p是否仅由小的素数组成?你完成了.否则，请转到步骤3.

Is N > R? Quit this thread. Is p composed of only small prime factors? You're done. Otherwise, go to step 3.

3a-c中的任何一个之后，请转到步骤4.

After any of 3a-c, go to step 4.

a)将p舍入到最接近的2的倍数.此数字可以表示为m *2.
b)将p舍入到最接近的3的倍数.此数字可以表示为m *3.
c)将p舍入到最接近的5的倍数.此数字可以表示为m *5.

a) Round p up to the nearest multiple of 2. This number can be expressed as m * 2.
b) Round p up to the nearest multiple of 3. This number can be expressed as m * 3.
c) Round p up to the nearest multiple of 5. This number can be expressed as m * 5.

使用p = m转到步骤2.

Go to step 2, with p = m.

我已经省略了有关跟踪N的簿记工作，但是我很容易做到这一点.

I've omitted the bookkeeping to do regarding keeping track of N but that's fairly straightforward I take it.

忘记了6，谢谢ypercube.

Forgot 6, thanks ypercube.

如果多达30个(5、6、10、15、30)意识到这是不必要的，则将其删除.

Edit 2: Had this up to 30, (5, 6, 10, 15, 30) realized that was unnecessary, took that out.

编辑3 :(我保证的最后一个！)添加了30次幂检查功能，这有助于防止该算法耗尽您的所有RAM.

Edit 3: (The last one I promise!) Added the power-of-30 check, which helps prevent this algorithm from eating up all your RAM.

根据finnw的观察，将30次幂更改为2次幂.

Edit 4: Changed power-of-30 to power-of-2, per finnw's observation.

这篇关于查找不小于N的最小正则数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！