Big prime

[diamonddragon]

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?

        //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++;
            }                                        
        }

[JosAH]

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

[diamonddragon]

You mean 292 years worst case?
That sounds creepy.

[JosAH]

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

[diamonddragon]

Luckily, it's only 5.69 years? :)

[JosAH]

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.

[diamonddragon]

Here we go again, but luckily not:

     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;            
    }

[diamonddragon]

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.

[JosAH]

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

[diamonddragon]

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

[JosAH]

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]

Here is another try, but no results.

         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;
    }

[JosAH]

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.

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

[diamonddragon]

If try to check this number, it is slow:

    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.

[JosAH]

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

kind regards,

Jos

[diamonddragon]

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))

[JosAH]

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

[diamonddragon]

That number is (most likely) a prime number.

kind regards,

Jos

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

[JosAH]

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

[diamonddragon]

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. :)