[thatsnotmyname]

Hey all,

I'm having issues with Euler Problem 3 (http://projecteuler.net/index.php?section=problems&id=3).

My issue with my code is that the compiler says "running user program" and then never stops, so I guess it must be an infinite loop.

I know that a lot my code/technique to solving this problem is probably wrong and that I could just look up the right code/approach on the internet. However, I'm just trying to find a way to solve the problem on my own and then after that looking at the better code.

So here's what I've come up with so far... I think the issue is an infinite loop, but I don't see where/how that's occurring...

public class Euler3{

	public static void main(String[] args){
		long x = 200;
		long y = x-1;
		PrimeFactor myPrime = new PrimeFactor();
		
		while(y > 1){
			
			myPrime.divide(x, y);
			
			if(myPrime.divide(x, y) >= 1){
			
			System.out.println(myPrime.getDivisor() + "^" + myPrime.getCount());
			}//if
			
			y--;
			
			}//while
				
	}//main
}//class

public class PrimeFactor{

	public long divisor = 2;
	public long dividend = 0;
	public long quotient = 0;
	public long count = 0;

	public long divide(long x, long y) {
	
		dividend = x;
		divisor = y;
		
		while(dividend%divisor==0){
			
				quotient = dividend / divisor;
				divisor = quotient;
				count++;
				
				}//while
				return count;
			}//divide
		
	public long getDivisor(){
	
		return divisor;
		
		}//getDivisor
		
	public long getCount(){
	
		return count;
		
		}//getCount
		
}

Also, everything is a long right now, because eventually I want to solve it for the really big number. I'm just seeing if what I did works with small numbers right now...

I really appreciate any help!

This post has been edited by JackOfAllTrades: 07 August 2010 - 10:53 AM
Reason for edit:: Switched quote tags to code tags

[krizjaz]

Next time, please don't use quote tags. Use "code tags" instead in showing your code.

[JackOfAllTrades]

Please use CODE tags, not QUOTE tags, when posting code.

[thatsnotmyname]

krizjaz, on 07 August 2010 - 09:53 AM, said:

Next time, please don't use quote tags. Use "code tags" instead in showing your code.

Definitely. I just missed the code snippet option at the top next to quote. Sorry.

[krizjaz]

In your code, when your while loop's condition:

while(dividend%divisor==0){
}

becomes true, the loop would never end.

I think, you should organize your code well.
Here's another way, create a loop which starts at 2 (because we don't need to start at 0 or 1) and would end at your max number (which is 200).

Make a method that would tell if the number is a prime number. Like for example:

public static boolean isPrimeNumber(long num){
	int num2 = 0;
	for(long i = 2; i <= max; i++){
		if(max != i){
			if((num % i) == 0)
				num2++;
		}
	}
	if(num2 == 0) return true;
	else return false;
}

If num2 > 0, then the number is not a prime number.

So, what you should do is to check all the numbers beginning from 2 to the max number if there are prime numbers.

Then check if when you divide the max number (which is, in your code, 200) with the prime number, is equal to 0:

if(max % primenum == 0){
}

Then if the condition is true, you can now divide:

if(max % primenum == 0){
	max /= primenum;
}

And to get the largest prime factor, the last prime number, that when max % primenum, has no remainder will be your largest prime factor.

if(max % primenum == 0){
	max /= primenum;
	largest = primenum;
}

This is my code to give you an idea:

public class Euler3{

	public static void main(String[] args){
		java.util.Scanner s = new java.util.Scanner(System.in);
		long store = 0, max = s.nextLong(), largest = 0;
		for(long i = 2; i <= max; i++){
			if(isPrimeNumber(i)){
				if(max % i == 0){
					max /= i;
					largest = i;
				}
			}
		}
		System.out.println(largest);
	}

	public static boolean isPrimeNumber(long num){
		int num2 = 0;
		for(long i = 2; i <= num; i++){
			if(num != i){
				if((num % i) == 0)
					num2++;
			}
		}
		if(num2 == 0) return true;
		else return false;
	}
}

Or use ternary operators to lessen the code:

public class Euler3{

	public static void main(String[] args){
		java.util.Scanner s = new java.util.Scanner(System.in);
		long store = 0, max = s.nextLong(), largest = 0;
		for(long i = 2; i <= max; i++){
			max = isPrimeNumber(i) && max % i == 0 ? max / i + i - (largest = i) : max;
		}

		System.out.println("Largest: " + largest);
	}

	public static boolean isPrimeNumber(long num){
		int num2 = 0;
		for(long i = 2; i <= num; i++)
			num = num != i ? (num % i) == 0 ? num2++ : num : num;
		return num2 == 0 ? true : false;
	}
}

This post has been edited by krizjaz: 07 August 2010 - 02:36 PM

[pbl]

This is a useless statement

            myPrime.divide(x, y);  

Why invoking a method if you do not use the result returned by it ?