Jump to content
  • Advertisement
Sign in to follow this  
DevFred

prime numbers

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by Sneftel
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).

Something like that?

for (int i = 10; i--; )
{
// do stuff
}

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

Share this post


Link to post
Share on other sites
Quote:
Original post by DevFred

for (int i = 10; i--; )
{
// do stuff
}


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

Share this post


Link to post
Share on other sites
Quote:
Original post by Sneftel
try 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 this post


Link to post
Share on other sites
Quote:
Original post by MJP
Instead of calling a function in main, you can do this:


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

std::vector<natural> 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 this post


Link to post
Share on other sites
Quote:
Original post by janta
The standard guarantees wrapping of unsigned integers, right?

Not for underflow! [smile]

Share this post


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

Okay, how about this?

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

Share this post


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

Okay, how about this?

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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!