public static int[] primes(int n) {
		if (n <= 2) {
			int[] result = {};
			return result;
		}
		
		ArrayList<Integer> list = new ArrayList<Integer>();
		boolean[] array = new boolean[n];

		for (int i = 3; i < n; i += 2) { // consider odds only
			array[i] = true;
		}
		
		int prime = 3;
		int q;
		list.add(2);
		
		while (prime < n) {
			list.add(prime);
			q = prime * prime; // skip to first square, all others below have already been eliminated
			
			while (q > 0 && q < n) { // check overflow
				array[q] = false;
				q += prime;
			}
			
			prime += 2;
			while (prime < n && array[prime] == false) {
				prime += 2; // check odds only
			}
		}
		
		int[] result = new int[list.size()];
		int index = 0;
		for (int i : list) {
			result[index++] = i;
		}
		
		return result;
	}