CODEWITHSUNDEEP
algorithmmathcalculatordivision
ucei
ucei

Reputation: 51

First number that divides all numbers (1,2,...,100)

Given that the first number to divide all (1,2,..,10) is 2520. And given that the first number to divide all (1,2,..,20) is 232792560. Find the first number to divide all (1,2,..,100). (all consecutive numbers from 1 to 100). The answer should run in less than a minute.

I'm writing the solution in Java, and I'm facing two problems:

  1. How can I compute this is the solution itself is a number so huge that cannot be handled? I tried using "BigInteger" by I'm doing many additions and divisions and I don't know if this is increasing my time complexity.

  2. How can I calculate this in a less than a minute? The solution I though about so far haven't even stopped.

This is my Java code (using big integers):

public static boolean solved(int start, int end, BigInteger answer) {
    for (int i=start; i<=end; i++) {
        if (answer.mod(new BigInteger(valueOf(i))).compareTo(new BigInteger(valueOf(0)))==0) {
            return false;
        }
    }
    return true;
}

public static void main(String[] args) {
    BigInteger answer = new BigInteger("232792560");
    BigInteger y = new BigInteger("232792560");
    while(!solved(21,100, answer)) {
        answer = answer.add(y);
    }
    System.out.println(answer);
}

I take advantage of the fact that I know already the solution for (1,..,20).

Currently is simply not stopping.

I though I could improve it by changing the function solved to check for only values we care about.

For example:
100 = 25,50,100
99  = 33,99
98 = 49,98
97 = 97
96 = 24,32,48,96

And so on. But, this simple calculation of identifying the smallest group of number needed has become a problem itself to which I didn't look for / found a solution. Of course, the time complexity should stay under a minute either case.

Any other ideas?

Upvotes: 1

Views: 340

Answers (3)

user1196549
user1196549

Reputation:

As 100 is small, you can work this out by producing the prime factorization of all numbers from 2 to 100 and keep the largest exponent of each prime among all factorizations. In fact, trying divisions by 2, 3, 5 and 7 will be enough to check primality up to 100, and there are just 25 primes to consider. You can implement a simple sieve to find the primes and perform the factorizations.

After you found all exponents of the prime decomposition of the lcm, you can either leave this as the answer, or perform the multiplications explicitly.

Upvotes: 1

Dave
Dave

Reputation: 9085

Find all max prime powers in your range and take their product.

E.g. 1-10: 2^3, 3^2, 5^1, 7^1: product is 2520, which is the right answer (not 5250). You could find the primes via the sieve of Eratosthenes or just download them from a list of primes.

Upvotes: 3

user555045
user555045

Reputation: 64933

The first number that can be divided by all elements of some set (which is what you have there, despite the slightly different formulation) is also known as the Least Common Multiple of that set. LCM(a, b, c) = LCM(LCM(a, b), c) and so on, so in general, it can be computed by taking n - 1 pairwise LCMs where n is the number of items in the set. BigInteger does not have an lcm function, but the LCM can be computed via a * b / gcd(a, b) so in Java with BigInteger:

static BigInteger lcm(BigInteger a, BigInteger b) {
    return a.multiply(b).divide(a.gcd(b));
}

For 1 to 20, computing the LCM in that way indeed results in 232792560. It's easy to do it up to 100 too.

Upvotes: 4

Related Questions