Smallest Positive Number

2520 is the smallest number that can be divided by each of the numbers  from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

N = divide by prime factor of N => take maximum power number of each prime
2= 2^1 = 2
3 =2^1 * 3^1 = 6
4 =2^1, 3^1, 2^2 = 2^2 * 3^1 = 12
5 =2^1, 3^1, 2^2,5^1 = 2^2 * 3^1 5^1 = 60
6 =2^1, 3^1, 2^2,5^1,(2^1*3^1) = 2^2 * 3^1 5^1 = 60
7 =2^1, 3^1, 2^2,5^1,(2^1*3^1),7^1 = 2^2 * 3^1 5^1 *7^1= 420
8 =2^1, 3^1, 2^2,5^1,(2^1*3^1),7^1,2^3 = 2^3 * 3^1 5^1 *7^1= 840
9 =2^1, 3^1, 2^2,5^1,(2^1*3^1),7^1,2^3,3^2 = 2^3 * 3^2 5^1 *7^1= 2520
10 =2^1, 3^1, 2^2,5^1,(2^1*3^1),7^1,2^3,3^2,(5^2*2^1) = 2^3 * 3^2 5^1 *7^1= 2520
11 =2^1, 3^1, 2^2,5^1,(2^1*3^1),7^1,2^3,3^2,(5^2*2^1),11^1 = 2^3 * 3^2 5^1 *7^1 * 11^1= 27720

maximum power of prime = > floor(log(N) / log(prime_value)) => floor(log(20)/log(2)) = 4;

public class Problem5 {

    public void smallestPE() {
        long n = 1, sm=1, evalue=10;
        for (long i=2;i<=evalue;i++) {
            if (isPrime(i)) {
                if (i<= Math.sqrt(evalue)) {
                    double pf = Math.floor(Math.log(evalue)/Math.log(i));
                    sm*=Math.pow(i, pf);
                    System.out.println(i + " - " + pf + " - "+ Math.pow(i, pf));
                } else {
                    sm*=i;
                }
            }
        }
        System.out.println(sm);
    }

     public static void main(String[] args) {
        Problem5 p = new Problem5();
        p.smallestPE();
     }
}
Advertisement

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: