Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

jcdenton999

Prime Number Program

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

I''m reading Bruce Eckel''s ''Thinking in C++'' book. I have no prior programming experience. After reading the chapter about loops, a question comes up which i can''t seem to find a solution to. The question is: "Write a program that uses two nested for loops and the modulus operator (%) to detect and print prime numbers (integral numbers that are not evenly divisible by any other numbers except for themselves and 1)". I am familier with the structure of for loops, and I know what the modulus operator does. Is there some sort of equation for detecting prime numbers that i can use. Thanks for any help

Share this post


Link to post
Share on other sites
Advertisement

for number in range
if number is divisible (x%y==0) by something except itself and one
it ain't prime
otherwise, print it cause it's prime

Not much to it, is there. ^_^

[edited by - twix on August 6, 2003 2:26:03 PM]

Share this post


Link to post
Share on other sites
*SPOILER*








an optimized version...


const int MAX_NUMBER=1000;
bool divisorFound=false;

for(int x=0, x<MAX_NUMBER, x+=2)
{

for(int y=3, y <= x/2, y+=2)
{
if (!(x%y)) { divisorFound=true; }
}
if (divisorFound) { std::cout << x; break;}
}


-Skips even number... only odd numbers can be prime
-Stop looking for other value of y when y>=x/2... x cannot be divided by a number more than its half. (It''s technically square root but i didn''t bother..)
-Breaks immediately when a divisor is found.

Share this post


Link to post
Share on other sites
Another optimization is that you don''t need to even test every odd number, only the previously found prime numbers. Save that until you get to lists and things though.

Share this post


Link to post
Share on other sites
Isn't a number a prime when there are no divisors? And shouldn't you reset the variable after each search?!
And if a divisor is found, the number is surely not a prime, so you can step out of the for-loop.
Starting the first loop from 0 isn't a good idea when you add 2 to that number every time, because that makes you checking only pair numbers. My code isn't correct yet , it still has a bug in it.


#include <iostream>
#include <stdlib.h>
#include <math.h>

using namespace std;

int main(int argc, char *argv[])
{
const int MAX_NUMBER=1000;
bool divisorFound=false;
for (int x=1; x<MAX_NUMBER; x+=2)
{
for (int y=3; y <= sqrt((double)x); y+=2)
{
if (x%y)
{
divisorFound=true;
break;
}
}
if (divisorFound)
{
cout << x << endl;
} else {
divisorFound = false;
}
}
system("PAUSE");
return 0;
}


"My basic needs in life are food, love and a C++ compiler"
[Project AlterNova] [Novanet]



[edited by - Vich on August 6, 2003 4:10:53 PM]

Share this post


Link to post
Share on other sites
Yeah some mistakes I did that quickly... but still.. the guys learning so obscure constructs like the ? operator and the use of bitshifts should be avoided.

Share this post


Link to post
Share on other sites
Also, you only need to test up to sqrt(x), not x/2.

Whoops, you metioned that already.

[edited by - twix on August 6, 2003 4:09:25 PM]

Share this post


Link to post
Share on other sites
I'm addicted to making these pointless little programs. Something must be seriously wrong with me.

#include <iostream>
#include <algorithm>
#include <list>
#include <cstdlib>
#include <boost/lambda/lambda.hpp>

using namespace std;
using namespace boost::lambda;

int main()
{
const int MAX_NUMBER = 1000;
list<int> primes;
cout << 2 << endl;

for (int x=3; x<MAX_NUMBER; x+=2)
if (find_if(primes.begin(), primes.end(), x%_1==0) == primes.end())
primes.push_back(x);

for_each(primes.begin(), primes.end(), cout << _1 << "\n");

system("PAUSE");
return 0;
}

Still, mine pwnz and you know it.

[edited by - twix on August 6, 2003 4:43:07 PM]

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

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

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!