?
Solved

Get a random prime number between a range of 2 BigInteger

Posted on 2005-03-30
28
Medium Priority
?
471 Views
Last Modified: 2008-02-01
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
Comment
Question by:yongeng
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 13
  • 8
  • 4
  • +1
28 Comments
 
LVL 37

Expert Comment

by:zzynx
ID: 13660248
Have a look at http://java.sun.com/developer/JDCTechTips/2002/tt0806.html
(about BigInteger's probablePrime() function)
0
 
LVL 29

Assisted Solution

by:bloodredsun
bloodredsun earned 600 total points
ID: 13660322
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
 

Author Comment

by:yongeng
ID: 13660432
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.

 
LVL 29

Expert Comment

by:bloodredsun
ID: 13660493
>>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
 
LVL 86

Expert Comment

by:CEHJ
ID: 13660538
Is this homework yongeng? If so, you've had a lot of previous qs answered ;-)
0
 
LVL 37

Assisted Solution

by:zzynx
zzynx earned 600 total points
ID: 13660580
>> 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
 
LVL 86

Accepted Solution

by:
CEHJ earned 800 total points
ID: 13660633
     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
 
LVL 37

Expert Comment

by:zzynx
ID: 13660709
Remark for yongeng: nextProbablePrime() is available in java 1.5 only
0
 

Author Comment

by:yongeng
ID: 13680072
>> 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
 

Author Comment

by:yongeng
ID: 13680358
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
 

Author Comment

by:yongeng
ID: 13680413
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
 
LVL 37

Expert Comment

by:zzynx
ID: 13680447
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
 
LVL 29

Expert Comment

by:bloodredsun
ID: 13680467
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
 
LVL 37

Expert Comment

by:zzynx
ID: 13680468
Did you remark that for random = 20, you start checking negative values like -30, -29, ... ?
Or is that intended?
0
 
LVL 37

Expert Comment

by:zzynx
ID: 13680484
bloodredsun, as I previously said, you'd better avoid calling isPrime() twice
0
 
LVL 37

Expert Comment

by:zzynx
ID: 13680573
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
 
LVL 37

Expert Comment

by:zzynx
ID: 13680685
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
 
LVL 29

Expert Comment

by:bloodredsun
ID: 13680729
>>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
 
LVL 37

Expert Comment

by:zzynx
ID: 13680795
>> for (int divisor=2; divisor*divisor <= n; divisor++) {
No use to try even divisors if you tested with 2
0
 
LVL 29

Expert Comment

by:bloodredsun
ID: 13680808
>> And this is a quicker version of isPrime():

Very nice :-) I think it's asymptotically twice as fast depending on the range.
0
 
LVL 29

Expert Comment

by:bloodredsun
ID: 13680872
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
 
LVL 37

Expert Comment

by:zzynx
ID: 13680908
>> Standard took: 531ms    << Is that your code including my changes?
>> CEHJ took: 297ms
0
 
LVL 37

Expert Comment

by:zzynx
ID: 13680990
I already wondered from the beginning why yongeng wouldn't use BigInteger's probablePrime()
(or nextProbablePrime() for 1.5)
;°)
0
 
LVL 29

Expert Comment

by:bloodredsun
ID: 13681007
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
 
LVL 29

Expert Comment

by:bloodredsun
ID: 13681018
>> I already wondered from the beginning why yongeng wouldn't use BigInteger's probablePrime()

me too ;-)
0
 
LVL 37

Expert Comment

by:zzynx
ID: 13681148
:°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
 
LVL 86

Expert Comment

by:CEHJ
ID: 13692260
:-)
0
 
LVL 37

Expert Comment

by:zzynx
ID: 13695365
thanks
0

Featured Post

Free Tool: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

After being asked a question last year, I went into one of my moods where I did some research and code just for the fun and learning of it all.  Subsequently, from this journey, I put together this article on "Range Searching Using Visual Basic.NET …
Introduction This article is the first of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article explains our test automation goals. Then rationale is given for the tools we use to a…
Viewers learn about the third conditional statement “else if” and use it in an example program. Then additional information about conditional statements is provided, covering the topic thoroughly. Viewers learn about the third conditional statement …
This theoretical tutorial explains exceptions, reasons for exceptions, different categories of exception and exception hierarchy.
Suggested Courses
Course of the Month11 days, 18 hours left to enroll

752 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question