Prime Numbers with sqrt()

1. In last week, our homework requires you to display all the prime numbers less than or equal to N.
2. To test whether an integer J is prime in that homework, you may have a simple algorithm which check whether J can be evenly divided by another integer K which is less than J but greater than 1.
3. This algorithm is correct, but it is not very efficient. In this exercise we want to briefly demonstrate to you why efficiency is critical.
4. Let us first modify your program so that it need not display all the prime numbers it found (otherwise I/O would be the bottleneck of this program). Simply count how many prime numbers are less than or equal to the given input N.
   • For example, when N = 100, the output is "There are 25 prime numbers."
   • When N = 1000, the output is "There are 168 prime numbers."
5. For a large number N = 100000, the original program takes 24.7s to find the answer "There are 9592 prime numbers."
6. Your mathematics teacher may have taught you, to check whether J is a prime number or not, it is actually unnecessary to try all the integers less than J. You only need to check the integers less than or equal to sqrt(J).
7. I modifed the loop, and this reduces the running time to 0.155s!
8. You can further improve this algorithm. For example, among the integers less than or equal to sqrt(J), you need not consider even numbers except 2. If J can be evenly divided by an even number, it must be evenly divided by 2, so checking with 2 is sufficient!
9. With this improvement, I can find the answer for N = 100,000 with only 0.048s, and the answer for N = 1,000,000 in only 1.157s!
10. This shows you the power of an efficient algorithm. You will learn more skills in the courses of "Data Structures" and "Algorithms".