Page 1 of 2 12 LastLast
Results 1 to 20 of 26
Like Tree2Likes

Thread: Big prime

  1. #1
    diamonddragon is offline Senior Member
    Join Date
    Jan 2012
    Posts
    210
    Rep Power
    3

    Default Big prime

    Is my computer slow or I'm not doint right, but I'm just getting nothing while runing this code that suppose to find 5 prime numbers larger than Long.MAX_VALUE?

    Java Code:
            //Prime numbers larger than Long.MAX_VALUE
            long min = Long.MAX_VALUE; //minimum larg number
            int count = 0; //count prime numbers
            BigInteger big = new BigInteger(String.valueOf(min));        
            
            while (count < 5) {
                BigInteger bigCount = BigInteger.ONE; //increment for big prime number
                big = big.add(BigInteger.ONE);
                boolean prime = true;
    
                while(bigCount.compareTo(big.divide(BigInteger.valueOf(2))) < 0) {
                    bigCount = bigCount.add(BigInteger.ONE);//start 2                
                    if (big.mod(bigCount).compareTo(BigInteger.ZERO) == 0) {
                        prime = false;
                        break;
                    }                    
                }
    
                if (prime) {
                    System.out.println("Big prime> " + big.toString());
                    count++;
                }                                        
            }
    Last edited by diamonddragon; 02-01-2012 at 08:42 PM.

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

    Default Re: Big prime

    Long.MAX_VALUE is 0x7fffffffffffffffL (9223372036854775807L in decimal); suppose your loop can do 1E9 iterations per second (it can't); your loop takes 9223372036854775807/1E9 == 9223372036 seconds worst case ... (do your math ;-)

    kind regards,

    Jos
    tnrh1 likes this.
    cenosillicaphobia: the fear for an empty beer glass

  3. #3
    diamonddragon is offline Senior Member
    Join Date
    Jan 2012
    Posts
    210
    Rep Power
    3

    Default Re: Big prime

    You mean 292 years worst case?
    That sounds creepy.

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

    Default Re: Big prime

    Quote Originally Posted by diamonddragon View Post
    You mean 292 years worst case?
    That sounds creepy.
    Yes it does; luckily you don't have to do that many calculations; i.e. if you want to find a prime factor of n, you only have to check numbers p, where p*p <= n. If you check for potential divisors 2 and 3, you only have to check for potential factors p == 6*m-1 and p == 6*m+1 afterwards; in total you only have to check sqrt(n)/3 numbers instead of n numbers.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  5. #5
    diamonddragon is offline Senior Member
    Join Date
    Jan 2012
    Posts
    210
    Rep Power
    3

    Default Re: Big prime

    Luckily, it's only 5.69 years? :)

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

    Default Re: Big prime

    Quote Originally Posted by diamonddragon View Post
    Luckily, it's only 5.69 years? :)
    Nope, just a couple of seconds; I just calculated the prime factors for Long.MAX_VALUE in my own (cute) language:

    649657L*92737L*337L*127L*73L*7L*7L

    kind regards,

    Jos

    ps. Try it: check if 2, 3, and the factors 6*n+-1 are prime factors for a number n, only check numbers p such that p*p <= n.
    cenosillicaphobia: the fear for an empty beer glass

  7. #7
    diamonddragon is offline Senior Member
    Join Date
    Jan 2012
    Posts
    210
    Rep Power
    3

    Default Re: Big prime

    Here we go again, but luckily not:

    Java Code:
         public static void main(String[] args) {      
            //Prime numbers larger than Long.MAX_VALUE
            long min = Long.MAX_VALUE;        
            BigInteger big = new BigInteger(String.valueOf(min));            
            int count = 0;
            
            while (count < 5) {
    
                big = big.add(BigInteger.ONE);//big number >  Long.MAX_VALUE;          
                BigInteger bigPrimeCheck = BigInteger.valueOf(2);//prime numbers less than sqrt(n)            
    
                boolean prime = true;
    
                while (bigPrimeCheck.pow(2).compareTo(big) <= 0) {//if bigPrimeCheck < sqrt(n)                                 
                    if (isPrime(bigPrimeCheck) && big.mod(bigPrimeCheck).compareTo(BigInteger.ZERO) == 0) {
                        prime = false;
                        break;
                    }
                    bigPrimeCheck = bigPrimeCheck.add(BigInteger.ONE);
                }
    
                if (prime) {
                    System.out.println("Big prime> " + big.toString());
                    count++;
                }
            }
         }
         
        public static boolean isPrime(BigInteger n) {
            BigInteger i = BigInteger.valueOf(2);
            for (; i.compareTo(n.divide(BigInteger.valueOf(2))) < 0; i = i.add(BigInteger.ONE)) {
                if (n.mod(i).compareTo(BigInteger.ZERO) == 0) {                
                    return false;
                }
            }     
            return true;            
        }
    Last edited by diamonddragon; 02-01-2012 at 08:46 PM.

  8. #8
    diamonddragon is offline Senior Member
    Join Date
    Jan 2012
    Posts
    210
    Rep Power
    3

    Default Re: Big prime

    I used this approach:
    To determine whether n is prime check whether any of the prime numbers less than or equal to sqrt(n) can divide n evenly.
    If not, n is prime.

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

    Default Re: Big prime

    Quote Originally Posted by diamonddragon View Post
    I used this approach:
    To determine whether n is prime check whether any of the prime numbers less than or equal to sqrt(n) can divide n evenly.
    If not, n is prime.
    I didn't check your code but your approach seems sensible enough; any problems with the implementation?

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  10. #10
    diamonddragon is offline Senior Member
    Join Date
    Jan 2012
    Posts
    210
    Rep Power
    3

    Default Re: Big prime

    Quote Originally Posted by JosAH View Post
    I didn't check your code but your approach seems sensible enough; any problems with the implementation?

    kind regards,

    Jos
    No problem, just can't get results since temperture of processor becomes high and computer becomes slow.
    Will try Your approach later, but I don't understand what this means:

    factors 6*n+-1

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

    Default Re: Big prime

    Quote Originally Posted by diamonddragon View Post
    No problem, just can't get results since temperture of processor becomes high and computer becomes slow.
    Will try Your approach later, but I don't understand what this means:

    factors 6*n+-1
    Sorry about that; it means multiples of six plus or minus one; i.e. 5, 7, 11, 13, 17, 19, 23, 25 etc.

    kind regards,

    Jos
    diamonddragon likes this.
    cenosillicaphobia: the fear for an empty beer glass

  12. #12
    diamonddragon is offline Senior Member
    Join Date
    Jan 2012
    Posts
    210
    Rep Power
    3

    Default Re: Big prime

    Here is another try, but no results.

    Java Code:
             public static void main(String[] args) {      
            //Prime numbers larger than Long.MAX_VALUE
            long min = Long.MAX_VALUE;        
            BigInteger big = BigInteger.valueOf(min);            
            int count = 0;                 
            
            while (count < 5) {                               
    
                if (primeFactors(big)) {
                    System.out.println("Big prime> " + big.toString());
                    count++;
                }              
                big = big.add(BigInteger.ONE);
            }
         }          
         
        
         
        public static boolean primeFactors(BigInteger n) {   
            BigInteger i = BigInteger.valueOf(2);
            BigInteger s = BigInteger.valueOf(6);  
            BigInteger o = BigInteger.ONE;
            BigInteger z = BigInteger.ZERO;
            BigInteger number = n;
                
            //check for numbers 2 and 3
            if (number.mod(BigInteger.valueOf(2)).compareTo(z) == 0 || 
                    number.mod(BigInteger.valueOf(3)).compareTo(z) == 0)
                    return false;
            
            for (; n.compareTo(o) != 0; i = i.add(o)) {//find factors of number                 
                
                while (n.mod(i).compareTo(z) == 0) {                         
                    //if factor multiple 6
                    if (i.add(o).mod(s).compareTo(z) == 0 ^ i.subtract(o).mod(s).compareTo(z) == 0)
                        if (number.mod(i).compareTo(z) == 0) {
                        return false;
                    }                                
                    System.out.println(i);
                    n = n.divide(i);
                }
                if (i.pow(2).compareTo(number) > 0) {
                    return true;
                }
            }
            return true;
        }

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

    Default Re: Big prime

    I copied (and adjusted a bit) the following code from the runtime part of my own little language; it finds all prime factors of a number; do with it what you want.

    Java Code:
    import java.math.BigInteger;
    import java.util.ArrayList;
    import java.util.List;
    
    public class T{
    	
    	private static int[] inc= { 0, 4, 1, 2, 0, 2, 0 };
    	
    	static public List<BigInteger> factors(BigInteger n) {
    		
    		List<BigInteger> l= new ArrayList<BigInteger>();
    		
    		if (n.compareTo(BigInteger.valueOf(4L)) < 0) {
    			if (n.compareTo(BigInteger.ONE) > 0)
    				l.add(n);
    			return l;
    		}
    		
    		int ii= 2;
    
    		for (BigInteger i= BigInteger.valueOf(ii); i.multiply(i).compareTo(n) <= 0; )
    			
    			if (n.mod(i).compareTo(BigInteger.ZERO) == 0) {
    				l.add(i);
    				n= n.divide(i);
    			}
    			else {
    				int iinc= inc[ii];
    				ii= (ii+iinc)%6;
    				i= i.add(BigInteger.valueOf(iinc));				
    			}
    		
    		l.add(n);
    		
    		return l;
    	}
    	public static void main (String[] args)    {
    		
    		System.out.println(factors(BigInteger.valueOf(Long.MAX_VALUE)));
    	}
    }
    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  14. #14
    diamonddragon is offline Senior Member
    Join Date
    Jan 2012
    Posts
    210
    Rep Power
    3

    Default Re: Big prime

    If try to check this number, it is slow:

    Java Code:
        public static void main (String[] args)    {
             
            BigInteger big = BigInteger.valueOf(Long.MAX_VALUE).add(BigInteger.valueOf(30L));
            System.out.println(factors(big));
        }
    And finding 5 such numbers is what I'm not gona achieve with this approach.
    Last edited by diamonddragon; 02-02-2012 at 05:35 PM.

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

    Default Re: Big prime

    Did you check my approach? It finds all factors of Long.MAX_VALUE in just a bit of time ...

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  16. #16
    diamonddragon is offline Senior Member
    Join Date
    Jan 2012
    Posts
    210
    Rep Power
    3

    Default Re: Big prime

    Quote Originally Posted by JosAH View Post
    Did you check my approach? It finds all factors of Long.MAX_VALUE in just a bit of time ...

    kind regards,

    Jos
    Of Long.MAX_VALUE, but, try to check number 9223372036854775837

    or, in Java code: BigInteger.valueOf(Long.MAX_VALUE).add(BigInteger. valueOf(30L))

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

    Default Re: Big prime

    Quote Originally Posted by diamonddragon View Post
    Of Long.MAX_VALUE, but, try to check number 9223372036854775837

    or, in Java code: BigInteger.valueOf(Long.MAX_VALUE).add(BigInteger. valueOf(30L))
    That number is (most likely) a prime number.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  18. #18
    diamonddragon is offline Senior Member
    Join Date
    Jan 2012
    Posts
    210
    Rep Power
    3

    Default Re: Big prime

    Quote Originally Posted by JosAH View Post
    That number is (most likely) a prime number.

    kind regards,

    Jos
    Most likely, but how should I know it is prime?

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

    Default Re: Big prime

    Quote Originally Posted by diamonddragon View Post
    Most likely, but how should I know it is prime?
    Either wait (by using my method) and be sure or use the BigInteger.isProbablePrime( ... ) method to be almost sure.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  20. #20
    diamonddragon is offline Senior Member
    Join Date
    Jan 2012
    Posts
    210
    Rep Power
    3

    Default Re: Big prime

    Quote Originally Posted by JosAH View Post
    Either wait (by using my method) and be sure or use the BigInteger.isProbablePrime( ... ) method to be almost sure.

    kind regards,

    Jos
    So at the and of the story, if man want to be sure, have to wait, otherwise man is not sure. :)

Page 1 of 2 12 LastLast

Similar Threads

  1. Palindromic Prime?
    By soccergirl67 in forum New To Java
    Replies: 5
    Last Post: 12-01-2011, 09:48 AM
  2. Prime Factorization
    By skaterboy987 in forum New To Java
    Replies: 7
    Last Post: 10-27-2011, 01:18 AM
  3. Prime Number - System print all the prime numbers ...
    By pinkdreammsss in forum New To Java
    Replies: 20
    Last Post: 04-26-2009, 01:50 AM
  4. Prime numbers
    By tercius in forum New To Java
    Replies: 3
    Last Post: 05-04-2008, 06:05 AM
  5. Prime numbers
    By gapper in forum New To Java
    Replies: 3
    Last Post: 02-07-2008, 10:09 AM

Posting Permissions

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