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

# 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
• 13
• 8
• 4
• +1
3 Solutions

Software engineerCommented:
Have a look at http://java.sun.com/developer/JDCTechTips/2002/tt0806.html
0

Commented:
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 Commented:
Hi bloodredsun,

sorrie but all the variables declared are in "int", i would have a big problem if i use the codes......
0

Commented:
>>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

Commented:
Is this homework yongeng? If so, you've had a lot of previous qs answered ;-)
0

Software 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

Commented:
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) {
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

Software engineerCommented:
Remark for yongeng: nextProbablePrime() is available in java 1.5 only
0

Author 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

Author 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

Author 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

Software 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

Commented:
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

Software engineerCommented:
Did you remark that for random = 20, you start checking negative values like -30, -29, ... ?
Or is that intended?
0

Software engineerCommented:
bloodredsun, as I previously said, you'd better avoid calling isPrime() twice
0

Software 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

Software 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

Commented:
>>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 ;
PrimePrimer Prime = new PrimePrimer() ;
int random =  (int)Math.floor(Math.random() * iRange + iRange) ;
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

Software engineerCommented:
>> for (int divisor=2; divisor*divisor <= n; divisor++) {
No use to try even divisors if you tested with 2
0

Commented:
>> And this is a quicker version of isPrime():

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

Commented:
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

Software engineerCommented:
>> Standard took: 531ms    << Is that your code including my changes?
>> CEHJ took: 297ms
0

Software engineerCommented:
I already wondered from the beginning why yongeng wouldn't use BigInteger's probablePrime()
(or nextProbablePrime() for 1.5)
;Â°)
0

Commented:
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** !

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

0

Commented:
>> I already wondered from the beginning why yongeng wouldn't use BigInteger's probablePrime()

me too ;-)
0

Software 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

Commented:
:-)
0

Software engineerCommented:
thanks
0

## Featured Post

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