help, trying to find prime number

This is a discussion on help, trying to find prime number within the C++ Programming forums, part of the General Programming Boards category; ok, i just started working with c++, and im doing a basic project trying to find all the prime numbers ...

  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
    21,422
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    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,294
    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
    21,422
    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.)
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    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
    21,422
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Page 1 of 2 12 LastLast
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, 04:56 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21