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?

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

---

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

You mean 292 years worst case?
That sounds creepy.

Quote:

---

Originally Posted by diamonddragon

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

Luckily, it's only 5.69 years? :)

Quote:

---

Originally Posted by diamonddragon

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.

Here we go again, but luckily not:

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

---

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.

Quote:

---

Originally Posted by 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.

---

I didn't check your code but your approach seems sensible enough; any problems with the implementation?

kind regards,

Jos

Quote:

---

Originally Posted by JosAH

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

Quote:

---

Originally Posted by diamonddragon

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

Here is another try, but no results.

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

---

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.

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

If try to check this number, it is slow:

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.

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

kind regards,

Jos

Quote:

---

Originally Posted by JosAH

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

Quote:

---

Originally Posted by diamonddragon

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

Quote:

---

Originally Posted by JosAH

That number is (most likely) a prime number.

kind regards,

Jos

---

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

Quote:

---

Originally Posted by diamonddragon

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

Quote:

---

Originally Posted by JosAH

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