# Thread: Big prime

1. Senior Member
Join Date
Jan 2012
Posts
210
Rep Power
5

## 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 09:42 PM.

2. ## 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

3. Senior Member
Join Date
Jan 2012
Posts
210
Rep Power
5

## Re: Big prime

You mean 292 years worst case?
That sounds creepy.

4. ## Re: Big prime

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

5. Senior Member
Join Date
Jan 2012
Posts
210
Rep Power
5

## Re: Big prime

Luckily, it's only 5.69 years? :)

6. ## Re: Big prime

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.

7. Senior Member
Join Date
Jan 2012
Posts
210
Rep Power
5

## 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 09:46 PM.

8. Senior Member
Join Date
Jan 2012
Posts
210
Rep Power
5

## 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. ## Re: Big prime

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

10. Senior Member
Join Date
Jan 2012
Posts
210
Rep Power
5

## Re: Big prime

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

11. ## Re: Big prime

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

12. Senior Member
Join Date
Jan 2012
Posts
210
Rep Power
5

## 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. ## 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

14. Senior Member
Join Date
Jan 2012
Posts
210
Rep Power
5

## 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 06:35 PM.

15. ## 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

16. Senior Member
Join Date
Jan 2012
Posts
210
Rep Power
5

## Re: Big prime

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

17. ## Re: Big prime

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

18. Senior Member
Join Date
Jan 2012
Posts
210
Rep Power
5

## Re: Big prime

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?

19. ## Re: Big prime

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

20. Senior Member
Join Date
Jan 2012
Posts
210
Rep Power
5

## Re: Big prime

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

Page 1 of 2 12 Last

#### Posting Permissions

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