Results 1 to 8 of 8
  1. #1
    perito is offline Member
    Join Date
    Feb 2008
    Posts
    9
    Rep Power
    0

    Default Finding Largest Prime Factor

    Im trying to solve this problem
    The prime factors of 13195 are 5, 7, 13 and 29.

    What is the largest prime factor of the number 600851475143 ?
    My code is this:
    Java Code:
    import java.math.BigInteger;
    public class LargestPrimeFactor 
    {
    	public static boolean isPrime(BigInteger nbr)
    	{
    		boolean isNPrime=true;
    		BigInteger i = BigInteger.valueOf(2);
    		while (i.compareTo(nbr.divide(BigInteger.valueOf(2))) < 0)
    		{
    			if ((nbr.compareTo(i) != 0) && (nbr.mod(i).equals(BigInteger.ZERO)))
    			{
    				isNPrime = false;
    				break;
    			}
    			i=i.add(BigInteger.ONE);
    		}
    		if (isNPrime == true) return true;
    		else return false;
    	}
    	public static void main(String[] args) 
    	{
    		String strNum = "600851475143";
    		BigInteger num = BigInteger.valueOf(Long.parseLong(strNum));
    		BigInteger i = BigInteger.valueOf(Long.parseLong(strNum)-1);
    		BigInteger answer=BigInteger.ZERO;
    			while(i.compareTo(BigInteger.ONE)>0)
    			{
    				if (num.mod(i).equals(BigInteger.ZERO) && isPrime(i)==true)
    					{
    						answer=i;
    						break;
    					}
    				i=i.subtract(BigInteger.ONE);
    			}
    		System.out.println(answer);
    	}
    }
    I think this code will work but it will take FOREVER to work, I waited about an hour and got no results...
    anyone have any alternative code or any idea to get the right answer?

  2. #2
    hardwired's Avatar
    hardwired is offline Senior Member
    Join Date
    Jul 2007
    Posts
    1,576
    Rep Power
    8

    Default

    Java Code:
    import java.util.*;
    
    public class FindingPrimes {
    
        public static void main(String[] args) {
            System.out.printf("int max value  = %d%n" +
                              "long max value = %d%n" +
                              "given value    = %d%n",
                               Integer.MAX_VALUE, Long.MAX_VALUE,
                               600851475143L);
            System.out.println();
     
            // Generate and store the first 1000 prime numbers.
            boolean print = false;
            long[] primes = new long[1000];
            int count = 1;
            int index = 0;
            if(print)
                System.out.printf(" %5d, ", 2);
            primes[index++] = 2;
            for(int i = 1; i < 7920; i++) {
                for(int j = 2; j < i; j++) {
                    if(i % j == 0)
                        break;
                    if(j == i-1) {
                        primes[index++] = i;
                        if(print) {
                            System.out.printf(" %5d, ", i);
                            if(++count > 9) {
                                count = 0;
                                System.out.println();
                            }
                        }
                    }
                }
            }
    
            // Try to factor the given value with these primes.
            long value = 600851475143L;
            System.out.println("------ factor " + value + " ------");
            List<Long> factors = new ArrayList<Long>();
            for(int i = 0; i < primes.length; i++) {
                if(value % primes[i] == 0) {
                    System.out.printf("primes[%3d] = %4d%n",
                                       i, primes[i]);
                    factors.add(Long.valueOf(primes[i]));
                }
            }
            System.out.printf("%s%n", factors);
            long product = 1;
            for(int i = 0; i < factors.size(); i++) {
                product *= factors.get(i).longValue();
            }
            System.out.printf("product = %d%n", product);
        }
    }

  3. #3
    blackhole8746 is offline Member
    Join Date
    Mar 2008
    Posts
    2
    Rep Power
    0

    Default

    You seriously waited for an hour?!! I'm a beginner too but if you wait that long do two things:

    1- Check your output statements (And no I don't think you're stupid, we all make that one silly mistake)
    2- Check your while loops. If any while loop is infinite, or you forgot to increment one of the variables you're using in the loop body the program will not run.

  4. #4
    eNine is offline Member
    Join Date
    Aug 2007
    Location
    new yrok
    Posts
    3
    Rep Power
    0

    Default

    here are two methods from a class that I wrote...these might be helpful. you'd still need to do a little work...

    Java Code:
    public boolean isPrime(long p){
    	
    	long pAsALong = p;
    	long mySqrt = (long)Math.sqrt(pAsALong );
    	long divisor = 3;
    	if(p%2 == 2)
    		return true;
    	else if(p%2 == 0)
    		return false;
    	
    	while(divisor <= mySqrt )
    	{
    
    		if(pAsALong % divisor == 0)
    			return false;
    		
    		//only check odd numbers
    		divisor+=2;
    	}
    	
    return true;
    }
    
    //@return array list of longs that are prime factors
    public ArrayList<Long> listPrimes(long upToWhat){
    	ArrayList<Long> listOfPrimes = new ArrayList<Long>(20);
    	listOfPrimes.add(2L);//add two
    
    //only add odd numbers
    for(long  potentialPrime = 3;potentialPrime<= upToWhat; potentialPrime+=2){
    		if(isPrime(potentialPrime))
    			listOfPrimes.add(potentialPrime);
    	}
    	return listOfPrimes ;
    }

  5. #5
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    19

    Default

    Quote Originally Posted by perito View Post
    I waited about an hour and got no results...
    Amazing, why are you stay that much time for a result. If your application take an hour to give an output how can it become useful at all. Best thing to do in such a case is debug the code and see where you hang on. Specially on loops those things can be happen.

    Check hardwireds' code. All what you want is there.

  6. #6
    funnyboy's Avatar
    funnyboy is offline Member
    Join Date
    Nov 2010
    Posts
    10
    Rep Power
    0

    Exclamation

    You don't have to use a long integer!
    Just do that:
    long number = 600851475143L;
    The L at the end shows, that the variable is of type long.

  7. #7
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,000
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by perito View Post
    What is the largest prime factor of the number 600851475143 ?
    6857

    kind regards,

    Jos

    ps. the other prime factors are 1471, 839 and 71

  8. #8
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,316
    Blog Entries
    1
    Rep Power
    25

Similar Threads

  1. Computing prime numbers in Java
    By Java Tip in forum java.lang
    Replies: 0
    Last Post: 04-12-2008, 08:39 PM
  2. Prime numbers
    By gapper in forum New To Java
    Replies: 3
    Last Post: 02-07-2008, 10:09 AM
  3. Finding largest and smallest integer
    By mlhazan in forum New To Java
    Replies: 2
    Last Post: 01-12-2008, 10:30 PM
  4. ArrayList problem (finding largest no)
    By bugger in forum New To Java
    Replies: 3
    Last Post: 12-12-2007, 12:47 PM
  5. Finding largest no
    By bugger in forum New To Java
    Replies: 11
    Last Post: 11-29-2007, 12:49 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •