如何计算与一定数量的约数最小的数字？ [英] How to calculate smallest number with certain number of divisors?

问题描述

从项目欧拉问题500

120除数的数是16。事实上120具有16的除数的最小数字。

The number of divisors of 120 is 16. In fact 120 is the smallest number having 16 divisors.

查找最小的数与2 ** 500500除数。给你的答案模500500507。

Find the smallest number with 2**500500 divisors. Give your answer modulo 500500507.

这是很简单的计算n的约数，例如。在Python LEN（[我为我的range（1，N + 1）如果n％我== 0]）。这是O（n）。

It's simple enough to count the divisors of n, eg. in Python len([i for i in range(1,n+1) if n % i == 0]). This is O(n).

我试图蛮力搜索，发现最小的数字与32除数是840，但它的多为上述问题的速度太慢。从不平等 count_divisors（N）其中​​。= N ，这个数字将是巨大的。

I tried brute force search and found the smallest number with 32 divisors is 840, but it's much too slow for the problem above. From the inequality count_divisors(n) <= n, the number is going to be massive.

你怎么看？有任何想法吗？如何计算与一定数量的约数最小的数字？

What do you think? Any ideas? How to calculate smallest number with certain number of divisors?

修改：我不认为这是一个重复。这个问题是比较具体的，它涉及某一类的多的较大的数字。 href="http://stackoverflow.com/questions/8861994">其他问题一般询问

Edit: I don't think this is a duplicate. This question is more specific, it concerns a particular class of much larger numbers. The other question asks generally. Its answers aren't applicable to this problem, it's a different magnitude.

推荐答案

您应该使用公式整数除数的数 N ：

You should use the formula for the number of divisors of integer n:

D（N）=（A <子> 1 +1）（A ₂ +1）的 ... 的（A <子> K +1）

d(n) = (a₁+1)(a₂+1)...(a_k+1)

其中

N = P <子> 1 ^{在<子> 1} * P ₂ ^{一<子> 2} * P <子> 3 ^{在<子> 3} * ...... * P <子> K < SUP>在<子> K

是每一个整数通过其素因子的权力独特的重新presentation。这是一个著名的公式，但如果人们不知道如何得到它，注意 D 分歧 N 如果和只有当 D 是形如P <子> 1 ^{X <子> 1} * P <子> 2 ^{X ₂} * P <子> 3 ^{X <子> 3} * .. * P <子> K ^{X <子> K} ，其中各X <子>我介于0和<子>我< /分>，所以有<子>我 + 1的可能性，选择各X <子>我。现在只要取本品规则，你会得到想要的公式。

is a unique representation of every integer through powers of its prime divisors. This is a well-known formula, but if one wonders how to get it, note that d divides n if and only if d is of the form p₁^x₁ * p₂^x₂ *p₃^x₃ *...*p_k^x_k, where each of x_i is between 0 and a_i, so there are a_i + 1 possibilities for choosing each of x_i. Now just apply the product rule and you get the desired formula.

对于固定 D（N）（如你的情况）， N 显然获得的最小值通过仔细选择现有的素数的权力，或通过增加新的素数。让我们的工作，通过这个简单的例子，16：

For fixed d(n) (as in your case), the minimum value of n is obviously obtained by carefully selecting powers of existing primes, or by adding new primes. Let's work through this simple example, 16:

D（X）=（A <子> 1 +1）（A ₂ +1）的 ... 的（A <子> K + 1）= 16 = 2 ⁴ 。

d(x) = (a₁+1)(a₂+1)...(a_k+1) = 16 = 2⁴.

这意味着你最多有4个不同的素数，因此：

This means that you have at most 4 different primes, therefore:

X = 2 ^{在<子> 1} * 3 ^{在 ₂} * 5 ^{在<子> 3} * 7 ^{在<子> 4}

x = 2^a₁ * 3^a₂ *5^a₃ * 7^a₄

其中<子>我> = 0。现在的问题是 - 为了获得 X ，是它更好地提高权力2（即增加一个<子> 1 ），或使用7（即取<子> 4 = 1，而不是<子> 4 = 0） ？那么，它的简单检查，2 * 3 * 5 * 7> 2 ³ * 3 * 5 = 120，这就是为什么120的答案在这种情况下。

where a_i >= 0. The question is now - in order to get minimum value of x, is it better to increase the powers of 2 (i.e., increment a₁), or to use 7 (i.e. take a₄=1 instead of a₄=0)? Well, it's simple to check, 2*3*5*7 > 2³ * 3 * 5 = 120, that's why the 120 is answer in this case.

如何推广这种做法？您应该创建分堆，你就会把素数的权力，照顾的分频器的数量达到指定值。如果16​​，这分堆将包含数字2，3，5，7，2 ² 3 ² 2 ⁴ 等。 为什么？由于16 = 2 ⁴ ，所以每个（一个<子>我 +1）有16分，也就是说，它必须是2，当您添加新的电源功率每次，就应该增加左侧（即变量 D（X））由2的幂，因为你的最终目标是找到最小的数与2 ⁵⁰⁰⁵⁰⁰ 约数。

How to generalize this approach? You should create min-heap where you'll put the powers of primes, taking care that the number of divisors reaches the specified value. In case of 16, this min-heap would contain numbers 2, 3, 5, 7, 2², 3², 2⁴ etc. Why? Because 16 = 2⁴, so each of (a_i+1) has to divide 16, i.e. it has to be power of 2. Every time when you add new power, it should increase the left hand side (i.e., the variable d(x)) by power of 2, since your final goal is to find the smallest number with 2⁵⁰⁰⁵⁰⁰ divisors.

HTH。

这篇关于如何计算与一定数量的约数最小的数字？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！