Prime Number Program
Author
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
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]
*SPOILER*
an optimized version...
-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.
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.
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.
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.
"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]
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]
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.
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]
Whoops, you metioned that already.
[edited by - twix on August 6, 2003 4:09:25 PM]
I'm addicted to making these pointless little programs. Something must be seriously wrong with me.
Still, mine pwnz and you know it.
[edited by - twix on August 6, 2003 4:43:07 PM]
#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]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
