[zee5229]

I had all the logic worked out for my program and it worked fine until I realized that the number I need to test my program against was to large for an integer. I have tried switching all my variables to doubles and longs but I keep getting possible loss of precision error. If someone can figure out why and help me fix it I would be very apreciative.

/**
 * The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?
 */


public class zee_prob3
{

    public static void main (String[] zee)
    {

    	long array[]=getPrimesUpTo(600851475143L);
    	int length=array.length;

    	 for(double i=length-1; i>=0; i--)
    	 {
    	 	while(array[i]==0)
    	 		i--;

    	 	if(600851475143L%array[i]==0)
    	 		System.out.println(array[i]);

    	 }

    }

    public static long[] getPrimesUpTo(long x)//will find all primes up to x
    {
    	boolean prime=true;
    	long primes[]=new long[x];
    	int count=0;
    	for(int i=2; i<=x; i++)//master loop;interates 1 less than x
    	{
    		for(int div=2;div<i; div++ )//changes div to test if i is prime or not
    		{
    			if(i%div==0)
    			{
    				prime=false;
    				break;
    			}

    		}

    		if(prime==true)
    		{
    			primes[count]=i;
    			count++;
    		}

    		prime=true;

    	}

    		return primes;

    }//end of getPrimesUpTo
}

[pbl]

for(double i=length-1; i>=0; i--)

not a very good idea to use a double as array index anyhow

array[1.5] will be transalate to array[1] you just lost the .5

[Dogstopper]

The indexes to an array must always by integers. Thus long[] primes = new long[100000]; will work, while long[] primes = new long[100000L]; will not. Your array will still be capable of holding longs. It just only has to be an int in length (any longer than that and you are allocating a loooottttt of memory. You also, at one point were specifying a double as an index variable. Don't do that.

You cannot produce an array big enough (gigabytewise, you're talking 4.3GB of RAM) to hold an array of longs that is 600851475143 elements long (assuming a long is 64 bits). You are going to need a different approach. Is this an Euler problem? I think I have that lying around somewheere (though I used Python, not Java)

[pbl]

or use
http://www.dreaminco...snippet6272.htm

[Dogstopper]

But, there is a far more elegant solution to this problem programming-wise. I don't think he needs an array larger than maybe 2000 indexes of primes period. It's an inefficient algorithm.

[Dogstopper]

For prime factorization, here is what you want to do. Start with the lowest prime (2) and divide evenly until you cannot evenly divide anymore (use the % function). Then, increment to the next largest prime (3), and divide evenly until you cannot any longer, just as with 2. Then, increment and divide again. Now, all you must do is generate the NEXT prime number after one. You don't even need an array of primes. You simply increment one number until it is prime and divide.

An efficient Java algorithm for this problem should take 15 seconds to run, maximum, unless the number is particularly strange.

[pbl]

OK Doggy

http://www.dreaminco...-prime-numbers/

and for really large primes:

http://www.dreaminco...snippet4665.htm

[zee5229]

ok I figured out a solution. Yes it is a problem from project Euler. thanks for the help. I knew that the array was far larger than it needed to be but I couldn't figure out a mathematical way to know how large the array needed to be.

@Dogstopper that solution is so much easier than anything I had in mind.

[Dogstopper]

And if you use the sieve that pbl showed you to pull numbers from, it's fast. Just make sure you have enough in your sieve to proceed. This method takes some initial time to generate the sieve, but after that, it's MUCH faster to pull from it than having to regenerate the next highest every time. If your app takes too long, try using a sieve and adjusting the size to work for you.

Glad I could help.