Write a program that will calculate all of the prime numbers less than 1,000,000. Also, determine how many primes there are less than 1,000,000. There are many different ways to tackle this problem, some more efficient than others. Most "simple" methods for determining whether a number of primes do so by searching for factors. Actually, the question of determining if a number is prime _can_ be answered without ever actually finding any factors of a non-prime (composite) number are! But for this lab, we'll just stick with the relatively simple approach of searching and testing possible factors through BRUTE FORCE and trial and error. Several methods, each slightly "better" than the one before: 1) Test every value between 2 & the number. 2) Test every value between 2 and the square root of the number. 3) Test only the prime numbers between 2 and the square root of the number. For lab2, you will implement a solution to #3 above. Improve upon the program that I gave you in class so that it will only test the PRIME numbers between 2 and the square root of 'n' when it is testing a given number 'n' for prime. 

This is the program that he gave us.

// find all primes < 1M using BRUTE FORCE, checking

// ALL whole numbers less than square root as possible

// factors of 'n'

public class Lab2

{

public static boolean isPrime(int n)

{

int root = (int) Math.sqrt(n);

for (int i=2; i<=root; i++) {

if ((n%i) == 0)

{

return false;

}

}

return true;

}

public static void main(String args[])

{

int c=0;

long start, end, mstime;

final int LIMIT=1000000; // 1M took ~800 secs.

start = System.currentTimeMillis();

for (int i=2; i

if (isPrime(i)) {

System.out.println(i);

c++;

}

}

end = System.currentTimeMillis();

mstime = end - start;

System.out.println("#primes = " + c + ", mstime = " + mstime);

}

}