Prime Numbers Hints

2012-01-23 Lecture

First problem on "Prime Numbers" Assignment: (see previous notes on table thingy)

n // some command line parameter
boolean[] primes = new boolean[n];
for (int i = 2; i<n; i++)
    prime[i] = true;

for (int i = 2; i<n; i++) {
    for (int j=2; j<i;j++) {
        if (i%j == 0) {
            prime[i] = false;
            break;
        }
    }
}

For part 3, you need a seperate array of integers (primeNums) holding the prime numbers.

int[] primeNums = new int[n];
primeNums[0] = 2;
int pIndex = 1; // Next location to place a prime in the primeNums array
boolean isPrime;

for (int i = 2; i < n; i++) { 
    int jmax = (int) Math.sqrt(i);
    isPrime = true;
    for (int j = 0; primeNums[j] <= jmax; j++) {
        if (i % primeNums[j] == 0)
            isPrime = false;
            break;
    }
    if (isPrime) {
        primeNums[pIndex] = i;
        pIndex++;
    }
}

The sieve or Eratosthenes

2 3 4 5 6 7 8 9 10 11 12 13 14 15 ^ ^ x ^ x x x x x x x

n++;
n // command line parameter
boolean[] primes = new boolean[n];
for (int i = 2; i < n; i++)
    primes[i] = true;

int sqrtN = (int) Math.sqrt(n);
for (int i = 2; i <= sqrtN; i++) {
    if (primes[i]) {
        for (int j = i*i; j < n; j+=i) {
            primes[j] = false;
        }
    }
}

Actual Lecture for the Day

Overloading Two or more methods with the same name in the same class. The types and numbers of the parameters is how the compiler distinguises between the methods.

Packages A named collection of related classes that can serve as a library. It's a directory structure that's specified.