Mega Code Archive

 

Categories / Java / Data Type

 

Compute prime numbers

/* Compute prime numbers, after Knuth, Vol 1, Sec 1.3.2, Alg. "P".  * Unlike Knuth, I don't build table formatting into  * computational programs; output is one per line.  * <p>  * Note that there may be more efficient algorithms for finding primes.  * Consult a good book on numerical algorithms.  * @author Ian Darwin  */ public class Primes {   /** The default stopping point for primes */   public static final long DEFAULT_STOP = 4294967295L;   /** The first prime number */   public static final int FP = 2;   static int MAX = 10000;   public static void main(String[] args) {     long[] prime = new long[MAX];     long stop = DEFAULT_STOP;     if (args.length == 1) {       stop = Long.parseLong(args[0]);     }     prime[1] = FP;       // P1 (ignore prime[0])     long n = FP+1;       // odd candidates     int j = 1;        // numberFound     boolean isPrime = true;  // for 3     do {       if (isPrime) {         if (j == MAX-1) {           // Grow array dynamically if needed           long[] np = new long[MAX * 2];           System.arraycopy(prime, 0, np, 0, MAX);           MAX *= 2;           prime = np;         }         prime[++j] = n;  // P2         isPrime = false;       }       n += 2;        // P4       for (int k = 2; k <= j && k < MAX; k++) {  // P5, P6, P8         long q = n / prime[k];         long r = n % prime[k];         if (r == 0) {                 break;         }         if (q <= prime[k]) {    // P7           isPrime = true;           break;         }       }            } while (n < stop);        // P3     for (int i=1; i<=j; i++)       System.out.println(prime[i]);   } }