Thread: help, trying to find prime number

  1. #1
    Registered User
    Join Date
    May 2009
    Posts
    16

    help, trying to find prime number

    ok, i just started working with c++, and im doing a basic project trying to find all the prime numbers under 100.

    here is what i have right now:
    Code:
    /*variables needed num1, num2, index.
    if num1 % num2 = 0 index++, if index = 0 print num1. */
    #include <iostream>
    using namespace std;
    
    int main ()
    {
    	int num1, num2;// the 2 numbers we divide to find the remainder
    	int remainder, index=0; // remainder determines if the number is prime or not
    
    	for(num1=1; num1 <= 100; num1++) // we take each number under 100
    	{
    		index = 0;// we reset index back to 0
    		for(num2=1; num2< num1; num2++) //and mod it be each number lower than itself
    		{
    			remainder = num1%num2; // find out the remainder of it
    			if(remainder != 0) // and if there is none
    			{
    				index++; // we increment index once.
    			}
    		}
    		if (index != 0) // if we didnt increment index during that operation
    		{	
    			cout << num1 << " is a prime number\n"; // it means that num1 is a prime number
    		}
    	}
    	cin.get();
    	return 0;
    }

    issue is, i get 77-100 as prime numbers, nothing before 77 at all, and not only the prime numbers between 77 and 100, but rather 77, 78, 79, 80, etc.

    i know i probably made a logic error somewhere along the line.

    can someone please look through the code tell me where im wrong. because ive been staring at it for an hour w/ no luck so far.

  2. #2
    Registered User
    Join Date
    Mar 2009
    Posts
    344
    if (index != 0) // if we didnt increment index during that operation


    Comment doesn't match the code here.

  3. #3
    Registered User
    Join Date
    May 2009
    Posts
    16
    Quote Originally Posted by KCfromNC View Post
    if (index != 0) // if we didnt increment index during that operation


    Comment doesn't match the code here.
    hmm, thats cuz i messed w/ it a lot before finally posting here.


    i still have the problem tho, i tried lowering my range to 100 and i get 3-10 as prime numbers, when clearly numbers like 4, and 6 are not, and 1-3 nothing shows. im still confused.


    here is what i have, yet again.

    Code:
    /*variables needed num1, num2, index.
    if num1 % num2 = 0 index++, if index = 0 print num1. */
    #include <iostream>
    using namespace std;
    
    int main ()
    {
    	int num1, num2;// the 2 numbers we divide to find the remainder
    	int remainder=0, index=0; // remainder determines if the number is prime or not
    
    	for(num1=1; num1 <= 10; num1++) // we take each number under 100
    	{
    		cout << "after first for loop num1 is " << num1 <<endl;
    		cout << "after first for loop index is " << index <<endl;
    		index = 0;// we reset index back to 0
    		for(num2=1; num2<num1; num2++) //and mod it be each number lower than itself
    		{
    			remainder = num1%num2; // find out the remainder of it
    			cout << "after second for loop num2 is " << num2 << endl;
    			cout << "after second for loop remainder is: " << remainder << endl;		
    			if(remainder == 0) // and if there is none
    			{
    				++index; // we increment index once.
    			cout << "after first if index is " << index <<endl;
    			}
    		}
    		if (index == 0) // if we didnt increment index during that operation
    		{	
    			cout << "after second if num1 is " << num1 <<endl;
    			cout << "after second if index is " << index <<endl;
    			cout << "after second if num2 is " << num2 << endl;
    			cout << "after second if remainder is: " << remainder << endl;
    			cout << num1 << " is a prime number\n\n\n"; // it means that num1 is a prime number
    		}
    	}
    	cin.get();
    	return 0;

    still havent gotten it to work, i have cout statements there because i want to see where the issue is, none of the couts from if(index == o) ever print for a range from 1-10. so im confused why that is.


    thats the source code, here is the output:

    Code:
    after second for loop remainder is: 0
    
    after first if index is 1
    
    after first for loop num1 is 3
    after first for loop index is 1
    
    after second for loop num2 is 1
    after second for loop remainder is: 0
    
    after first if index is 1
    
    after second for loop num2 is 2
    after second for loop remainder is: 1
    
    after first for loop num1 is 4
    after first for loop index is 1
    
    after second for loop num2 is 1
    after second for loop remainder is: 0
    
    after first if index is 1
    
    after second for loop num2 is 2
    after second for loop remainder is: 0
    
    after first if index is 2
    
    after second for loop num2 is 3
    after second for loop remainder is: 1
    
    after first for loop num1 is 5
    after first for loop index is 2
    
    after second for loop num2 is 1
    after second for loop remainder is: 0
    
    after first if index is 1
    
    after second for loop num2 is 2
    after second for loop remainder is: 1
    
    after second for loop num2 is 3
    after second for loop remainder is: 2
    
    after second for loop num2 is 4
    after second for loop remainder is: 1
    
    after first for loop num1 is 6
    after first for loop index is 1
    
    after second for loop num2 is 1
    after second for loop remainder is: 0
    
    after first if index is 1
    
    after second for loop num2 is 2
    after second for loop remainder is: 0
    
    after first if index is 2
    
    after second for loop num2 is 3
    after second for loop remainder is: 0
    
    after first if index is 3
    
    after second for loop num2 is 4
    after second for loop remainder is: 2
    
    after second for loop num2 is 5
    after second for loop remainder is: 1
    
    after first for loop num1 is 7
    after first for loop index is 3
    
    after second for loop num2 is 1
    after second for loop remainder is: 0
    
    after first if index is 1
    
    after second for loop num2 is 2
    after second for loop remainder is: 1
    
    after second for loop num2 is 3
    after second for loop remainder is: 1
    
    after second for loop num2 is 4
    after second for loop remainder is: 3
    
    after second for loop num2 is 5
    after second for loop remainder is: 2
    
    after second for loop num2 is 6
    after second for loop remainder is: 1
    
    after first for loop num1 is 8
    after first for loop index is 1
    
    after second for loop num2 is 1
    after second for loop remainder is: 0
    
    after first if index is 1
    
    after second for loop num2 is 2
    after second for loop remainder is: 0
    
    after first if index is 2
    
    after second for loop num2 is 3
    after second for loop remainder is: 2
    
    after second for loop num2 is 4
    after second for loop remainder is: 0
    
    after first if index is 3
    
    after second for loop num2 is 5
    after second for loop remainder is: 3
    
    after second for loop num2 is 6
    after second for loop remainder is: 2
    
    after second for loop num2 is 7
    after second for loop remainder is: 1
    
    after first for loop num1 is 9
    after first for loop index is 3
    
    after second for loop num2 is 1
    after second for loop remainder is: 0
    
    after first if index is 1
    
    after second for loop num2 is 2
    after second for loop remainder is: 1
    
    after second for loop num2 is 3
    after second for loop remainder is: 0
    
    after first if index is 2
    
    after second for loop num2 is 4
    after second for loop remainder is: 1
    
    after second for loop num2 is 5
    after second for loop remainder is: 4
    
    after second for loop num2 is 6
    after second for loop remainder is: 3
    
    after second for loop num2 is 7
    after second for loop remainder is: 2
    
    after second for loop num2 is 8
    after second for loop remainder is: 1
    
    after first for loop num1 is 10
    after first for loop index is 2
    
    after second for loop num2 is 1
    after second for loop remainder is: 0
    
    after first if index is 1
    
    after second for loop num2 is 2
    after second for loop remainder is: 0
    
    after first if index is 2
    
    after second for loop num2 is 3
    after second for loop remainder is: 1
    
    after second for loop num2 is 4
    after second for loop remainder is: 2
    
    after second for loop num2 is 5
    after second for loop remainder is: 0
    
    after first if index is 3
    
    after second for loop num2 is 6
    after second for loop remainder is: 4
    
    after second for loop num2 is 7
    after second for loop remainder is: 3
    
    after second for loop num2 is 8
    after second for loop remainder is: 2
    
    after second for loop num2 is 9
    after second for loop remainder is: 1
    Last edited by vampirekid.13; 05-01-2009 at 01:14 PM.

  4. #4
    The larch
    Join Date
    May 2006
    Posts
    3,573
    I guess your problem is that all numbers are divisible by 1.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  5. #5
    Registered User
    Join Date
    May 2009
    Posts
    16
    Quote Originally Posted by anon View Post
    I guess your problem is that all numbers are divisible by 1.
    that was kinda it. i changed it so if index is 1 its a prime number, and it comes out with

    2
    3
    5
    7

    so i need to figure out a way to exclude 2 and im good.


    wait, 2 is a prime number right? its divisible by 1 and 2 only. so i guess its working fine now. i think.


    AWESOME it works, thats great, thank you for the help. im off to find the next prime number now.
    Last edited by vampirekid.13; 05-01-2009 at 01:47 PM.

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    Quote Originally Posted by vampirekid.13
    so i need to figure out a way to exclude 2 and im good.
    But 2 is a prime number.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Registered User
    Join Date
    May 2009
    Posts
    16
    Quote Originally Posted by laserlight View Post
    But 2 is a prime number.
    yea, i realized that shortly after making myself look stupid on a public c++ board. heh.


    also now i need to find a way to include 1 in all of it, but im lazy and i think im just going ot hardcode it in and not worry about it.

  8. #8
    Banned ಠ_ಠ's Avatar
    Join Date
    Mar 2009
    Posts
    687
    you could count how many times the remainder was 0

    If it's more than 2 then it's not a prime number
    ╔╗╔══╦╗
    ║║║╔╗║║
    ║╚╣╚╝║╚╗
    ╚═╩══╩═╝

  9. #9
    Registered User
    Join Date
    May 2009
    Posts
    16
    Quote Originally Posted by ಠ_ಠ View Post
    you could count how many times the remainder was 0

    If it's more than 2 then it's not a prime number
    yea, thats what i ended up doing. and it worked, im runing it now trying to find all the prime numbers less than 4billion haha


    i kinda regret not saving them to a file or anything, but im doing it just for fun anyway.


    its been a few hrs now, i am @ 1 million....i got a long time left to go.

  10. #10
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by vampirekid.13 View Post
    yea, thats what i ended up doing. and it worked, im runing it now trying to find all the prime numbers less than 4billion haha


    i kinda regret not saving them to a file or anything, but im doing it just for fun anyway.


    its been a few hrs now, i am @ 1 million....i got a long time left to go.
    That's horridly slow.
    You could stop it, make a few improvements and run it again, and have it catch up to where is was in less than 30 seconds.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  11. #11
    Registered User
    Join Date
    Jan 2009
    Location
    Australia
    Posts
    375
    I agree with iMalc.

    You could try implementing The Sieve of Eratosthenes to make it a lot faster. Although it will also use a lot more memory.

  12. #12
    C / C++
    Join Date
    Jan 2006
    Location
    The Netherlands
    Posts
    312
    My time for primes from 2 to 1 Million is about 2.6 secs. ('real' return value from the 'time' command).

    To improve your speed, you can, for example:
    - break out of the inner loop when remainder == 0, instead of further looping;
    - calculate num2 up to sqrt(num1);
    - skip the even numbers in the outer (and inner) loops, they won't be primes anyway.
    Operating Systems:
    - Ubuntu 9.04
    - XP

    Compiler: gcc

  13. #13
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    Quote Originally Posted by Ideswa
    My time for primes from 2 to 1 Million is about 2.6 secs. ('real' return value from the 'time' command).
    Interesting. I just tested my "perfect" trial division submission to our prime number generation contest, and my program found the primes less than 1 million in the order of 0.2 seconds. So, it is either a case of my computer being much faster than yours, or "perfect" trial division with primes really is so much faster than trial division with odd numbers. (Or both.)
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  14. #14
    C / C++
    Join Date
    Jan 2006
    Location
    The Netherlands
    Posts
    312
    Nice! I haven't used any of the fast prime algorithms yet. But I'm having a lack of time because I have my final exams in 17 days and I have to code some PHP websites too .
    Operating Systems:
    - Ubuntu 9.04
    - XP

    Compiler: gcc

  15. #15
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    hmm... there might be another reason: did you print out all the primes found? When I changed my implementation to do that (since that is what vampirekid.13 did, after all), the time taken was in the neighbourhood of 2.25 seconds.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. prime number program with function
    By mackieinva in forum C Programming
    Replies: 17
    Last Post: 09-20-2007, 08:36 AM
  2. for loop to find prime numbers
    By 1rwhites in forum C Programming
    Replies: 11
    Last Post: 10-21-2005, 10:37 AM
  3. Prime Number stops after 29, but why?
    By Daveo in forum C Programming
    Replies: 22
    Last Post: 09-17-2004, 10:55 AM
  4. prime # query
    By alokin in forum C Programming
    Replies: 8
    Last Post: 09-04-2002, 11:50 AM
  5. Homework help
    By Jigsaw in forum C++ Programming
    Replies: 2
    Last Post: 03-06-2002, 05:56 PM