prime numbers

This topic is 3828 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

Given a natural number, I often need to find the next prime number (for example when building hash tables). So I wrote a little C++ program that does the job for me, and I have a couple of questions:
#include <algorithm>
#include <limits>
#include <iostream>
#include <cmath>
#include <vector>

typedef unsigned natural;
std::vector<natural> primes;

void eratosthenes()
{
const natural sieve_size = 1 << (std::numeric_limits<natural>::digits >> 1);
bool is_prime[sieve_size];
std::fill(is_prime, is_prime + sieve_size, true);
is_prime[0] = false;
is_prime[1] = false;

for (natural i = 2; i < sieve_size; ++i)
{
if (is_prime)
{
primes.push_back(i);
for (natural k = i + i; k < sieve_size; k += i)
is_prime[k] = false;
}
}
}

bool is_prime(natural i)
{
typedef std::vector<natural>::iterator vit;
const natural root = static_cast<natural>(sqrt(i));
const vit end = primes.end();
for (vit it = primes.begin(); it != end && *it <= root; ++it)
if ((i % *it) == 0) return false;
return true;
}

const natural max = std::numeric_limits<natural>::max();

int main()
{
eratosthenes();
std::cout << "enter any number to calculate next prime or garbage to exit\n\n? ";
natural i;
while (std::cin >> i)
{
std::cout << "! ";
if (i <= *primes.rbegin())
{
std::cout << *lower_bound(primes.begin(), primes.end(), i);
}
else
{
for (i |= 1; i != max & !is_prime(i); i += 2);
if (i != max)
std::cout << i;
else
std::cout << "overflow";
}
std::cout << "\n\n? ";
}
}

1. The global primes needs to be initialized only once, so I call eratosthenes at the beginning of main. Is there a cleaner way of doing that? I guess im looking for something like static initializers in Java. 2. Is bool is_prime[sieve_size]; standard C++? 3. Is there a better solution than an array of bool in terms of memory consumption? Micro optimization questions, no real concern, just curious 4. Can I calculate the square root of an integer without converting to and from double via a standard C++ library function? I guess calculating it myself using approximations will not gain me anything, right? 5. Is a loop condition of the form it != something.end() slower than saving something.end() to a local variable and comparing it to that? Any general comments on my source? Thanks!

Share on other sites
Quote:
 1. The global primes needs to be initialized only once, so I call eratosthenes at the beginning of main. Is there a cleaner way of doing that? I guess im looking for something like static initializers in Java.

Load it from a file, if the time/space tradeoffs are worth it. Otherwise, you could do this with some static initialization hackery (constructor of a global variable doing the work) but I don't recommend it because it's yucky.

Quote:
 2. Is bool is_prime[sieve_size]; standard C++?

Yes, because the constant's value is visible from within the translation unit. (The rules may be a little more complicated... this is just from memory.)

Quote:
 3. Is there a better solution than an array of bool in terms of memory consumption?
Yes, a bitvector would use less storage. But you shouldn't worry too much about the size of local variables.

Quote:
 4. Can I calculate the square root of an integer without converting to and from double via a standard C++ library function?
Yes, I belive there's code floating around to do just that. BTW, an approximation which overestimates the square root is fine.

Quote:
 5. Is a loop condition of the form it != something.end() slower than saving something.end() to a local variable and comparing it to that?
Possibly but not necessarily. Check the generated assembly (from an optimized compilation) to see if end() is being called each time around.

Quote:
 Any general comments on my source?

typedef unsigned natural;

Don't do this. I know it sounds clever now, but it's not. For one thing, it makes your code less readable, because now programmers (who already know what unsigned means) have to additionally remember what natural means. More importantly, unsigned integers are a lot more painful than they'd appear. As an example of this, try writing a for-loop which uses an unsigned counter variable to count down from 9 to 0 (inclusive).

Share on other sites
Instead of calling a function in main, you can do this:

std::vector<natural> eratosthenes(){    ...}std::vector<natural> primes = eratosthenes();

Share on other sites
Quote:
 Original post by SneftelMore importantly, unsigned integers are a lot more painful than they'd appear. As an example of this, try writing a for-loop which uses an unsigned counter variable to count down from 9 to 0 (inclusive).

Something like that?
for (int i = 10; i--; ){    // do stuff}

I don't know... I just love unsigned :) Thanks for your input.

Share on other sites
Quote:
 Original post by DevFredfor (int i = 10; i--; ){ // do stuff}

Exactly. Sticking the decrement in the test should be your first clue that Aught Is Amiss.

Share on other sites
Quote:
 Original post by Snefteltry writing a for-loop which uses an unsigned counter variable to count down from 9 to 0 (inclusive).

for (unsigned int i = 9 ; i != ((unsigned int)0) - 1 ; --i){}

Not pretty but still possible. The standard guarantees wrapping of unsigned integers, right?

Share on other sites
Quote:
 Original post by MJPInstead of calling a function in main, you can do this:std::vector eratosthenes(){ ...}std::vector primes = eratosthenes();

Of course, thanks! Changes:
- initilization of primes
- primes -> const primes
- iterator -> const_iterator
- reserving enough space in local primes before the algorithm and cutting off unused space before returning
- natural -> unsigned

#include <algorithm>#include <limits>#include <iostream>#include <cmath>#include <vector>std::vector<unsigned> eratosthenes(){    const unsigned sieve_size = 1 << (std::numeric_limits<unsigned>::digits >> 1);    bool is_prime[sieve_size];    std::fill(is_prime, is_prime + sieve_size, true);    is_prime[0] = false;    is_prime[1] = false;    std::vector<unsigned> primes;    primes.reserve(sieve_size);    for (unsigned i = 2; i < sieve_size; ++i)    {        if (is_prime)        {            primes.push_back(i);            for (unsigned k = i + i; k < sieve_size; k += i)                is_prime[k] = false;        }    }    std::vector<unsigned>(primes).swap(primes);    return primes;}const std::vector<unsigned> primes = eratosthenes();bool is_prime(unsigned i){    typedef std::vector<unsigned>::const_iterator vit;    const unsigned root = static_cast<unsigned>(sqrt(i));    const vit end = primes.end();    for (vit it = primes.begin(); it != end && *it <= root; ++it)        if ((i % *it) == 0) return false;    return true;}const unsigned max = std::numeric_limits<unsigned>::max();int main(){    std::cout << "enter any number to calculate next prime or garbage to exit\n\n? ";    unsigned i;    while (std::cin >> i)    {        std::cout << "! ";        if (i <= *primes.rbegin())        {            std::cout << *lower_bound(primes.begin(), primes.end(), i);        }        else        {            for (i |= 1; i != max & !is_prime(i); i += 2);            if (i != max)                std::cout << i;            else                std::cout << "overflow";        }        std::cout << "\n\n? ";    }}

Share on other sites
Quote:
 Original post by jantaThe standard guarantees wrapping of unsigned integers, right?

Not for underflow! [smile]

Share on other sites
Quote:
 Original post by SneftelExactly. Sticking the decrement in the test should be your first clue that Aught Is Amiss.

for (int i = 9; i != std::numeric_limits<unsigned>::max(); --i){    // do stuff}

Share on other sites
Quote:
Original post by DevFred
Quote:
 Original post by SneftelExactly. Sticking the decrement in the test should be your first clue that Aught Is Amiss.

for (int i = 9; i != std::numeric_limits<unsigned>::max(); --i){    // do stuff}

Bzzt. The language standard doesn't require unsigned integers to underflow to the maximum.

• What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

(You must login to your GameDev.net account.)

• 11
• 11
• 15
• 11
• 11
• Forum Statistics

• Total Topics
634149
• Total Posts
3015834
×