Sign in to follow this  

Prime Number Generator [C++]

This topic is 2819 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

What I'm trying to do is make a prime number generator that will give the *th prime number. Code explains best:
#include <iostream>
using namespace std;

int main()
{
    int prime=0;
    int count=0;

    while (count != 5)
    {
        for(int i=prime; prime%i==0; i--)
        {

            if(count==5)
            {
                cout<<prime;
                break;
            }

            if(i==0)
            {
                count++;
                break;
            }
            
            else
                prime++;
            
        }

    }

    return 0;
}
This is suppossed to find the 5th prime number. The if(i==0) is suppossed to check if it's a prime. My logic behind this was if the for loop gave modulo i==0 the whole way along until 0, it must be a prime number. This code is a bit of a mess but I'm not sure what else I can do! Thanks

Share this post


Link to post
Share on other sites
Couldn't really follow the code. To check if a number is prime (exhastitivly) first calculate its square root then check every number up to and including that, if it divides exactly then its not a prime.

Find the first 10 primes:


bool IsPrime(int primeCandidate)
{
if(primeCandidate < 2)
{
return false;
}
int root = sqrt((double)primeCandidate);
for(int i = 2; i <= root; i++)
{
if(primeCandidate%i == 0)
{
return false;
}
}
return true;
}

int main()
{
int primes[10];
int numFound = 0;
int num = 0;
while(numFound < 10)
{
if(IsPrime(num))
{
primes[numFound] = num;
numFound++;
}
num++;
}
return 0;
}




Share this post


Link to post
Share on other sites
From Nanoha's code, the i's, by which is divided, can also only be prime numbers. So if you remember the previously found prime numbers, you should only test modulo != 0 for all those prime numbers up to sqrt(prime-candidate).
Also, Nanoha's code increases the primeCandidate and the i by one each time, it would be twice as fast if it'd start at 3 and increase by 2 each time.

Your code is indeed a bit hard to follow. Try to start at primeCandidate = 3, and thus count = 2. Two nested for-loops sounds like a better idea.

Also, I think you make a crucial mistake. Modulo prime of i must ONLY be zero for 1 and prime, for the rest it must NOT be zero, contrary to what you say. Tell me if I misunderstood you.

Share this post


Link to post
Share on other sites
Quote:
Original post by soitsthateasy
The if(i==0) is suppossed to check if it's a prime. My logic behind this was if the for loop gave modulo i==0 the whole way along until 0, it must be a prime number.


I also don't follow the code (it doesn't seem to match up with what I think you're saying).

However, what you seem to be suggesting is that a number n is prime if n mod k = 0 for all k < n. This is almost exactly the opposite of what you want to check - a mod b = 0 implies that a is divisible by b. You want to check for n mod k != 0 (as mentioned, there are ways to speed this up - most straightforwardly, you only need check up to the square root).

Share this post


Link to post
Share on other sites
Quote:
Couldn't really follow the code. To check if a number is prime (exhastitivly) first calculate its square root then check every number up to and including that, if it divides exactly then its not a prime.


You don't need to check *every* number from two to its square root, either. Of course, if you really want a fast algorithm, this brute force algorithm isn't going to be it once you start getting into numbers larger than a 32-bit integer data type will handle.


bool IsPrime(int primeCandidate)
{
if (primeCandidate < 2) return false; // less than 2
if (primeCandidate == 2) return true; // only even prime
if (primeCandidate % 2 == 0) return false; // divisible by 2

int root = sqrt( (double) primeCandidate);
for(int i = 3; i <= root; i += 2)
{
if(primeCandidate % i == 0)
{
return false;
}
}
return true;
}





[Edited by - CaspianB on March 29, 2010 7:55:26 PM]

Share this post


Link to post
Share on other sites
This line is questionable:
    int root = sqrt( (double) primeCandidate);


sqrt(25.0) could very well return some value slightly below 5, which would become 4 when casting to int. Then you would think that 25 is prime. I don't think this happens in practice, but I don't think there are any strong guarantees that it won't either.

Just to be safe, I usually add a small amount to the number before I take the sqrt. [EDIT: I only do this when I am using sqrt for this particular purpose.]

[Edited by - alvaro on March 30, 2010 1:01:12 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by alvaro
Just to be safe, I usually add a small amount to the number before I take the sqrt. [EDIT: I only do this when I am using sqrt for this particular purpose.]
I think that the more logical option to ensure it rounds up, is to take the ceil of the sqrt.
Otherwise, you're potentially adding numbers of vastly differing magnitudes and risk the smaller number having no effect on the larger number. Yes that's more a problem with floats than with doubles, but with 'ceil', it just works and you don't have to think twice about it.

Share this post


Link to post
Share on other sites
First, this reeks of homework.

Second, the problem is well-researched. There is no easy formula for it. You can use a simple Sieve approach but the problem quickly grows intractable. There are several formulas to approximate the prime sequence, but they aren't perfect and only work for relatively low numbers. Finally, there are a few nightmarishly complex formulas to enumerate all primes but they require so much work that they are only useful for math theory.



The two simple solutions are to write your own Sieve of Eratosthenes based algorithm, or to use a lookup table written by somebody else.

Sieve-based is easy enough. Create a container, store the value 2 in order to reduce your work by half. You are done if your count equals the size of the container. Start at 3, see if any number in the store divides it. If not, add it to the store. Then add two and repeat until the store size is equal to your needed prime. Done.

If you care about speed rather than space, Google can find lookup tables of them. (It's about 140MB if you get the full 32-bit table up to 4294967291.) It is both faster and easier to seek in a file and read a few bytes than it is to calculate primes above a million or so.

Share this post


Link to post
Share on other sites
Quote:
Original post by frob
Sieve-based is easy enough. Create a container, store the value 2 in order to reduce your work by half. You are done if your count equals the size of the container. Start at 3, see if any number in the store divides it. If not, add it to the store. Then add two and repeat until the store size is equal to your needed prime. Done.

This sounds a lot like trial division to me. You'd be better off following the sieve verbatim:



http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Also note that, if the nth prime is p, you can reduce the space complexity of the sieve up to p from O(p) to O(n) amortized. All it involves is only sieving against a list of some limited size (say, 5000) at a time, and better management of your prime number store.

There are other tricks I employ, but not much that can't be grasped from a skimming of Wikipedia. I'm definitely still a lightweight at this myself.

Quote:
Original post by frob
If you care about speed rather than space, Google can find lookup tables of them. (It's about 140MB if you get the full 32-bit table up to 4294967291.) It is both faster and easier to seek in a file and read a few bytes than it is to calculate primes above a million or so.

Hmm, I just ran a test of one of my sieves on my weary rig.

run:
Prime #10000000: 179424691
Time taken: 7352 milliseconds
BUILD SUCCESSFUL (total time: 7 seconds)

I place intractability a few orders of mangitude above a million, but yeah, sieving to int bounds is tough.
I had a sieve which was theoretically capable of switching to a double-type store for primes larger than INT_MAX, but I could never test it because my system didn't have the memory for it. It was only when I got it onto my uni's servers that I was able to confirm it - at which point I found out I needed to make a slight adjustment to the code to allow an extra ~5 million primes in the int store. >_>

Share this post


Link to post
Share on other sites
Thanks guys! It wasn't homework by the way. What kind of a 14 year old gets programming homework :P It was for ProjectEuler problems. My code was a mess but it's better now I think:


///////////////
//// Conor ////
//// Flynn ////
///////////////
#include <iostream>
using namespace std;

int isPrime(int prime)
{
if (prime < 2) return 0; // Not number less than 2 is a prime.
if (prime == 2) return 1; // 2 Is the only even prime.
if (prime % 2 == 0) return 0; // Eliminates even numbers.

int calculateTo = prime/2; // Finds how high I have to divide unitl. Should be the square root but this way was easier.

for(int i = 3; i <= calculateTo; i += 2) // Loop.
{
if(prime % i == 0)
{
return 0; // If a number is evenly divisible by another number, It's not a prime.
}
}
return 1;

}

int main()
{
int count=0;
int prime=2;
int howHigh;

cout<<"What prime number do you want?\n";
cin>>howHigh;

while(1)
{
if(isPrime(prime))
{
count++;
if(count==howHigh)
{
cout<<"Prime number " <<howHigh <<" is " <<prime;
return 0;
}

prime++;
}

else
{
prime++;
}

}

return 0;

//Bye!!! Comments welcome.
}



Thanks again!

Share this post


Link to post
Share on other sites
Ah. You'll be back here a few problems later, trying to figure out that sieve.

I'd also be learning to write a prime list generator class as a separate component if I were you. You'll be using it a lot.

Share this post


Link to post
Share on other sites

This topic is 2819 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this