Project Euler #3 Java Solution Problem

class eulerThree {

    public static void main(String[] args) {

        double x = 600851475143d; 

        for (double z = 2; z*z <= x; z++) {

            if (x%z == 0) {

                开发者_开发百科System.out.println(z + "PRIME FACTOR");

            }

        }

    }

}

and the output is:

71.0
839.0
1471.0
6857.0
59569.0
104441.0
486847.0

So, I assume 486847 is the largest prime factor of x, but project euler says otherwise. I don't see a problem in my code or my math, so I'm pretty confused. Can you see anything I can't?

Firstly, you have to use an accurate arithmetic means. Others have suggested using BigInteger. You can do this. To me, it feels a bit like cheating (this will be more important for later problems that deal with much larger integers) so the more fun way (imho) is to write the necessary arbitrary precision operations yourself.

Second, 600851475143 is small enough to be done accurate with a long, which will be much faster.

Third, your loop isn't correctly checking for prime factors. You're just checking odd numbers. This is a barebones (incomplete) solution:

long num = 600851475143L;
List<Long> factors = new ArrayList<Long>(); // or use a Set
if (num & 1 == 0) {
  factors.add(2L);
}
for (long i=3; i*i<=num; i+=2) {
  // first check i is prime
  // if i is prime check if it is a factor of num
}

Checking if something is prime has differing levels of implementation. The most naive:

public boolean isPrime(long num) {
  for (long i=2; i<=num; i++) {
    if (num % i == 0) {
      return false;
    }
  }
  return true;
}

Of course that does all sorts of unnecessary checking. As you've already determined you only need to check numbers up to sqrt(n) and you can eliminate even numbers (other than 2):

public boolean isPrime(long num) {
  if (num & 1 == 0) {
    return false; // checks divisibility by 2
  }
  for (long i=3; i*i<=num; i+=2) {
    if (num % i == 0) {
      return false;
    }
  }
  return true;
}

But you can do better than this as well. Another optimization is that you only need to check a number by prime numbers within that range. The prime factors of 63 are 3 and 7. If a number isn't divisible by 3 or 7 then it by definition won't be divisible by 63.

So what you want to do is build up probably a Set<Long> or prime numbers until the square is equal to or higher than your target number. Then just check this series of numbers for divisibility into the target.

double is inherently inaccurate for large values and should never be used for these type of number operations. The right class to use is BigInteger, which allows arbitrarily large integral values to be represented precisely. See this wikipedia article for a description on what floating point data types are and are not.

First, use BigInteger or long rather than double. Double isn't exact, and as you get to later problems, it won't be correct at all.

Second, what you're printing is factors, not prime factors.

This will work in your case:

for (double z = 2; z <= x; z++) {
        if (x%z == 0) {
                    while( x%z == 0)
                        x = x/z
                System.out.println(z + "PRIME FACTOR");
        }
}

Also, Project Euler gives you sample input and output. Use that, since your code doesn't output values that match the example they give in the problem.

Two things:

1. Don't use double, the bigger the numbers the less precision it has. Instead you can use BigInteger to store arbitrarily large integers, or in this case a simple long will suffice.

2. You need to divide by the prime factor after you find it, otherwise you'll find all factors not just prime factors. Something like this:

   if (x % z == 0) {
       System.out.println(z + "PRIME FACTOR");
       x /= z;
       z -= 1; // Might be present multiple times, try it again
   }
   

public class Prime {
    public static void main(String[] args) {
        double out = 0;
        double m = 600851475143d;
        for (double n = 3; n < m; n += 2) {
            while (m % n == 0) {
                out = n;
                m = m / n;
            }
        }
        System.out.println("" + ((m == 1)?out:m));
    }
}

See the program. And you'll understand the algorithm. This is very easy and very fast. And return the correct answer 6857.

          import java.util.Scanner;

          class Primefactor
                   {
                          public static void main(String args[])
                              {
                       Scanner get=new Scanner(System.in);
                       System.out.println("Enter a number");
                       long number=get.nextLong();
                       int count=0;
                       long input=number;
                             for(long i=number;i>=1;number--)
                                 {
                    for(long j=number;j>=1;j--)
                     {
                       if(i%j==0)
                         {
                            count++;
                         }
                      if(count==2)
                        {
                           if(input%j==0)
                              {
                                 System.out.println(j);
                               }
                           }
                     }
                  }
            }
          }

This is to see largest primefactor of any number within the datatype limit.

public static void largestPrimeNo(long lim)
{
long newNum = lim;
long largestFact = 0;

int counter = 2;
while( counter * counter <= newNum )
{
if(newNum % counter == 0)
{
    newNum = newNum / counter;
    largestFact = counter;
}else{
counter++;
}
}
if(newNum > largestFact)
{
largestFact=newNum;
}
System.out.println(largestFact);
}
}

as Prime no is work on the principle that Any integer greater than 1 is either a prime number, or can be written as a unique product of prime numbers.So we can easily use above program.In this program we divide the long no,and find its prime factor

package findlaragestprimefactor;

public class FindLaragestPrimeFactor{

    boolean isPrime(long number) {
        for (long divider = 2; divider <= number / 2; divider++) {
            if (number % divider == 0) {
                return false;
            }

        }
        return true;
    }

    void calculateLargestPrimeFactor() {
        long largestPrimeFactor = 0;
        long x = 600851475143L;
        for(long factor = 3 ; factor <= x/2 ; factor = factor + 2){
            if(x%factor==0 & factor>largestPrimeFactor & isPrime(factor)){
                largestPrimeFactor = factor;
            }
        }
        System.out.println(largestPrimeFactor);
    }







    public static void main(String[] args) {

        MyProject m = new MyProject();
        m.calculateLargestPrimeFactor();
    }
}

long tNum=600851475143L;

ArrayList<Integer> primeNum=new ArrayList();
System.out.println(10086647/1471);
for(int i=2;i<=tNum;i++) {
    if(tNum%i==0) {
        primeNum.add(i);
        tNum=tNum/i;    
    }
}

System.out.println(primeNum);