patternjavaMinor
Find smallest multiple
Viewed 0 times
smallestmultiplefind
Problem
Algorithm which returns a number which is divisible by all the numbers from \$1\$ to \$n\$ without remainders.
Any better approach is there?
public static void smallestMultiple(long l){
int count = 1;
boolean flag = true;
while(true){
flag = true;
for(int i=1; i<=l; i++){
if( count % i != 0){
count++;
flag = false;
break;
}
}
if(flag){
break;
}
}
System.out.println(count);
}Any better approach is there?
Solution
Your approach works but it is hard to read: all the logic is concentrated in the single
Dedicated methods
Looking at the points above, we clearly need a method whose goal will be to say if one number
This is very clear. It loops over all the numbers between 2 (no need to start at 1, thanks to Konrad Morawski that pointed it out) and
Take note also of the spacing: adding a single space after the
You are using inconsistently
Also,
You need to clarify: what can be big enough to warrant using a
Namings
Main method
With the above dedicated method, we then have:
With such a method, one can clearly see what is happening: we are incrementing
Note that it also returns the result, instead of printing it: you should let whoever is calling printing the result, printing is not the task of that method.
The big advantage here: no need to
Faster methods
There are indeed faster methods:
smallestMultiple method, which is responsible for:- looping over the numbers
- determining if one is divisible by all the number between 1 and
l
- printing the result
Dedicated methods
Looking at the points above, we clearly need a method whose goal will be to say if one number
n is divisible by all the numbers between 1 and max.private static boolean isDivisible(long n, int max) {
for (int i = 2; i <= max; i++) {
if (n % i != 0) {
return false;
}
}
return true;
}This is very clear. It loops over all the numbers between 2 (no need to start at 1, thanks to Konrad Morawski that pointed it out) and
max. If one does not divide n, then it returns false. If none were found, it means all divide n, so we return true.Take note also of the spacing: adding a single space after the
for, before the curly braces, after each semi-colon in the loop condition, greatly contributes to clarity.long vs intYou are using inconsistently
long and int. smallestMultiple takes a long as parameter but the inner loop uses an int:// vvvv
public static void smallestMultiple(long l){
// ...
while(true){
// vvv
for(int i=1; i<=l; i++){Also,
count, which will be the result of the result is an int.You need to clarify: what can be big enough to warrant using a
long? Clearly, it is not the upper bound, which is 20 here. So l doesn't need to be a long. count, on the other hand, is expected to be big so we could use a long for this variable. In this case, it turns out that the result fits in an int, but if we increase a little the upper bound, it won't fit anymore.Namings
countis a bad name here. This is really the result of the calculation. It doesn't really count anything. It is merely an temporary variable that we increment. A genericresultwould be more explicit.
lis not very clear also. We could rename itupperormaxto signify that this is the upper bound for the numbers to consider.
Main method
With the above dedicated method, we then have:
public static long smallestMultiple(int max) {
long result = 1;
while (!isDivisible(result, max)) {
result++;
}
return result;
}With such a method, one can clearly see what is happening: we are incrementing
result while it is not divisible by all the numbers from 1 to max.Note that it also returns the result, instead of printing it: you should let whoever is calling printing the result, printing is not the task of that method.
The big advantage here: no need to
break any loop and no need for flag variables: having such flags is generally a code-smell indicating that the method is doing too much.Faster methods
There are indeed faster methods:
- taking the prime factorization of the numbers between 1 and the `max, as shown in this answer.
- using a property of the lowest common multiple, as shown in this answer.
Code Snippets
private static boolean isDivisible(long n, int max) {
for (int i = 2; i <= max; i++) {
if (n % i != 0) {
return false;
}
}
return true;
}// vvvv
public static void smallestMultiple(long l){
// ...
while(true){
// vvv
for(int i=1; i<=l; i++){public static long smallestMultiple(int max) {
long result = 1;
while (!isDivisible(result, max)) {
result++;
}
return result;
}Context
StackExchange Code Review Q#125362, answer score: 6
Revisions (0)
No revisions yet.