查找除数最大的数字的最快方法 [英] 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屋!