Calculation for Primes using square roots, and algorithm build inquiry

Question

Below is a calculation for primes. I was trying to deconstruct it to get a better understanding of loops. Also, I would like to tweak this function to find primes by comparing a number to its square root instead of this way:

(assume proper declarations are made before int main)

// Determines whether the number is prime

bool isPrime (long n)
{
    int a;

    if (n == 1)
    {
        return false;
    }

    for (a = 2; a <= (n / 2); a++)
    {
        if ((n % a) == 0)
        {
            return false;
        }

    }
    return true;
}

However, observing this loop, I have a question to see if I am observing this function correctly to start with. From what I see, it looks like int a; is the counter and it is starting at 2 since 0 and 1 are not prime. n should be the formal variable. It states that for every number which is less than or equal to itself when divided by two, returns a true for bool if there is a remainder of more than zero. At the same time, if a number divides by two evenly (so no remainder) then it is not considered prime (the bool returns false). Does that sound about right? If not, please do let me know where I made a wrong turn. If I got it right, on to the second half of the program.

Now here, primeCount; is limited with primeCount (2, 50000); in main but The first function feeds into here:

// Counts and organizes the prime numbers using the isPrime function

long primeCount (long x, long y)
{
    bool prime;
    int b;
    int c = 1000;
    int counter = 0;
    int totalSum = 0;

    for (b = 1; b <= y; b++)
    {
        prime = isPrime (b);

        if (prime == true)
        {
            counter++;
        }
        if (b == c)
        {
            cout << setw(10) << left << (b - 999) << setw(10) << left << b << setw(12) << counter << endl;
            cout << fixed << showpoint << setprecision(2) << endl;
            totalSum = totalSum + counter;
            counter = 0;
            c = c + 1000;
        }
    }

Now, I figure x and y are formal variables but I don't know what x is supposed to represent. Does it represent int c; ? The for loop in that function completely confused me. I don't understand it. Any light that can be shed on that would be appreciated.

As for the square root inquiry, would I need to use 3 nested for loops in order to get the primes?Like this:

 for (a > m => b)

  for (a==m => b==m)

    for (a < m => b>m)

Would locating the primes this way be more or less complicated than the way illustrated here? I know this is a lot to tackle. IF you guys suggest that I break it into separate posts, I'll edit this one and post the second half in a different post. Thanks for the assist! Just a freshman C++ programmer trying to make heads and tails out of this stuff :)

Answer 1

The first function isPrime() does what it is supposed to. Returns true if a number is prime and returns false if it is not. The reason why the loop variable a runs only till n/2 is because any number n cannot have a factor that is greater than n/2 (apart from itself). EXAMPLES? 6 -- 1, 2, 3 and 6, 12 -- 1, 2, 3, 4, 6 and 12. The loop is just trying to see if a has any factors (numbers that divide it without leaving a remainder). If it does it is not a prime (return false) else it is (return true).

However I feel that primeCount() doesn't completely do what it is intended to.

From the definition of primeCount() I think it is meant to compute the total number of prime numbers from x to y (in your case 2 to 50000, since you mentioned main() calls primeCount(2, 50000)). However for it to do this the for loop must be changed to this

for (b = x; b <= y; b++)

The role of the variable c here is to keep a check for every thousandth value of the loop variable b.

Notice that on 1st run when b = 1000 i.e b == c the program prints the number of primes that it encountered until now (counter). After that the counter is reset to 0 and c is now 2000.Then, b goes on from 1001 to 2000 and the same thing repeats till b is 50000.

Overall, The idea is to print the number of primes that exist within each 1000 natural numbers from 2 to 50000.

Answer 2

for (a = 2; a <= (n / 2); a++)
{
    if ((n % a) == 0)
    {
        return false;
    }

}

This is the "for" loop you use. It checks the remainder of n when dividing by each "a", iterating from 2, up to n/(one half (integral division) of n). If ANY of these remainders is zero, then n is a composite, and there's no point continuing onward. We just return a false - the number is not prime.

It is safe to assume that if we have not found a divisor of n until (n/2), the number is a prime, so AFTER we try all possibile guesses for divisors, if we got that far, we return that the number IS prime.