Euler Project #5 Java- if statement does not execute

Question

I am writing a simple algorithm to solve Euler project #5, but one of the if statements does not work. In the method findNumber(), the if statement which changes the field variable 'divisibleNum' does not change the value of the variable and so every time I compile, the output is always 1.

I am trying to answer "What is the least positive number that is evenly divisible (divisible with no remainder) by all of the numbers from 1 to 25?"

public class Least
{
    private int divisibleNum;

    public Least()
    {
        divisibleNum = 1;
    }

    public static void main(String[] args)
    {
        Least lst = new Least();
        lst.findNumber();
        lst.printNumber();
    }

    public void findNumber()
    {       
        for(int i = 25; i<1; i--)
        {
            if(divisibleNum % i !=0)
                divisibleNum*= i;
        }


    }   


    public void printNumber()
    {
        System.out.println(divisibleNum);
    }
}

The output needs to be the smallest positive number that is divisible by 1-25(included), but every time it just prints 1.

Answer 1

So, this is actually pretty interesting. Not only is your algorithm flawed, but your code is too. Your algorithm will always generate a number that is divisible by all numbers through the given one, however only sometimes will it actually be the smallest one. First of all, the reason your current algorithm isn't working is because you're getting integer overflows (An integer is not a big enough variable to store that number). Instead, you should be using a Long for this purpose. Second of all, I took the liberty of writing you a new program that works 100% of the time to find the smallest number that is divisible through c. It works off of the fact that if you take every number through i, take the prime factorization of that number, and then go through all of the numbers and for each prime find the largest exponent of it that you get like this and then multiply all of those together, you get the smallest number which is divisible by all of those 1 through i.

import java.util.ArrayList;
import java.util.Arrays;
public class Least{
  private int c;
  private Long div;
  public Least(){
    c=25;
    div=1L;
  }
  public static void main(String[] args){
    Least lst = new Least();
    lst.smallestdiv();
    lst.printNumber();
  }
  public void printNumber(){
    System.out.println(c);
  }
  public int[] genPrime(int x){
    ArrayList<Integer> y = new ArrayList<Integer>();
    y.add(2);
    for(int i = 3; i < x; i++){
      boolean prime = true;
      int z = 0;
      while(z<y.size()&&y.get(z)<=sqrt(x)&&prime){
        if(isDiv(i,y.get(z))){
          prime=false;
        }
        z++;
      }
      if(prime){
        y.add(i);
      }
    }
    return IntegertoInt(y.toArray(new Integer[0]));
  }
  public boolean isDiv(int x,int y){return x%y==0;}
  public boolean isDivthrough(int x, int y){
    for(int i = 1;i<y;i++){
      if(!isDiv(x,i)){
        println(i);
        return false;
      }
    }
    return true;
  }
  public boolean isDiv(Long x,int y){return x%y==0;}
  public boolean isDivthrough(Long x, int y){
    for(int i = 1;i<y;i++){
      if(!isDiv(x,i)){
        println(i);
        return false;
      }
    }
    return true;
  }
  public int[] IntegertoInt(Integer[] x){
    int[] y = new int[x.length];
    for(int i = 0;i<x.length;i++){
      y[i]=x[i];
    }
    return y;
  }
  public int[] pFactor(int x,int[] y){
    int[] output = new int[y.length];
    int z = x;
    for(int i = 0;i<y.length;i++){
      while(isDiv(z,y[i])&&z>1){
        z=z/y[i];
        output[i]++;
      }
    }
    return output;
  }
  public void smallestdiv(){
    int[][] y = new int[c-1][];
    int[] primes = genPrime(c);
    for(int i = 2;i<=c;i++){
      y[i-2]=pFactor(i,primes);
    }
    for(int i = 0;i<primes.length;i++){
      int largest = -1;
      for(int k = 0;k<y.length;k++){
        if(y[k][i]>largest){
          largest=y[k][i];
        }
      }
      //println(largest,primes[i],(int)pow((float)primes[i],(float)largest));
      //println(output);
      div*=(int)pow((float)primes[i],(float)largest);
    }
  }
}