What is the smallest number divisible by each of the numbers 1 to 20.

Project Euler Problem 5: 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?
Solution: Here we find the least number by finding the Least Common Multiple (LCM).

When prompted for an input enter 20. It will find smallest number divisible by each of the numbers 1 to 20.


Java implementation of above is as follows:


import java.io.*;
class LCM{
int a[];
int lcm = 1,range,p;
void findLCM(){
// flag if any no. in the array were divisible by p
boolean flag = true;
p=2;
while(p<range){
while(flag==true){
flag=false;
for(int i=0;i<range;i++){
if(a[i]%p == 0){
a[i] = a[i]/p;
flag = true;
}
}
System.out.println("Array after dividing:");
for(int i:a)
System.out.print(i+" ");
System.out.print("n");
if(flag==true){
lcm = p * lcm;
}
}
nextPrime(++p);
flag=true;
}
System.out.println("The LCM of 1 to "
+ range + " is " + lcm);
}
void nextPrime(int x){
//starting from current prime find next prime
for(int i=x;i<=range;i++)
/* check if no. being checked is divisible
by any no. less than or only itself */
for(int j=2;j<=i;j++){
//check if no. is divisible by any other no.
if(i%j==0){
/* check if the no. is divisible only by
itself or anyother no. if yes go to next no. */
if(i!=j)
break;
else {
p=i;
return;
}
}
}
}
void getRange(){
do{
System.out.println("Enter the range :");
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
try{
String str = br.readLine();
range = Integer.parseInt(str);
}
catch(IOException e){};
if(range<=20)
break;
else
System.out.println("Enter range less than or equal to 20");
}while(range>20);
a = new int [20];
for(int i=1;i<=range;i++)
a[i-1] = i;
}
}
class Test5{
public static void main(String [] args){
LCM l = new LCM();
l.getRange();
l.findLCM();
}
}

Happy coding. Enjoy !!!

Leave a Reply

Your email address will not be published. Required fields are marked *