algorithm - 找出具有最多除数的数字的最快方法

Question

给定一个数字 n一个人能以多快的速度找到具有最多因子且小于 n 的最小数？
PS:除了寻找所有数字的除数数量的天真方法之外 n .

更新:我的观察:

int solve(int primes[],int s,int n)
{
    int i=0;
    while(s<n)
    {
        s*=primes[i];
        i++;
    }
    if(s>n)
        s/=primes[i-1];
    return s;
}
int main()
{
    int primes[] = {2,3,5,7,11,13,17,19,23,29,31,37};
    int n;
    scanf("%d",&n);
    int s=1;
    while(s*2<n)//checking the possibility of existence of any prime such that s*p<n
    {
        s=solve(primes,s,n);
    }
    printf("%d\n",s);
}

output为此 100000是60060 .这个观察是真的吗？因为我没有这种方法的任何具体证据。我观察到的是，假设采用素数数组 {2,3,5,7,11}并假设给定的 n是100 .然后观察不断乘以不同的素数直到你得到它>100 .即2*3*5 .再次从第一个元素开始将数组中的素数相乘。即2*3*5*2 .这是所需的数量 60与 12 factors.Now 没有素数可以相乘而不超过 100 .这个观察是真的吗？如果它是真的，那么素数最多为 37我们可以处理n<=10000000很容易。下面的所有数字100大多数因素是60, 72, 84, 90和 96 .我们用这种方法得到了这些数字中最小的。都有12因素。 100 以下的数字都不会超过 12因素。

Answer 1

我觉得这个问题可以用类似于Hamming Number的算法来解决, 事实上你最初的概念也与汉明数非常相似。

海明数是生成数x的问题，其中x = 2^i * 3*j * 5*k，从small to large O(N) 其中 N 是要生成的汉明数的数量。

在这里，我认为可以使用类似的概念，但我们必须使用低于上限的素数集而不是 {2,3,5}，我们只需要计算生成数时质因子的最大#，生成数大于N后输出。

---

例如，这里是海明数列表(使用 {2,3,5} 用于演示目的)<100:

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 81 90 96 100

60 = 2^2 * 3^1 * 5^1，总因子 = 3*2*2 = 12 或

96 = 2^5 * 3^1，总因子 = 6*2 = 12

因此可能有多个答案，但您应该能够在生成汉明数时捕获它们。

---

可以证明它在逻辑上是正确的，因为

1. 数字是由质数(质因数)产生的
2. 数字按顺序生成

请注意，在您的情况下，基本上您正在生成从 1 到上限的所有正数。

这是一个网站，其中包含大量使用不同语言实现此算法以生成汉明数的示例:https://rosettacode.org/wiki/Hamming_numbers