查找除数最大的数字的最快方法 [英] Fastest way to find out a number with most divisors
问题描述
给出一个数字 n 可以找到多因素最多且小于n的最小数字的速度有多快?
PS:不是天真的方法，就是找出所有 n 个数的除数.
Given a number n how fast can one find the smallest number with most factors and is less than n?
PS:other than the naive approach of finding number of divisors for all numbers upto 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);
}
100000 的输出为 60060 .这个观察是真的吗?因为我没有这种方法的任何具体证据.我观察到的是，假设采用素数数组 {2,3,5,7,11} 并假定给定的 n 为 100 .然后观察到，不断乘以不同的素数，直到得到> 100 .这是 2 * 3 * 5 .再次从第一个元素开始重复数组中的质数，即 2 * 3 * 5 * 2 .这是需要 60 且具有 12 个因数的数字.现在没有可以乘以不超过 100 的素数.这个观察是真的吗?如果它是真的，那么使用最多为 37 的质数，我们可以轻松处理 n< = 10000000 . 100 以下所有数字中受大多数因素影响的都是 60、72、84、90 和 96 .通过这种方法，我们得到的数字最少.所有因素都有 12 个因素.小于100的数字的系数不超过 12 .
The output for this for 100000 is 60060. Is this observation true? Because I don't have any concrete proof of this approach.
What I observed is that suppose take a prime array {2,3,5,7,11} and suppose that the given n is 100. Then observe that keep multiplying distinct primes until that point that you get it >100. That is 2*3*5.Repeat multiplying primes from the array from the first element again.That is 2*3*5*2. This is the number required 60 with 12 factors.Now there is no prime that can be multiplied without exceeding 100. Is this observation true? If its true then with primes upto 37 we can deal with n<=10000000 easily.All the numbers below 100 with most factors are 60, 72, 84, 90 and 96. We get the smallest of these numbers with this approach. All have 12 factors. No number below 100 has more than 12 factors.
推荐答案
我认为可以通过类似于汉明编号，实际上您的原始概念也与汉明编号非常相似.
I think this problem can be solved by algorithm similar to Hamming Number, indeed your original concept is very similar to Hamming Number as well.
Hamming Number是生成数字 x 的问题，其中 x = 2 ^ i * 3 * j * 5 * k ，从小到大，位于 O(N)中，其中N是要生成的汉明数的数量.
Hamming Number is a problem to generate number x, where x = 2^i * 3*j * 5*k, from small to large in O(N) where N is the number of hamming number to be generated.
在这里，我认为可以使用类似的概念，但是我们必须使用位于您的上限以下的素数集而不是{2,3,5} ，我们只需要计算一下生成数字时的最大素数最大数，并在生成的数字大于N之后输出.
Here, I think similar concept can be used but we have to use the set of prime which is below your upper bound instead of {2,3,5}, we just need to also count the maximum # of prime factors when generating the number, and output it after the number generated is larger than N.
例如，这是汉明码的列表(使用{2,3,5}进行演示)<100:
For example, here is the list of hamming number(using {2,3,5} for demo purpose) < 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或
60 = 2^2 * 3^1 * 5^1, total factors = 3*2*2 = 12 or
96 = 2 ^ 5 * 3 ^ 1，总因子= 6 * 2 = 12
96 = 2^5 * 3^1, total factors = 6*2 = 12
所以可能会有多个答案，但是您应该能够在生成汉明码的同时捕获它们.
So there may be multiple answer but you should be able to capture them while generating hamming number.
一个人可以证明它在逻辑上是正确的，因为
One can show that it is logically correct because
- 数字是由质数(质因数)生成的
- 数字是按顺序生成的
请注意，就您而言，基本上是从1到上限生成所有正数.
Note that in your case, basically you are generating all positive numbers from 1 to your upper bound.
这是一个站点，这里有大量使用不同语言的示例，实现了该算法来生成海明数: https://rosettacode.org/wiki/Hamming_numbers
Here is a site with tons of example in different language implementing this algorithm to generate hamming numbers: https://rosettacode.org/wiki/Hamming_numbers
这篇关于查找除数最大的数字的最快方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
