Divides all Numbers to a Million

Computer Science Level 4

Let $n$ be the smallest positive integer divisible by all positive integers up to $1,000,000 = 10^6$ , inclusive. Let $m$ be $n$ divided by the largest power of $10$ it can evenly be divided by. What are the last 3 digits of $m$ ?

Details and Assumptions

The smallest positive integer divisible by all positive integers up to $30$ is $2329089562800$ . In this case, you would divide this number by the largest power of $10$ it can evenly be divided by ( $100$ ), and give the last three digits of the result, or $628$ .

The answer is 608.

3 solutions

Logan Dymond
Jan 5, 2014

My python solution:

from math import sqrt
from math import ceil
import time

start = time.time()

n=10**6
primes = [True]*(n+1)
primes[0]=False
primes[1]=False
for i in range(2,int(ceil(sqrt(n+1)))):
    if primes[i]==True:
        for j in range(i**2,n+1,i):
            primes[j]=False

zeros = 0
while 5**(zeros+1) <= n:
    zeros+=1

huge = 1
for i in range(n+1):
    if primes[i] == True:
        k=0
        while i**(k+1) <= n:
            k+=1
        else:
            huge = (huge*i**k) % 10**(zeros+3)

end = time.time()

print huge/10**zeros

print end-start

First, I generate a list of prime numbers (primes) up to $1,000,000$ using the Sieve of Eratosthenes. I store them as Booleans to conserve memory; Trues are primes and Falses are not. Next, I calculate the greatest power of $10$ that will divide $n$ (zeros). This is directly dependent on the greatest power of $5$ that divides $n$ , which is the greatest power of $5$ less than the bound of $1,000,000$ . Finally, I calculate $n$ (huge) by starting with $1$ and multiplying the largest prime power for each prime up to $1,000,000$ . I mod out $10^{zeros+3}$ however, because we only care about the last three digits before the long string of zeros at the end. All the time stuff is just the method I use to time my script (which ran in about 1.23 seconds).

Nice solution!

Thaddeus Abiy - 7 years, 5 months ago

What is wrong with this program? It gave me 125 as result.

public class brilliant201410120821{
    private static final int N = 1000000;
    public static void main(String[] args){
        int m = 1;
        for(int i=2;i<=N;i++){
            if(!isPrime(i)) continue;
            m *= largest(i);
            while(m%10==0) m/=10;
            m %= 1000;
        }
        System.out.println(m);
    }
    private static boolean isPrime(int n){
        for(int i=2;i<=Math.sqrt(n);i++){
            if(n%i==0) return false;
        }
        return true;
    }
    private static int largest(int p){
        int a = 1;
        while(a<=N/p){
            a *= p;
        }
        System.out.println(p+":"+a);
        return a;
    }
}

Kenny Lau - 6 years, 8 months ago

David Holcer
Apr 3, 2015

from math import *
def primes(n):
    """ Returns  a list of primes < n """
    sieve = [True] * n
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i]=[False]*((n-i*i-1)/(2*i)+1)
    global array
    array= [2] + [i for i in xrange(3,n,2) if sieve[i]]

primes(10**6)
product=1
for i in array:
    product*=i**int(floor((log(10**6)/log(i))))
while True:
    if '0' in str(product)[-1]:
        product/=10
    else:
        break
print str(product)[-3:]

For primes I used this and the rest was me. Probably better way of stripping ending zeroes.

Bill Bell
Dec 17, 2014

I did it this way—and had plenty of time for a nap.

Divides all Numbers to a Million

The answer is 608.

3 solutions

0 pending reports