HiveBrain v1.2.0
Get Started
← Back to all entries
patterncppMinor

Prime Number Checker

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
numberprimechecker

Problem

This is my prime number checker in C++. I know that calculating the square root of a number can be very costly, so I don't do it unless the number is larger than 10k, where we would have to check 2450 extra values \$5k-\sqrt{10k}\over2\$.

void primeChecker(std::vector &primes, int val)
{
    int max = val > 10000 ? sqrt(val) : val / 2;
    for (int i = 0; primes[i] <= max; i++)
    {
        if (val % primes[i] == 0)
        {
            return;
        }
    }
    primes.push_back(val);
    std::cout << val << std::endl;
}


Running it like this, it takes a few seconds to calculate the top 1,000,000 primes:

int main()
{
    std::vector primes;
    primes.push_back(2);

    for (int i = 3; i < 1000000; i+=2)
    {
        primeChecker(primes, i);
    }

    return 0;
}


Am I breaking any coding standards, and are there any ways to improve this?

Solution

Instead of hard-coding 1000000000, use a constant:

const int maxPrimes = 1000000000;


Then, use it in the loop like this:

for (int i = 3; i < maxPrimes; i+=2)


This will make it clear what this value is.

Regarding the timing, you could use something from ` or another suitable library to time certain code sections. For instance, you may time the loop in main() or just the one in primeChecker()` for testing purposes. This may be OS-dependent, so I'll let you decide on this if you wish to try it.

Code Snippets

const int maxPrimes = 1000000000;
for (int i = 3; i < maxPrimes; i+=2)

Context

StackExchange Code Review Q#74657, answer score: 8

Revisions (0)

No revisions yet.