CODEWITHSUNDEEP
java
manish
manish

Reputation: 956

Project Euler Program 5 takes too much time in Java

The question is: What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

I write the following program which gives the correct output, but it took very long to execute.

What can I do to fasten my program?

    public class ep5 {

    public static void main(String[] args) {

    int n=100,k=0;
    boolean check=true;
    while(check)
    {   
        k=0;
        n++;

        for (int i=2;i<21;i++)
            if(n%i!=0)
                k=1;

        if (k!=1)
            check=false;
    }
    System.out.println(n);
}
}

Upvotes: 3

Views: 173

Answers (2)

user1928596
user1928596

Reputation: 1753

one can easily see that the smallest number that divide all numbers from 1 to 20 is the product of all (greatest power (of prime numbers smaller than 20) smaller than 20), you can manage to find those numbers and calculate there greater power that is smaller than 20 and multiply theses numbers

what I mathematically do is decompose all these numbers on prime numbers product, and take the biggest power for each prime number.

Upvotes: -1

the_prole
the_prole

Reputation: 8945

A start would be not to divide by multiples of two. 

for (int i=3;i<21;i++){ //begin at i = 3
     i = i + 1; //count by twos
     if(n%2 !=0 && n%i!=0) //add a condition
          k=1;
}

I imagine you could extend this logic to multiples of 3, 5, 7, 11, 13, 17, and 19, all the prime numbers between 1 and 21. Get rid of the for loop and use an else if statements to speed up the process. 

if      (n%2 !=0)
     k = 1;
else if (n%3 != 0)
     k = 1;
else if (n%5 != 0)
     k = 1;
else if (n%7 != 0)
     k = 1;
else if (n%11 != 0)
     k = 1;
else if (n%13 != 0)
     k = 1;
else if (n%17 != 0)
     k = 1;
else if (n%19 != 0)
     k = 1;
else 
     check = false;

Hope that helps.

Upvotes: 1

Related Questions