#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;
}
Prime Number Generator [C++]
Author
What I'm trying to do is make a prime number generator that will give the *th prime number.
Code explains best:
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:
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;}
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.
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.
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).
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]
This line is questionable:
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]
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]
Quote:Original post by alvaroI think that the more logical option to ensure it rounds up, is to take the ceil of the sqrt.
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.]
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.
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.
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.
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. >_>
Author
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:
Thanks again!
/////////////// //// 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!
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
