Results 1 to 20 of 26
 02012012, 02:18 AM #1Senior Member
 Join Date
 Jan 2012
 Posts
 210
 Rep Power
 3
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; 02012012 at 08:42 PM.
 02012012, 09:22 AM #2
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,433
 Blog Entries
 7
 Rep Power
 20
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,
Joscenosillicaphobia: the fear for an empty beer glass
 02012012, 04:32 PM #3Senior Member
 Join Date
 Jan 2012
 Posts
 210
 Rep Power
 3
Re: Big prime
You mean 292 years worst case?
That sounds creepy.
 02012012, 04:44 PM #4
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,433
 Blog Entries
 7
 Rep Power
 20
Re: Big prime
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*m1 and p == 6*m+1 afterwards; in total you only have to check sqrt(n)/3 numbers instead of n numbers.
kind regards,
Joscenosillicaphobia: the fear for an empty beer glass
 02012012, 06:07 PM #5Senior Member
 Join Date
 Jan 2012
 Posts
 210
 Rep Power
 3
Re: Big prime
Luckily, it's only 5.69 years? :)
 02012012, 06:13 PM #6
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,433
 Blog Entries
 7
 Rep Power
 20
Re: Big prime
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
 02012012, 08:33 PM #7Senior Member
 Join Date
 Jan 2012
 Posts
 210
 Rep Power
 3
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; 02012012 at 08:46 PM.
 02012012, 08:40 PM #8Senior Member
 Join Date
 Jan 2012
 Posts
 210
 Rep Power
 3
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.
 02012012, 09:08 PM #9
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,433
 Blog Entries
 7
 Rep Power
 20
 02012012, 09:25 PM #10Senior Member
 Join Date
 Jan 2012
 Posts
 210
 Rep Power
 3
 02012012, 09:32 PM #11
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,433
 Blog Entries
 7
 Rep Power
 20
 02022012, 03:40 PM #12Senior Member
 Join Date
 Jan 2012
 Posts
 210
 Rep Power
 3
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; }
 02022012, 04:09 PM #13
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,433
 Blog Entries
 7
 Rep Power
 20
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))); } }
Joscenosillicaphobia: the fear for an empty beer glass
 02022012, 05:33 PM #14Senior Member
 Join Date
 Jan 2012
 Posts
 210
 Rep Power
 3
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)); }
Last edited by diamonddragon; 02022012 at 05:35 PM.
 02022012, 05:42 PM #15
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,433
 Blog Entries
 7
 Rep Power
 20
Re: Big prime
Did you check my approach? It finds all factors of Long.MAX_VALUE in just a bit of time ...
kind regards,
Joscenosillicaphobia: the fear for an empty beer glass
 02022012, 05:45 PM #16Senior Member
 Join Date
 Jan 2012
 Posts
 210
 Rep Power
 3
 02022012, 05:51 PM #17
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,433
 Blog Entries
 7
 Rep Power
 20
 02022012, 05:58 PM #18Senior Member
 Join Date
 Jan 2012
 Posts
 210
 Rep Power
 3
 02022012, 06:18 PM #19
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,433
 Blog Entries
 7
 Rep Power
 20
 02022012, 06:22 PM #20Senior Member
 Join Date
 Jan 2012
 Posts
 210
 Rep Power
 3
Similar Threads

Palindromic Prime?
By soccergirl67 in forum New To JavaReplies: 5Last Post: 12012011, 09:48 AM 
Prime Factorization
By skaterboy987 in forum New To JavaReplies: 7Last Post: 10272011, 01:18 AM 
Prime Number  System print all the prime numbers ...
By pinkdreammsss in forum New To JavaReplies: 20Last Post: 04262009, 01:50 AM 
Prime numbers
By tercius in forum New To JavaReplies: 3Last Post: 05042008, 06:05 AM 
Prime numbers
By gapper in forum New To JavaReplies: 3Last Post: 02072008, 10:09 AM
Bookmarks