• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 529
  • Last Modified:

Get a random prime number between a range of 2 BigInteger

Hi All,

Can anyone help to get a random prime number between a range of 2 BigInteger?

For example generate a random prime number between the range of 10000000000000000000000000000 to 10000000000000000000000000000000000


Thanxs
Garion
0
yongeng
Asked:
yongeng
  • 13
  • 8
  • 4
  • +1
3 Solutions
 
zzynxSoftware engineerCommented:
Have a look at http://java.sun.com/developer/JDCTechTips/2002/tt0806.html
(about BigInteger's probablePrime() function)
0
 
bloodredsunCommented:
Here's an example using a random selection between 1-1000 using integers.

package com.bloodredsun;

public class PrimePrimer {

      public static void main(String[] args) {
            
            int random =  (int)Math.floor(Math.random() * 1000) ;
            for(int ii = (random-50) ; ii < (random+50) ; ii++){
                  System.out.println("Checking " + ii);
                  System.out.println( isPrime(ii)) ;
            }
            System.out.println("random was: " + random) ;
      }
      
      //      See if n is a prime number
      private static boolean isPrime(int n) {
            for (int divisor=2; divisor*divisor <= n; divisor++) {
                  if (n % divisor == 0)
                        return false;
            }
            return true;
      } // end isPrime
}

You can easily apply this to your problem. Should you want to know more about the prime number calculation search for "Sieve of Eratosthenes"
0
 
yongengAuthor Commented:
Hi bloodredsun,

sorrie but all the variables declared are in "int", i would have a big problem if i use the codes......
0
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 
bloodredsunCommented:
>>the variables declared are in "int"

I'm well aware of this. As this sort of programming is commonly used a a homework example I'm unable to give you a complete example due to the EE rules.

You just need to take this example and use the correct operators such as divide() and multiply.
0
 
CEHJCommented:
Is this homework yongeng? If so, you've had a lot of previous qs answered ;-)
0
 
zzynxSoftware engineerCommented:
>> between the range of 10000000000000000000000000000 to 10000000000000000000000000000000000
That's with 29 to 35 digits.

Try this:

        Random r1 = new Random();
        Random r2 = new Random();
        for (int i=1; i<11; i++) {
            BigInteger prime = BigInteger.probablePrime(r1.nextInt(22)+94, r2);
            System.out.println(prime);
        }
0
 
CEHJCommented:
     public static List primesBetween(String bigInt1, String bigInt2) {
            List primes = new ArrayList();
            BigInteger biLo = new BigInteger(bigInt1);
            BigInteger biHi = new BigInteger(bigInt2);
            BigInteger nextPrime = null;
            while ((nextPrime = biLo.nextProbablePrime()).compareTo(biHi) < 0) {
                  primes.add(nextPrime);
                  biLo = nextPrime;
            }
            return primes;
      }

Running this function thus:

C:\DOCUME~1\Charles\MYDOCU~1\java>java BetweenPrimes 100 200

produces:

[101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179,
 181, 191, 193, 197, 199]
0
 
zzynxSoftware engineerCommented:
Remark for yongeng: nextProbablePrime() is available in java 1.5 only
0
 
yongengAuthor Commented:
>> Is this homework yongeng? If so, you've had a lot of previous qs answered ;-)

Hi,

erm.... this is not exactly my homework.....

i am doing some research on el gamel encryption and would like to use java to test it out.... thus all the questions.....

thanks to everyone who has helped me so much :)
0
 
yongengAuthor Commented:
Hi bloodredsun,

is it possible to break the for loop when isPrime is true?

i tried changing to:

          for(int ii = (random-50) ; ii < (random+50) ; ii++){

               System.out.println("Checking " + ii);
               System.out.println( isPrime(ii)) ;
               if (isPrime(ii)==true) break;

          }

but the result always return the number after the isPrime is true number...

is there a way to make it return the number which makes isPrime true?
0
 
yongengAuthor Commented:
sorrie.... posted the previous msg in a rush....

managed to resolve it....

      int random =  (int)Math.floor(Math.random() * 10000) ;
      for(int ii = (random-50) ; ii < (random+50) ; ii++)
      {
      //System.out.println("Checking " + ii);
      //System.out.println( isPrime(ii)) ;
      if (isPrime(ii)==true)
                     {
                     random = ii;
                     break;
               }
      }
0
 
zzynxSoftware engineerCommented:
Remark:
1) That should work
2) For performance reasons it's better not to call isPrime() twice:

          for(int ii = (random-50) ; ii < (random+50) ; ii++){
               System.out.println("Checking " + ii);
               boolean isPrime = isPrime(ii);
               System.out.println( isPrime ) ;
               if (isPrime==true) break;
          }

    or

          boolean isPrime = false;
          for(int ii = (random-50) ; ii < (random+50) && !isPrime ; ii++){
               System.out.println("Checking " + ii);
               isPrime = isPrime(ii);
               System.out.println( isPrime ) ;
          }
0
 
bloodredsunCommented:
Does this work for you?

package com.bloodredsun;

public class PrimePrimer {

       public static void main(String[] args) {
            int random =  (int)Math.floor(Math.random() * 1000 + 1000) ;
            for(int ii = (random-50) ; ii < (random+50) ; ii++){
                  if (isPrime(ii)==true){
                        System.out.println(ii + " is a prime: checking " + isPrime(ii) ) ;
                         break;
                  }
            }
       }
     
       //See if n is a prime number
       private static boolean isPrime(int n) {
              for (int divisor=2; divisor*divisor <= n; divisor++) {
                     if (n % divisor == 0)
                              return false;
              }
              return true;
       } // end isPrime
}
0
 
zzynxSoftware engineerCommented:
Did you remark that for random = 20, you start checking negative values like -30, -29, ... ?
Or is that intended?
0
 
zzynxSoftware engineerCommented:
bloodredsun, as I previously said, you'd better avoid calling isPrime() twice
0
 
zzynxSoftware engineerCommented:
An alternative for generating an int between 1000 (inclusive) and 2000 (exclusive) is:

java.util.Random r = new java.util.Random();
int random = r.nextInt(1000) + 1000;    // <<< personally, I find this one better readable
0
 
zzynxSoftware engineerCommented:
And this is a quicker version of isPrime():

     private static boolean isPrime(int n) {
          if (n % 2 == 0)
              return false;
          for (int divisor=3; divisor*divisor <= n; divisor+=2) {   // No use to try even divisors if you tested with 2
               if (n % divisor == 0)
                    return false;
          }
          return true;
     }
0
 
bloodredsunCommented:
>>as I previously said, you'd better avoid calling isPrime() twice
I know, it was just for emphasis so that it printed out "true"(and I hadn't refreshed so it wasn't there when I did)

>>int random = r.nextInt(1000) + 1000;    // <<< personally, I find this one better readable
Yes. I re-wrote the code to include the incrementor to make the value always positive and also chage the isPrime method to non-static so it's better for larger ranges.

----------
package com.bloodredsun;

public class PrimePrimer {

       public static void main(String[] args) {
             int iRange = 1000000000 ;
             int iSpread = 500 ;
             PrimePrimer Prime = new PrimePrimer() ;
            int random =  (int)Math.floor(Math.random() * iRange + iRange) ;
            for(int ii = (random-iSpread) ; ii < (random+iSpread) ; ii++){
                  if ( Prime.isPrime(ii)==true ){
                        System.out.println(ii + " is a prime: ") ;
                         //break; //comment out to see all in range
                  }
            }
       }
     
       //See if n is a prime number
       private boolean isPrime(int n) {
              for (int divisor=2; divisor*divisor <= n; divisor++) {
                     if (n % divisor == 0)
                              return false;
              }
              return true;
       } // end isPrime
}

0
 
zzynxSoftware engineerCommented:
>> for (int divisor=2; divisor*divisor <= n; divisor++) {
No use to try even divisors if you tested with 2
0
 
bloodredsunCommented:
>> And this is a quicker version of isPrime():

Very nice :-) I think it's asymptotically twice as fast depending on the range.
0
 
bloodredsunCommented:
for 10 000 spread of value, base of 1 000 000 000 , finding all primes took:
Standard took: 531ms
CEHJ took: 297ms

for 100 000 spread of value, base of 1 000 000 000 , finding all primes took:
Standard took: 5485ms
CEHJ version took: 3078ms

for 1 000 000 spread of value, base of 1 000 000 000 , finding all primes took:
Standard took: 56656ms
CEHJ took: 53422ms

Seems to fall off nicely but I'm a biologist by training so Maths is not the strongest part of my amoury.
0
 
zzynxSoftware engineerCommented:
>> Standard took: 531ms    << Is that your code including my changes?
>> CEHJ took: 297ms
0
 
zzynxSoftware engineerCommented:
I already wondered from the beginning why yongeng wouldn't use BigInteger's probablePrime()
(or nextProbablePrime() for 1.5)
;°)
0
 
bloodredsunCommented:
Sorry zzynx, I cut and pasted CEHJ's name from an earlier comment and looked right past it when I pasted it into the comment  box. My apologies.

As Tim would say, **blush** !

So this should read:

for 10 000 spread of value, base of 1 000 000 000 , finding all primes took:
Standard took: 531ms
zzynx version took: 297ms

for 100 000 spread of value, base of 1 000 000 000 , finding all primes took:
Standard took: 5485ms
zzynx version took: 3078ms

for 1 000 000 spread of value, base of 1 000 000 000 , finding all primes took:
Standard took: 56656ms
zzynx version  took: 53422ms

and I made your method non-static for a more direct comparison.
0
 
bloodredsunCommented:
>> I already wondered from the beginning why yongeng wouldn't use BigInteger's probablePrime()

me too ;-)
0
 
zzynxSoftware engineerCommented:
:°D

From the first link I posted, I quote:
Trying all odd divisors up to the square root is a hopelessly inefficient technique for generating prime numbers,
when the numbers are really big.
0
 
CEHJCommented:
:-)
0
 
zzynxSoftware engineerCommented:
thanks
0

Featured Post

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

  • 13
  • 8
  • 4
  • +1
Tackle projects and never again get stuck behind a technical roadblock.
Join Now