# Big prime

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• 02-01-2012, 03:18 AM
diamonddragon
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++;             }                                                }```
• 02-01-2012, 10:22 AM
JosAH
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
• 02-01-2012, 05:32 PM
diamonddragon
Re: Big prime
You mean 292 years worst case?
That sounds creepy.
• 02-01-2012, 05:44 PM
JosAH
Re: Big prime
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
• 02-01-2012, 07:07 PM
diamonddragon
Re: Big prime
Luckily, it's only 5.69 years? :)
• 02-01-2012, 07:13 PM
JosAH
Re: Big prime
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.
• 02-01-2012, 09:33 PM
diamonddragon
Re: Big prime
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;                }```
• 02-01-2012, 09:40 PM
diamonddragon
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.
• 02-01-2012, 10:08 PM
JosAH
Re: Big 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
• 02-01-2012, 10:25 PM
diamonddragon
Re: Big prime
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
• 02-01-2012, 10:32 PM
JosAH
Re: Big prime
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
• 02-02-2012, 04:40 PM
diamonddragon
Re: Big prime

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;     }```
• 02-02-2012, 05:09 PM
JosAH
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.

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
• 02-02-2012, 06:33 PM
diamonddragon
Re: Big prime
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.
• 02-02-2012, 06:42 PM
JosAH
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
• 02-02-2012, 06:45 PM
diamonddragon
Re: Big prime
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))
• 02-02-2012, 06:51 PM
JosAH
Re: Big prime
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
• 02-02-2012, 06:58 PM
diamonddragon
Re: Big prime
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?
• 02-02-2012, 07:18 PM
JosAH
Re: Big 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
• 02-02-2012, 07:22 PM
diamonddragon
Re: Big prime
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. :)
Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last