Thread: Anyone want to look over my 'extreme newbie' code to calculate prime numbers?

  1. #1
    Registered User
    Join Date
    Nov 2005
    Posts
    7

    Lightbulb Anyone want to look over my 'extreme newbie' code to calculate prime numbers?

    I hope its okay to post this here, the forum section is simply "C++ programming" so I hope it is ok here with all the other (much more advanced) topics. There didn't seem to be a 'newbie' area.

    This is probably laughable to the vast majority of you, but hey?

    I enjoyed doing it and it seems to work just fine

    If anyone wants to tell me how I SHOULD have done it, absolutely fine. If noone wants to bother reading it (I appreciate, that it is probably akin to writing ones name for most of you), also absolutely fine I just thought I would post it and see if anyone wants to comment.

    Code:
    /* A Simple Program for caluclating prime numbers
    
    (my first attempt at programming beyond the "Hello World" phase)
    
    USAGE
    *****
    
    Defines and counts prime numbers between 1 and upper_limit, where upper_limit is set by the user.
    
    LIMITATIONS
    ***********
    
    Presumably, there must be some? I did not test with a truly huge upper limit 
    so at present I am unaware as to what they are.
    
    Notes
    *****
    
    This is my very first attempt to code something of entirely my own work. I
    am approximately 200 pages into my 1st C++ primer (Practical C++ by Steve Ouline - second hand no less!) and was getting a little bored with his programming exercises. I therefore set my own for this evening. 
    
    I have never seen any source code for a program to calculate prime numbers. I have no idea if this way is efficient or inefficient (given my lack of knowledge and experience one would assume the latter!).
    
    If this program/source code ever sees happens to see the light of day any comments -  critical, constuctive or otherwise would be very gratefully recieved.
    
    
    Author
    ******
    
    Stewart Robertson (Iclestu)
    [email protected]
    
    Version
    *******
    0.1	2nd November 2005
    
    Licence??
    *********
    
    Yeah right!!??!!
    
    If anything is of any remote use to anyone (it IS possible - perhaps it's so badly written that a lecturer or tutor wants it as an example of what not to do!), please feel free to copy, distribute, amend, butcher, destroy, recreate, emulate and re-copy to your heart's content.
    */
    
    #include <iostream.h>
    
    long int upper_limit;	//highest number progrm will go up to (inputed by user)
    long int current;	//current number 'on test'
    int counter;		//keeps count of number of primes
    
    int prime_test(long int candidate)//Function returns 1 if candidate is prime, 0 otherwise
    {
    	int divisor;			//stores current divisor
    	int return_value;		//stores return value (should be 1 if no divisor is found) otherwise 0
    
    	return_value = 1;		// will only be amended to 0 if a divisor is found
    	divisor = 2;			// initialise
    
    	if ((candidate != 1) && (candidate != 2)) // no need to test these 2 and they don't quite fit into the main loop
    	{
    		while (divisor <= (candidate/2))
    		{
    			if ((candidate % divisor) == 0)
    			{
    				return_value = 0;
    				break;			//no sense continuing the WHILE loop if even 1 divisor is found
    			}
    			else
    			{
    			divisor++;	// It seems long-winded to test every number up to "candidate/2", but how else?
    			continue;
    			}
    		}
    	}
    
    return (return_value);
    }
    int main()
    {
    	/*Intro*/
    
    	cout << "Prime Version 0.1\n";
    	cout << "Author: Stewart Robertson (Iclestu)\n";
    	cout << "Comments to: [email protected]\n\n";
    
    
    
    	/*This Section to obtain upper limit from user*/
    
    	cout << "Please enter upper limit to calculate to:";
    	cin >> upper_limit;
    	cout << "\n";
    
    	/*This section is main loop*/
    
    	current = 1;	//might as well start at the beginning :)
    
    	while (current <= upper_limit)
    	{	
    		if (prime_test(current) == 1)	//test if prime
    		{
    			cout << current << "\n";	//if so output number
    			counter++;			// and increment counter
    		}
    		current++;
    		
    	}
    	
    
    	/* this section to close and display info*/
    	
    	cout << "\n" << counter << " prime numbers found up to " << upper_limit;
    	cout << ".\n\n\n";
    	cout << "Prime Version 0.1\n";
    	cout << "Author: Stewart Robertson (Iclestu)\n";
    	cout << "Comments to: [email protected]\n\n";
    
    }

  2. #2
    Deprecated Dae's Avatar
    Join Date
    Oct 2004
    Location
    Canada
    Posts
    1,034
    1. Why does a book made in 2003, thats highly rated, have you using #include <iostream.h>. The standard is to use <iostream> and the namespace std. You have 2nd edition right?

    2. You could prototype the function prime_test, thats a pretty standard thing to do, keep your int main as far up to the top as possible (under includes, and prototypes). Look in index of book for prototype if you don't know.

    The structure looks good, good formatting, but I didnt check to see if it works - so no comment on that.
    Warning: Have doubt in anything I post.

    GCC 4.5, Boost 1.40, Code::Blocks 8.02, Ubuntu 9.10 010001000110000101100101

  3. #3
    Registered User
    Join Date
    Nov 2005
    Posts
    7
    Quote Originally Posted by Dae
    1. Why does a book made in 2003, thats highly rated, have you using #include <iostream.h>. The standard is to use <iostream> and the namespace std. You have 2nd edition right?
    Ahh, I have an earlier edition - Copyright 1995 (I got it for next to nothing second hand).

    I assumed that it would be ok as I am new to this and not doing any serious study (just enjoying finding out how things work). I had no idea that the book was highly rated until you replied. Presumably the newer version you refer to will be updated, I will maybe shell out for a new book depending how I go.

    In any event, thank you very much for such a speedy and positive reply. You have intensified my motivation and enthusiasm with your kind comments.

    I will look into prototyping as you have suggested.

  4. #4
    ---
    Join Date
    May 2004
    Posts
    1,379
    You don't need to prototype the function especially for such a small program.

  5. #5
    Deprecated Dae's Avatar
    Join Date
    Oct 2004
    Location
    Canada
    Posts
    1,034
    ... 1995? Sheesh. All editions have different ratings, ed. 2 could get a 5 star rating and ed. 3 could get 1, while ed. 4 gets 4. It depends on the author mostly, and the highly rated 2003 one is from the same author so thats good.

    If you don't mind reading off the computer, I would read an online free ebook and not such an old book. Regardless of the author, thats just too old. Note: I dont mean that literally.. just its probably not as heavy on OOP than on procedurial coding than a newer one would (I assume), besides it being behind on some standards.

    I would try this one http://www.planetpdf.com//article.asp?contentid=6634&ra - although its dated 2001, which is still pretty old when you get into certain topics.

    Also, you would get further if you had a good book to start with - more enjoyable, understand it better, less chance of quitting, better chance of liking it, etc. - Accelerated C++

    You don't need to prototype the function especially for such a small program.
    Thats right its not necessary, as I implied, but was just pointing it out.
    Last edited by Dae; 11-02-2005 at 06:13 PM.
    Warning: Have doubt in anything I post.

    GCC 4.5, Boost 1.40, Code::Blocks 8.02, Ubuntu 9.10 010001000110000101100101

  6. #6
    Amazingly beautiful user.
    Join Date
    Jul 2005
    Location
    If you knew I'd have to kill you
    Posts
    254
    I found a much faster way of doing this a while back.
    Create an array of bools, with "upper_limit" elements, with each one equal to 1.
    Then, for each number from 2 to upper_limit, if it is equal to 1, go up by it, setting each value above it, which is a multiple of it equal to 1.

    let me show you my code, it will make more sense.

    Code:
    #include <iostream>
    #include <time.h>
    #include <stdio.h>
    const unsigned int max=100000;
    
    int main(int argc,char* argv[])
    {
            float t,c;
            bool* prime = new bool[max];
            for (unsigned int ctest = 0; ctest < max; ctest++)
            {
                    prime[ctest]=1;
            }
            c=clock();
            for (unsigned int ctest = 2; ctest < max; ctest++)
            {
                    if (prime[ctest]==1)
                    {
                            for (int citer = ctest*2; citer < max; citer+=ctest)
                            {
                                    prime[citer]=0;
                            }
                    }
            }
            int pnum=0;
            for (unsigned int ctest = 0; ctest < max; ctest++)
            {
                    if (prime[ctest]==1)
                    {
                            std::cout << ctest << std::endl;
                            pnum++;
                    }
            }
            t=clock()-c;
            t=t/(float)CLOCKS_PER_SEC;
            std::cout << "It took " << t << "seconds" << std::endl;
            std::cout << "There are: " << pnum << " primes below " << max << std::endl;
    }
    Basically, you cross out all the multiples of two. Then all the multiples of three. Then, because four has already been crossed out, you don't cross out its multiples (as they would have already been crossed out by two). Just continue this. Thus, multiples of multiples are not tested.

    Its reasonably fast, as it takes it 0.05 seconds to find all primes below 100,000 on my machine.

    Its possible to optimize my code further using pointer tricks, but I'll keep it simple for you.

    Also, if you do not include the printing of the results to std::cout within the timing, it is so fast that it takes 0 seconds according to the timer I am using.
    Last edited by CrazyNorman; 11-02-2005 at 06:22 PM.
    Programming Your Mom. http://www.dandongs.com/

  7. #7
    Registered User
    Join Date
    Nov 2005
    Posts
    7
    Thats great!

    I was thinking I had picked myself up a bargain and there are FREE ebooks on C++ out there! Never really considered that as a possibility let alone an option. I will definately look into that.

    With regard to the other one, I really appreciate the recommendation, but obviously actually spending some money requires a little more deliberation. Still, its my birthday in a few weeks, perhaps I could drop a few hints. How do you drop C++ textbooks into a conversation over dinner???

    Thanks very much again

  8. #8
    Amazingly beautiful user.
    Join Date
    Jul 2005
    Location
    If you knew I'd have to kill you
    Posts
    254
    Althought at low upper bounds, your algorithm is sufficient, if you want to find all of the primes below say, 100,000,000, mine takes 15 seconds while yours takes much longer (I stopped timing at 2 minute 30 seconds).

    Remember, when designing algorithms in C++, always take advantage of the low access of times of arrays and pointers.
    Programming Your Mom. http://www.dandongs.com/

  9. #9
    Registered User
    Join Date
    Nov 2005
    Posts
    7
    Quote Originally Posted by CrazyNorman
    Its reasonably fast, as it takes it 0.05 seconds to find all primes below 100,000 on my machine.
    That's reasonably fast???! seems like lightening to me

    I think we can safely say my code is extremely inefficient!

    Quote Originally Posted by CrazyNorman
    Its possible to optimize my code further using pointer tricks, but I'll keep it simple for you.
    not reached the chapter on pointers yet To be honest a fair amount of your code is over my head at the moment. However, I really greatly appreciate you replying and showing me how it SHOULD be done. I have copied your code and will revisit it as my knowledge grows.

    Thanks very much

  10. #10
    Amazingly beautiful user.
    Join Date
    Jul 2005
    Location
    If you knew I'd have to kill you
    Posts
    254
    If the algorithm makes sense, I'll explain my code too you. You might be able to understand it.
    I'll pull out some of the fluff (the timer in specific).
    Code:
            /*This will make more sense in later chapters.
            What we do is basically create a group of variables in memory.
            This first of these variables is "prime[0]", the last being "prime[max - 1]"
            Thus, you can treat each "prime[number]" as a seperate variable.
            */
            bool* prime = new bool[max];
            // We loop through each element (variable) in our array, and set it equal to 1
            for (int ctest = 0; ctest < max; ctest++)
            {
                    prime[ctest]=1;
            }
            //This is the heart of our prime finder
            for (int ctest = 2; ctest < max; ctest++)  //Loop from two to the upper limit.
            {
                    if (prime[ctest]==1) //Is the number we are testing (ctest) a multiple of any previous numbers?
                    {
                            for (int citer = ctest*2; citer < max; citer+=ctest) //If not, check of all of the multiples of it
                            {
                                    prime[citer]=0;
                            }
                    }
            }
            int pnum=0;
            for (unsigned int ctest = 0; ctest < max; ctest++)
            {
                    if (prime[ctest]==1) //All of the numbers still equal to 1 are prime.
                    {
                            std::cout << ctest << std::endl;
                            pnum++;
                    }
            }
            std::cout << "There are: " << pnum << " primes below " << max << std::endl;
    Programming Your Mom. http://www.dandongs.com/

  11. #11
    Deprecated Dae's Avatar
    Join Date
    Oct 2004
    Location
    Canada
    Posts
    1,034
    Quote Originally Posted by iclestu
    How do you drop C++ textbooks into a conversation over dinner???
    Any parent would be happy to hear their son/daughter may be considering a career, mention you might have found the career for you and blah blah learn c++ blah blah gotta order it off the internet blah blah (unless you have a barnes and nobles near you).

    Also, when designing a program to do an algorithm.. theres probably already many already designed to do it efficiently/effectively. Even if its a math algorithm, it can be easily converted to C++, so you could search at google for "algorithm *thing to do here*" when dealing with math/physics/3dgame algorithms.
    Warning: Have doubt in anything I post.

    GCC 4.5, Boost 1.40, Code::Blocks 8.02, Ubuntu 9.10 010001000110000101100101

  12. #12
    Deprecated Dae's Avatar
    Join Date
    Oct 2004
    Location
    Canada
    Posts
    1,034
    Quote Originally Posted by iclestu
    How do you drop C++ textbooks into a conversation over dinner???
    Any parent would be happy to hear their son/daughter may be considering a career, mention you might have found the career for you and blah blah learn c++ blah blah gotta order it off the internet blah blah (unless you have a barnes and nobles near you).

    Also, when designing a program to do an algorithm.. theres probably already many designed to do it efficiently/effectively. Even if its a math algorithm, it can be easily converted to C++, so you could search at google for "algorithm *thing to do here*" when dealing with math/physics/3dgame algorithms.

    I think I spent 3-4 hours making a program to prime factor a root, with someodd 50 lines of code; instead I could have searched google for a math equation and had it in done in 5 minutes, with 5 lines of code.
    Warning: Have doubt in anything I post.

    GCC 4.5, Boost 1.40, Code::Blocks 8.02, Ubuntu 9.10 010001000110000101100101

  13. #13
    Registered User
    Join Date
    Nov 2005
    Posts
    7
    Quote Originally Posted by CrazyNorman
    If the algorithm makes sense, I'll explain my code too you. You might be able to understand it.
    I'll pull out some of the fluff (the timer in specific).

    I've got you now - I think!

    Thanks for taking the trouble to explain it to me. Looks like I've got lots more learning to do

  14. #14
    Registered User
    Join Date
    Nov 2005
    Posts
    7
    Any parent would be happy to hear their son/daughter may be considering a career, mention you might have found the career for you and blah blah learn c++ blah blah gotta order it off the internet blah blah (unless you have a barnes and nobles near you).
    Ahhh, if only it were the good old days of persueding loving, devoted parents. Now it's the task of persueding an equally loving and devoted, but somewhat more sceptical, wife. An altogether different scenario!

    Also, when designing a program to do an algorithm.. theres probably already many designed to do it efficiently/effectively. Even if its a math algorithm, it can be easily converted to C++, so you could search at google for "algorithm *thing to do here*" when dealing with math/physics/3dgame algorithms.
    Thanks for the info, but in this circumstance I don't think i would have learned as much as I have done by trying it and only then trying to find out the quicker/better way. That said, i am sure it would be helpful to look at the 'expert's code once I have had a bash myself and I appreciate the 'know-how' you have provided on finding that code.

    Correct me if I am wrong, but I think it would be fair to say that for you or experienced programmers looking up sections of code to include in a program will save you time, whereas for me, whilst learning, all it would do is save me the trouble of learning at all.

  15. #15
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    >> Correct me if I am wrong, but I think it would be fair to say that for you or experienced programmers looking up sections of code to include in a program will save you time, whereas for me, whilst learning, all it would do is save me the trouble of learning at all.

    Sometimes learning which existing tools are right for the job is more important than learning how to do it yourself. And once you find the right tool, you can always spend time analyzing it and learning why it does a good job. That doesn't apply as much to finding prime numbers, since it is doubtful you will ever really need to do that except as a learning experience, but it is still something to think about.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Prime numbers
    By Lazy Student in forum C Programming
    Replies: 12
    Last Post: 05-14-2002, 05:53 AM
  2. Prime Numbers
    By cmangel518 in forum C++ Programming
    Replies: 13
    Last Post: 04-30-2002, 11:51 PM
  3. Homework help
    By Jigsaw in forum C++ Programming
    Replies: 2
    Last Post: 03-06-2002, 05:56 PM
  4. Prime Numbers
    By Korn1699 in forum C++ Programming
    Replies: 7
    Last Post: 11-03-2001, 09:52 PM