1    package math; 
2     
3    import java.math.BigInteger; 
4     
5    /** 
6     * Created by 
7     * User: lyon 
8     * Date: Aug 23, 2003 
9     * Time: 10:07:55 PM 
10    * 
11    */ 
12   public class Prime { 
13    
14    
15       /** 
16        * Uses a trivail algorithm to determing the first N prime numbers. 
17        * The algorithm is not computationally efficient, however it requires 
18        * nearly zero storage.  And besides, we're trying to stress the processor. 
19        * 
20        */ 
21       /** Represents the number of prime numbers to calculate. */ 
22       private int n = 0; 
23    
24       private BigInteger TWO = new BigInteger("2"); 
25    
26       /** */ 
27       private BigInteger primes[] = null; 
28    
29       /** */ 
30       private int primeCount = 0; 
31    
32       /** */ 
33       public Prime(int n) { 
34           this.n = n; 
35    
36           primes = new BigInteger[n]; 
37           primes[0] = new BigInteger("2"); 
38           primes[1] = new BigInteger("3"); 
39    
40           primeCount = 1; 
41       } 
42    
43       /** */ 
44       public void calculate() { 
45           System.out.println("Calculating " + n + " primes"); 
46           int primeCount = 1; 
47    
48           BigInteger test = new BigInteger("5"); 
49           while (primeCount < n - 1) { 
50               if (isPrime(test)) { 
51                   primeCount++; 
52                   primes[primeCount] = test; 
53               } else { 
54                   //if (test.isProbablePrime(2)) 
55                   if (false) 
56                       System.out.println(test + " is probable, but not prime"); 
57               } 
58               test = test.add(TWO); 
59           } 
60           System.out.println("the " + n + "th prime is " + primes[n - 1]); 
61       } 
62    
63       private final boolean isPrime(BigInteger bi) { 
64           BigInteger half = bi.divide(TWO); 
65           for (BigInteger i = TWO; 
66                i.compareTo(half) == -1; 
67                i = i.add(BigInteger.ONE)) { 
68               BigInteger q[] = bi.divideAndRemainder(i); 
69    
70               // If the remainder of the division is zero, the number is not prime. 
71               if (q[1].equals(BigInteger.ZERO)) 
72                   return false; 
73           } 
74           return true; 
75       } 
76    
77    
78    
79       public static void main(String args[]) { 
80           int count = 10000; 
81           Prime prime = new Prime(count); 
82           long start = System.currentTimeMillis(); 
83           prime.calculate(); 
84           long end = System.currentTimeMillis(); 
85           System.out.println("The " + count + "th prime is " + prime.primes[count - 1]); 
86           System.out.println("Time to calculate: " + (end - start)); 
87       } 
88   } 
89    
90