确定可以计入素数的下一个最高数字{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(链接)等算法能够以有效的方式运行.给定的链接讨论了该算法对于可以被分解为小素数的长度的输入是最优的.

如对该问题的评论中所建议的,如果FFTW算法是最优的,则看起来仅允许形式为2 ^ a*3 ^ b*5 ^ c*7 ^ d的数字.

Answer 1

例如,标准FFTW分布对于大小可以被分解为小素数(2,3,5和7)的数组效率最高,否则它使用较慢的通用例程.

真的,你不需要下一个最高,但只是相当接近的东西.最简单的方法就是选择最接近的2的幂.这将最多浪费原始阵列的大小.

为此,找到最重要的位并将其乘以2.

找到最重要位的明显方法:

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