Well, for starters, it is a proven mathematical fact that if a number is prime, it is not divisible by any prime number that is less than its square root. In your inner loop you go up to i/2 and you can change this to Math.floor(Math.sqrt(i)).

Because you are checking for a range of numbers, you would probably benefit from a cache of primes, rather than testing every odd number less than the square root.

Something like this:

package mypackage;

import java.util.ArrayList;

/**
 * Checks for primeness using a cache.
 */
public class PrimeCache {

    private static ArrayList<Integer> cache = null;

    static {
        cache = new ArrayList<Integer>();
        cache.add(2);
    }

    public static boolean isPrime(int i) {
        if (i == 1) return false; // by definition

        int limit = (int) Math.floor(Math.sqrt(i));
        populateCache(limit);

        return doTest(i, limit);
    }

    private static void populateCache(int limit) {
        int start = cache.get(cache.size() - 1) + 1;
        for (int i = start; i <= limit; i++) {
            if (simpleTest(i)) cache.add(i);
        }
    }

    private static boolean simpleTest(int i) {
        int limit = (int) Math.floor(Math.sqrt(i));

        return doTest(i, limit);
    }

    private static boolean doTest(int i, int limit) {
        int counter = 0;
        while (counter < cache.size() && cache.get(counter) <= limit) {
            if (i % cache.get(counter) == 0) return false;
            counter++;
        }

        return true;
    }
}

Well, for starters, it is a proven mathematical fact that if a number is prime, it is not divisible by any prime number that is less than its square root. In your inner loop you go up to i/2 and you can change this to Math.floor(Math.sqrt(i)).

Because you are checking for a range of numbers, you would probably benefit from a cache of primes, rather than testing every odd number less than the square root.

Something like this:

package mypackage;

import java.util.ArrayList;

/**
 * Checks for primeness using a cache.
 */
public class PrimeCache {

    private static ArrayList<Integer> cache = null;

    static {
        cache = new ArrayList<Integer>();
        cache.add(2);
    }

    public static boolean isPrime(int i) {
        if (i == 1) return false; // by definition

        int limit = (int) Math.floor(Math.sqrt(i));
        populateCache(limit);

        return doTest(i, limit);
    }

    private static void populateCache(int limit) {
        int start = cache.get(cache.size() - 1) + 1;
        for (int i = start; i <= limit; i++) {
            if (simpleTest(i)) cache.add(i);
        }
    }

    private static boolean simpleTest(int i) {
        int limit = (int) Math.floor(Math.sqrt(i));

        return doTest(i, limit);
    }

    private static boolean doTest(int i, int limit) {
        int counter = 0;
        while (counter < cache.size() && cache.get(counter) <= limit) {
            if (i % cache.get(counter) == 0) return false;
            counter++;
        }

        return true;
    }
}

Well, for starters, it is a proven mathematical fact that if a number is prime, it is not divisible by any prime number that is less than its square root. In your inner loop you go up to i/2 and you can change this to Math.floor(Math.sqrt(i)).

Because you are checking for a range of numbers, you would probably benefit from a cache of primes, rather than testing every odd number less than the square root.

Well, for starters, it is a proven mathematical fact that if a number is prime, it is not divisible by any prime number that is less than its square root. In your inner loop you go up to i/2 and you can change this to Math.floor(Math.sqrt(i)).

Because you are checking for a range of numbers, you would probably benefit from a cache of primes, rather than testing every odd number less than the square root.

Something like this:

package mypackage;

import java.util.ArrayList;

/**
 * Checks for primeness using a cache.
 */
public class PrimeCache {

    private static ArrayList<Integer> cache = null;

    static {
        cache = new ArrayList<Integer>();
        cache.add(2);
    }

    public static boolean isPrime(int i) {
        if (i == 1) return false; // by definition

        int limit = (int) Math.floor(Math.sqrt(i));
        populateCache(limit);

        return doTest(i, limit);
    }

    private static void populateCache(int limit) {
        int start = cache.get(cache.size() - 1) + 1;
        for (int i = start; i <= limit; i++) {
            if (simpleTest(i)) cache.add(i);
        }
    }

    private static boolean simpleTest(int i) {
        int limit = (int) Math.floor(Math.sqrt(i));

        return doTest(i, limit);
    }

    private static boolean doTest(int i, int limit) {
        int counter = 0;
        while (counter < cache.size() && cache.get(counter) <= limit) {
            if (i % cache.get(counter) == 0) return false;
            counter++;
        }

        return true;
    }
}