Public Group

#### Archived

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

# Prime Number Program

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

## 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 on other sites
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 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 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 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 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 on other sites
Also, you only need to test up to sqrt(x), not x/2.

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

##### 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 on other sites
quote:
Original post by twix
Still, mine pwnz and you know it.
Uh, no.

Sieve of Eratosthenes

##### Share on other sites
Feh, I''m just implementing people''s suggestions here.

1. 1
Rutin
34
2. 2
3. 3
4. 4
5. 5

• 12
• 14
• 9
• 9
• 9
• ### Forum Statistics

• Total Topics
633334
• Total Posts
3011409
• ### Who's Online (See full list)

There are no registered users currently online

×