CODEWITHSUNDEEP
algorithmmathprime-factoring
Denis Rozimovschii
Denis Rozimovschii

Reputation: 448

How many numbers have a maximum number of unique prime factors in a given range

Note that the divisors have to be unique

So 32 has 1 unique prime factor [2], 40 has [2, 5] and so on.

Given a range [a, b], a, b <= 2^31, we should find how many numbers in this range have a maximum number of unique divisors.

The best algorithm I can imagine is an improved Sieve of Eratosthenes, with an array counting how many prime factors a number has. But it is not only O(n), which is unacceptable with such a range, but also very inefficient in terms of memory.

What is the best algorithm to solve this question? Is there such an algorithm?

Upvotes: 4

Views: 1372

Answers (1)

MvG
MvG

Reputation: 60958

I'll write a first idea in Python-like pseudocode. First find out how many prime factors you may need at most:

p = 1
i = 0
while primes[i] * p <= b:
    p = p * primes[i]
    i = i + 1

This only used b, not a, so you may have to decrease the number of actual prime factors. But since the result of the above is at most 9 (as the product of the first 10 primes already exceeds 231), you can conceivably go down from this maximum one step at a time:

cnt = 0
while cnt == 0:
    cnt = count(i, 1, 0)
    i = i - 1
return cnt

So now we need to implement this function count, which I define recursively.

def count(numFactorsToGo, productSoFar, nextPrimeIndex):
    if numFactorsToGo > 0:
        cnt = 0
        while productSoFar * primes[nextPrimeIndex] <= b:
            cnt = cnt + count(numFactorsToGo - 1,
                              productSoFar * primes[nextPrimeIndex],
                              nextPrimeIndex + 1)
            nextPrimeIndex = nextPrimeIndex + 1
        return cnt
    else:
        return floor(b / productSoFar) - ceil(a / productSoFar) + 1

This function has two cases to distinguish. In the first case, you don't have the desired number of prime factors yet. So you multiply in another prime, which has to be larger than the largest prime already included in the product so far. You achieve this by starting at the given index for the next prime. You add the counts for all these recursive calls.

The second case is where you have reached the desired number of prime factors. In this case, you want to count all possible integers k such that a ≤ k∙p ≤ b. Which translates easily into ⌈a/p⌉ ≤ k ≤ ⌊b/p⌋ so the count would be ⌊b/p⌋ − ⌈a/p⌉ + 1. In an actual implementation I'd not use floating-point division and floor or ceil, but instead I'd make use of truncating integer division for the sake of performance. So I'd probably write this line as

        return (b // productSoFar) - ((a - 1) // productSoFar + 1) + 1

As it is written now, you'd need the primes array precomouted up to 231, which would be a list of 105,097,565 numbers according to Wolfram Alpha. That will cause considerable memory requirements, and will also make the outer loops (where productSoFar is still small) iterate over a large number of primes which won't be needed later on.

One thing you can do is change the end of loop condition. Instead of just checking that adding one more prime doesn't make the product exceed b, you can check whether including the next primesToGo primes in the product is possible without exceeding b. This will allow you to end the loop a lot earlier if the total number of prime factors is large.

For a small number of prime factors, things are still tricky. In particular if you have a very narrow range [a, b] then the number with maximal prime factor count might well be a large prime factor times a product of very small primes. Consider for example [2147482781, 2147482793]. This interval contains 4 elements with 4 distinct factors, some of which contain quite large prime factors, namely

  • 3 ∙ 5 ∙ 7 ∙ 20,452,217
  • 22 ∙ 3 ∙ 11 ∙ 16,268,809
  • 2 ∙ 5 ∙ 19 ∙ 11,302,541
  • 23 ∙ 7 ∙ 13 ∙ 2,949,839

Since there are only 4,792 primes up to sqrt(231), with 46,337 as their largest (which fits into a 16 bit unsigned integer). It would be possible to precompute only those, and use that to factor each number in the range. But that would again mean iterating over the range. Which makes sense for small ranges, but not for large ones.

So perhaps you need to distinguish these cases up front, and then choose the algorithm accordingly. I don't have a good idea of how to combine these ideas – yet. If someone else does, feel free to extend this post or write your own answer building on this.

Upvotes: 1

Related Questions