Answer to Question #188079 in C for Neel

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)
{
    
    if (n <= 1)
        return false;
 
    for (int i = 2; i < n; i++)
        if (n % i == 0)
            return false;
 
    return true;
}      

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

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.

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