Answer to Question #187985 in C++ for Shayla

Question

Compare the methods of determining prime numbers with code and concept.

i.Naive method

ii.square root method

iii.Seive of Eratosthenes

Answer 1

bool isPrime(int n)
{
    // Corner case
    if (n <= 1)
        return false;
 
    // Check from 2 to n-1
    for (int i = 2; i < n; i++)
        if (n % i == 0)
            return false;
 
    return true;
}      //  NAIVE

A naive solution is to iterate through all numbers from 2 to n-1 and for every number check if it divides n. If we find any number that divides, we return false.

Seive of Eratosthenes

1. Decide on a range of numbers you wish to test and lay them out on square grid. Just like in the first method, you will need to find the square root to decide how wide to make the grid: your work will be shorter if the grid is as close to a perfect square as is possible.
2. For example, to test all the numbers from 1 to 25 for primes, make the following 5x5 grid:
3. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
4. Cross out 1 with an X, because 1 is never considered prime by mathematicians for technical reasons.
5. Circle 2, because 2 is a prime. Now, cross out with an X every number which can be evenly divided by 2. So, cross out 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24. These numbers cannot be prime because they can be divided by a number other than 1 and themselves; namely 2.
6. Circle 3, and repeat the previous step, crossing out all the multiples of 3 which aren't already crossed out.
7. Skip 4, because it is crossed out and circle the next number which has not been crossed out (5). It is a prime number. Continue until all the numbers on your chart are either circled or crossed out. If you made your chart perfectly square, that should occur about the time you finish the first row.

SQUARE ROOT METHOD

A more intuitive explanation of the same thing. For the same reasons.

The square root of 100 is 10. Let's say a x b = 100, for various pairs of a and b.

If a == b, then they are equal, and are the square root of 100, exactly. Which is 10.

If one of them is less than 10, the other has to be greater. For example, 5 x 20 == 100. One is greater than 10, the other is less than 10.

Thinking about a x b, if one of them goes down, the other must get bigger to compensate, so the product stays at 100. They pivot around the square root.

The square root of 101 is about 10.049875621. So if you're testing the number 101 for primality, you only need to try the integers up through 10, including 10. But 8, 9, and 10 are not themselves prime, so you only have to test up through 7, which is prime.

Because if there's a pair of factors with one of the numbers bigger than 10, the other of the pair has to be less than 10. If the smaller one doesn't exist, there is no matching larger factor of 101.

If you're testing 121, the square root is 11. You have to test the prime integers 1 through 11 (inclusive) to see if it goes in evenly. 11 goes in 11 times, so 121 is not prime. If you had stopped at 10, and not tested 11, you would have missed 11.

You have to test every prime integer greater than 2, but less than or equal to the square root, assuming you are only testing odd numbers.

The conclusion of all this:

1) square root method is more optimized than naive method;

2)Seive of Eratosthenes is more optimized than square root method