CODEWITHSUNDEEP
javarandomprimes
Jesse
Jesse

Reputation: 161

How to generate two primes p1, p2 bigger than 10^25

I need to generate two primes p1, p2 bigger than 10^25, and their product n. and a number "a" less than n.

Why I use the code below, the result of 4 number are all 0.

public static void main(String args[]) {

        long min = (long) Math.pow(10, 25);
        long max = Long.MAX_VALUE;
        long p1 = (long)((Math.random()+1)*(max-min));
        long p2 = (long)((Math.random()+1)*(max-min));
        long n = p1 * p2 ;
        long a = (long)((Math.random())* n) ;
        System.out.println("p1= " + p1 + ", p2= " + p2 + ", n= " + n +",a= " + a);
}

Thank you.

Upvotes: 1

Views: 219

Answers (3)

Freiheit
Freiheit

Reputation: 8767

This Math.SE question cites several locations to get lists of prime numbers:

Instead of randomly generating these numbers acquire a listing of the prime numbers that satisfy the conditions for your problem. Load that file as an array or list in your Java application. Then randomly generate a number to select an index in that list. You could also count lines in the file and read a line from the file.

This approach trades CPU time (and maybe bugs?) for I/O and memory to read the list.

You should also consider setting an upper bound which is smaller than the largest value your numeric type can store. The largest prime is over twenty million digits. BigInteger should be able to store that, however you may start running into memory limits with numbers that large.

Upvotes: 1

thibsc
thibsc

Reputation: 4049

You obtain 0 because to represent Long.MAX_VALUE you need 63 bits, but to represent 10^25 you need 84 bits.

BigInteger maxLong = new BigInteger(String.valueOf(Long.MAX_VALUE));        
BigInteger pow_10_25 = BigInteger.TEN.pow(25);
System.out.println(maxLong.bitLength()); // 63
System.out.println(pow_10_25.bitLength()); // 84

A possible solution is to use BigInteger:

  • Determine the minimum of bit length to use
  • Generate two probable prime number
  • Multiply the two generated prime number

By using BigInteger.probablePrime(int, Random): "The probability that a BigInteger returned by this method is composite does not exceed 2-100."

Example:

Random r = new Random();
BigInteger pow_10_25 = BigInteger.TEN.pow(25);
int minBitLength = pow_10_25.bitLength();

BigInteger p1 = BigInteger.probablePrime(minBitLength, r);
BigInteger p2 = BigInteger.probablePrime(minBitLength, r);  
BigInteger n = p1.multiply(p2);

Upvotes: 4

Chiran K.
Chiran K.

Reputation: 404

You have the following problem: the maximum value that a long can hold is 9223372036854775807 and your computation Math.pow(10, 25) exceeds that limit. Thus, both your min and max will have the value 9223372036854775807 and the max-min becomes zero. And the problem continues on. Try using a type than can be larger, like BigInteger.

Upvotes: 3

Related Questions