Decompose integers larger than 100 digits [closed]

问题:

X and Y are integers larger than 100 digits. Find the integer P which is within the range [X, Y[ and that guaranties the "best" prime decomposition (i.e. the decomposition with the most unique prime factors).

What I've done is just check the primality and decompose each number in the range and find the number that respects the rule. Is there any other way to do this?

An example on small integers

Edit:

In the above example, 123456 is decomposed to
2^6 * 3^1 * 643^1, that's 2 * 2 * 2 * 2 * 2 * 2 * 3 * 643 but only 3 unique factors.

While the answer, 123690, is decomposed to 6 unique factors
2^1 * 3^1 * 5^1 * 7^1 * 19^1 * 31^1.

回答1:

The answer to questions about enumerating prime numbers is always to find a way to solve the problem using a sieve; in your case, you are looking for "anti-prime" numbers with a large number of factors, but the principle still applies.

The key to this question is that, for most numbers, most of the factors are small. Thus, my suggestion is to set up a sieve for the range X to Y, containing integers all initialized to zero. Then consider all the primes less than some limit, as large as convenient, but obviously much smaller than X. For each prime, add 1 to each element of the sieve that is a multiple of the prime. After sieving with all the primes, the sieve location with the largest count corresponds to the number between X and Y that has the most distinct prime factors.

Let's consider an example: take the range 100 to 125 and sieve with the primes 2, 3, 5 and 7. You'll get something like this:

100 2 5
101 (101)
102 2 3 (17)
103 (103)
104 2 (13)
105 3 5 7
106 2 (53)
107 (107)
108 2 3
109 (109)
110 2 5 (11)
111 3 (37)
112 2 7
113 (113)
114 2 3 (19)
115 5 (23)
116 2 (29)
117 3 (13)
118 2 (59)
119 7 (17)
120 2 3 5
121 (11)
122 2 (61)
123 3 (41)
124 2 (31)
125 5

So the winners are 105 and 120, each having three prime factors; you'll have to decide for yourself what to do with ties. Note that some factors are missed: 11 divides 110 and 121, 13 divides 104 and 117, 17 divides 102 and 119, 19 divides 114, 23 divides 115, 29 divides 116, 31 divides 124, 37 divides 111, 41 divides 123, 53 divides 106, 59 divides 118, 61 divides 122, and of course 101, 103, 107, 109, and 113 are prime. That means 102, 110 and 114 also tie for the lead, each having three prime factors. So this algorithm isn't perfect, but for X and Y in the hundred-digit range, and assuming you sieve by the primes to a million or ten million, it is unlikely you will substantially miss the answer.

Good question. Look for it soon at my blog.

回答2:

Take the list of all primes in order (2,3,5,7...) and start multiplying them (2 * 3 * 5 *...) until you get a number >= X. Call this number P'. If its <= Y, you're done, P = P'. If not, start computing P'/2, P'/3, P'/5 etc looking for a number [X,Y]. If you don't find it and get to a number < X, try multiplying in then next prime to P' and continuing. If this still fails, then the range [X,Y] is pretty small, so fall back to the method of factoring all the numbers in that range.

For a small range (Y-X is small), allocate an array of size Y-X+1, zero it, then for all primes <= Y-X, add one to the array elements corresponding to multiples of the prime (simple seive). Then search for the element with the largest total. If that total n is such that (Y-X)ⁿ >= X, then that is the answer. If not, continue sieving primes larger than Y-X until you get to some prime p such that pⁿ > X for some n in the table...

One of the two above methods should work, depending on how large the range is...