C/C++ Help
 
Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
 
User Name:
Password:
Remember me
 



Go Back   Dev Articles Community ForumsProgrammingC/C++ Help

Reply
Add This Thread To:
  Del.icio.us   Digg   Google   Spurl   Blink   Furl   Simpy   Y! MyWeb 
Thread Tools Search this Thread Display Modes
 
Unread Dev Articles Community Forums Sponsor:
  #1  
Old November 4th, 2006, 04:17 PM
fragop fragop is offline
Registered User
Dev Articles Newbie (0 - 499 posts)
 
Join Date: Nov 2006
Posts: 1 fragop User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 27 m 46 sec
Reputation Power: 0
Angry Program to find prime numbers

So I need to write a program that finds the prime numbers between 1 and 50 and then display the numbers plus how many prime numbers there are and how many non-prime numbers there are. I have a program written but the output is deifnantly not write, displaying some of the prime numbers several times and displaying some of the non prime numbers. Any help would be appreciated.

#include <iostream>

using namespace std;


int start_num; //starting number
int divisor; //number used to find prime numbers
int prime_num=1; //accumulator for prime numbers
int nonprime_num=1; //accumulator for non prime numbers
int end_num=50; //ending number

int main()
{
for(start_num=1; start_num<=end_num; start_num++)
{
for(divisor=2; divisor<=start_num/2; divisor++)
{
if((start_num%divisor==0) && (start_num!=divisor))
{
nonprime_num=nonprime_num+1;
break;
}
else
{
prime_num=prime_num + 1;
cout<<start_num<<"\n";
}

}
}
cout<<"Number of prime numbers: "<<prime_num<<"\n";
cout<<"Number of non-prime numbers: "<<nonprime_num<<"\n";
return 0;
}


Thanks

Reply With Quote
  #2  
Old November 4th, 2006, 06:17 PM
ubergeek ubergeek is offline
Contributing User
Dev Articles Novice (500 - 999 posts)
 
Join Date: Jan 2005
Posts: 600 ubergeek User rank is Private First Class (20 - 50 Reputation Level)ubergeek User rank is Private First Class (20 - 50 Reputation Level) 
Time spent in forums: 2 Days 22 h 40 m 27 sec
Reputation Power: 14
Send a message via AIM to ubergeek
First of all, I added some indents and spaces to your code to make it readable. (I also used this forum's fantastic highlight tag.)
C++ Code:
Original - C++ Code
  1.  
  2. #include <iostream>
  3.  
  4. using namespace std;
  5.  
  6.  
  7. int start_num; //starting number
  8. int divisor; //number used to find prime numbers
  9. int prime_num = 1; //accumulator for prime numbers
  10. int nonprime_num = 1; //accumulator for non prime numbers
  11. int end_num = 50; //ending number
  12.  
  13. int main()
  14. {
  15.     for(start_num = 1; start_num <= end_num; start_num++)
  16.     {
  17.         for(divisor = 2; divisor <= start_num / 2; divisor++)
  18.         {
  19.             if( (start_num % divisor == 0) && (start_num != divisor) )
  20.             {
  21.                 nonprime_num = nonprime_num + 1;
  22.                 break;
  23.             }
  24.             else
  25.             {
  26.                 prime_num = prime_num + 1;
  27.                 cout << start_num << "\n";
  28.             }
  29.        
  30.         }
  31.     }
  32.     cout << "Number of prime numbers: " << prime_num << "\n";
  33.     cout << "Number of non-prime numbers: " << nonprime_num << "\n";
  34.     return 0;
  35. }

Now, the logic problem. Let's dissect the inner for loop:
Loop maybe-divisors from 2 to half the maybe-prime number. Each time, check whether the maybe-divisor is actually a divisor. If it is, increment the nonprime counter and move on. Otherwise, increment the prime counter and print out the proved-to-be-prime number. Wait, what? Each time we find an invalid divisor, decide we have another prime number? That doesn't sound right to me. Choose a number for start_num and walk through the loop in your head if that didn't make sense to you.

To fix this, I changed around your loop a little bit. Basically, now it checks whether the divisor really is one. If it isn't, it skips the loop body and checks the next divisor. When it finds a divisor, it increment the nonprime counter and moves on. So if the number is prime, none of the divisors will work and the loop body (which increments the nonprime counter) will never execute. I removed the prime counter because it was hard to implement with my approach and also unnecessary -- you know end_num and nonprime_num, so prime_num is however many numbers are left over.
C++ Code:
Original - C++ Code
  1.  
  2. #include <iostream>
  3.  
  4. using namespace std;
  5.  
  6.  
  7. int start_num; //starting number
  8. int divisor; //number used to find prime numbers
  9. int nonprime_num = 1; //accumulator for non prime numbers
  10. int end_num = 50; //ending number
  11.  
  12. int main()
  13. {
  14.     for(start_num = 1; start_num <= end_num; start_num++)
  15.     {
  16.         for(divisor = 2; divisor <= start_num / 2; divisor++)
  17.         {
  18.             if (start_num % divisor != 0) continue;
  19.             nonprime_num = nonprime_num + 1;
  20.             cout << "not prime: " << start_num << "\n";
  21.             break;
  22.         }
  23.     }
  24.     cout << "Number of prime numbers: " << (end_num - nonprime_num) << "\n";
  25.     cout << "Number of non-prime numbers: " << nonprime_num << "\n";
  26.    
  27.     cin.get();
  28.     return 0;
  29. }


By the way, two comments on your programming style:
1. Why use global variables? As a general rule, globals are evil, and in this case there is no need. You only have one function, main, so declare the variables as local variables inside main.
2. Usually you should use endl at the end of the cout statement as opposed to "\n", because cin/cout is buffered and so you want to make sure the buffer is flushed to the screen. (This one is very minor.)

Reply With Quote
  #3  
Old November 5th, 2006, 09:18 AM
enp522 enp522 is offline
Registered User
Dev Articles Newbie (0 - 499 posts)
 
Join Date: Nov 2006
Posts: 4 enp522 User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 42 m 48 sec
Reputation Power: 0
An alternate algorithm

I dont have much to add. But I seem to remember learning a faster way to find prime numbers in my Discrete Math class. I believe it has something to do with the fact that every non prime number can be broken down into a series of primes.

So 28, which is not prime, breaks down to 2*2*7.

So when you're testing 28 to see if it's prime all you must do is divide it by the primes you have discovered thus far which are less than 1/2 of 28.

If it is divisible by any of those primes then it is not prime.

I'm not sure if this is exactly the algorithm. You might have to check all primes up to the square root of the number you're testing for.

Good luck on your program.

Reply With Quote
Reply

Viewing: Dev Articles Community ForumsProgrammingC/C++ Help > Program to find prime numbers


Developer Shed Advertisers and Affiliates


Thread Tools  Search this Thread 
Search this Thread:

Advanced Search
Display Modes  Rate This Thread 
Rate This Thread:


Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
View Your Warnings | New Posts | Latest News | Latest Threads | Shoutbox
Forum Jump

Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
  
 


Powered by: vBulletin Version 3.0.5
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.

© 2003-2018 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap