c++ - 确定可以分解为质数 {2,3,5,7} 的下一个最高数

Question

我想编写一个函数，给定一个无符号整数作为输入参数，并返回下一个可以因式分解为质数 {2, 3, 5, 7} 的最大数。这是一个简短的代码片段，显示了我想要做什么。

unsigned int getHigherNumber(unsigned int x)
{
    // obtain the next highest number that can be factored into
    // prime numbers (2, 3, 5, and 7)
    if (~(x % 2 || x % 3 || x % 5 || x % 7))
        return  x;
    else
    {
         // ???
    }  
} // end

此函数的目的是找出数组中应填充的零的数量，以确保 FFTW (link) 等算法能够高效运行。给定的链接讨论了该算法对于可以分解为小素数的长度的输入是最优的。

正如对此问题的评论中所建议的，如果 FFTW 算法是最优的，似乎只允许 2^a * 3^b * 5^c * 7^d 形式的数字。

Answer 1

For example, the standard FFTW distribution works most efficiently for arrays whose size can be factored into small primes (2, 3, 5, and 7), and otherwise it uses a slower general-purpose routine.

实际上，您不需要下一个最高的，而只需要相当接近的东西。最简单的方法就是选择最接近的 2 的幂。这最多会浪费原始数组的大小。

为此找到最高有效位并将其乘以 2。

The obvious way of finding the most significant bit:

    unsigned int v; // 32-bit word to find the log base 2 of  
    unsigned int r = 0; // r will be most significant bit

    while (v >>= 1)   
    {  
        r++;
    }