Optimize the prime-ness for testing

This is a discussion on Optimize the prime-ness for testing within the C++ Programming forums, part of the General Programming Boards category; Code: #include <iostream> #include <math.h> using namespace std; int main() { // Declare four variables n, i, an, and is_prime ...

  1. #1
    Registered User
    Join Date
    Sep 2008
    Posts
    65

    Optimize the prime-ness for testing

    Code:
    #include <iostream>
    #include <math.h>
    
    using namespace std;
    
    int main()
    {
        // Declare four variables n, i, an, and is_prime respectively.
        int n;        // Number to test for primeness
        int i;        // Loop counter
        int is_prime;
    
        // Assuming that the number is prime until proven otherwise
        is_prime = true;
    
        // Prompt user input
        cout << "Please enter a number for the primeness number test: ";
        cin >> n;
    
        // Test for prime-ness by checking for divisibility
        // by all whole numbers from 2 to sqrt(n)
        i = 2;
        while(i <= sqrt(static_cast<double>(n))){
            if(n &#37; i == 0){
                is_prime = false;
                i++;
            }
        }
    
        if(is_prime){
            cout << "The number is prime." << endl;
        }else{
            cout << "The number is not prime.";
        }
    
        return 0;
    }
    Let me tell you what I really hate programming, for real...Really hate it. But if you wanna create a video game or gain access to video gaming industry, you must know or have some decent programming skills. No choice.

    Anyway, here is the exercise question
    2.4.1 Optimize the program further by calculating the square root of n just once rather than over and over as was done in the example. To perform this optimization, you will need to declare another variable and set it to the square root of n. The type should be double. Write a complete program that includes this optimization.

    Well...I have found this kinda confusing and for my level of computer programming, it is hard for me to do it. Since while loop is for repetition, unless you use for loop or other methods, there is no way, in my opinion, to calculate the square root once with the use of while loop...I really need help here.

    Code:
    #include <iostream>
    #include <math.h>
    
    using namespace std;
    
    int main()
    {
        // Declare four variables n, i, an, and is_prime respectively.
        int n;        // Number to test for primeness
        int i;        // Loop counter
        double an;    // Optimization
        int is_prime;
    
        // Assuming that the number is prime until proven otherwise
        is_prime = true;
    
        // Prompt user input
        cout << "Please enter a number for the primeness number test: ";
        cin >> n;
    
        // Test for prime-ness by checking for divisibility
        // by all whole numbers from 2 to sqrt(n)
        i = 2;
        an = n;
        while(i <= sqrt(static_cast<double>(n))){
            if(n % i == 0){
                is_prime = false;
                i++;
            }
        }
    
        if(is_prime){
            cout << "The number is prime." << endl;
        }else{
            cout << "The number is not prime.";
        }
    
        return 0;
    }
    The loop executed without problems, but it didn't work the way I want it to be. Besides, the input of user doesn't function at all.

  2. #2
    Kiss the monkey. CodeMonkey's Avatar
    Join Date
    Sep 2001
    Posts
    902
    The square root might be calculated only once anyway.

    Look where the square root is. It is part of a loop, which will run many times. Instead, make some variable before the loop and set it equal to the square root. Then you can just put the name of that variable in the loop, as if it were a compile-time constant. Then the sqrt() function is called only once, right?
    Right now, every time you evaluate the conditional in the while() loop, you call the function sqrt(). If, instead, you simply had some variable there, then the computer would instead just look at some value at a memory address. No function necessary.

    Also, #include<cmath> rather than math.h

    And how is the input not working?
    "If you tell the truth, you don't have to remember anything"
    -Mark Twain

  3. #3
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    So you could, and I realize that this is crazy talk, but you could actually read the question. You even boldfaced it in your post. Read it:


    you will need to declare another variable and set it to the square root of n. The type should be double.
    You are supposed to (1) declare a variable of type double and (2) set it to the square root of n. Notice the complete absence of loops of any kind. Note the complete absence of any kind of casting. You need to (1) declare a variable and (2) set it equal to something.

  4. #4
    Registered User
    Join Date
    Feb 2003
    Posts
    595
    There's nothing wrong with the input. Your program is going into an infinite loop whenever you input an odd number greater than 3 because you only increment i when the if condition is true.

    The "i++" should be outside of the if {} block.
    Last edited by R.Stiltskin; 12-14-2008 at 12:59 AM.

  5. #5
    Registered User
    Join Date
    Sep 2008
    Posts
    65
    Yes...It worked...I guess the input didn't work is because of the syntax error by putting the i++ inside the curly braces. Besides as for setting the variable to something and declare it, I did it, which is double an...I am not sure if I am correct...I do not really understand the question if it is stated in the question that "set it to the square root of n" is not what I did "double an", which is declared and set it to "n".

  6. #6
    Registered User
    Join Date
    Jun 2005
    Posts
    6,259
    Quote Originally Posted by kenryuakuma View Post
    Yes...It worked...I guess the input didn't work is because of the syntax error by putting the i++ inside the curly braces.
    Incrementing i "inside the curly braces" is not a syntax error. It is a programmer error (in the sense that the programmer has written code that does not do what is wanted). The syntax is perfectly correct.
    Quote Originally Posted by kenryuakuma View Post
    Besides as for setting the variable to something and declare it, I did it, which is double an...I am not sure if I am correct...I do not really understand the question if it is stated in the question that "set it to the square root of n" is not what I did "double an", which is declared and set it to "n".
    Before the loop you have to set an to be equal to something. Then, in the loop, compare the value of i with the value of an.

    Your basic problem is that you are expecting the compiler to magically do what is required, based on a partial guess as to what is required. In reality, you have to tell the compiler in an unambiguous manner using source code to do what is required.

    Compilers do not read minds of programmers or the authors of coding exercises. If you give a compiler incorrect source code, the compiler will happily generate an executable that produces incorrect results.

  7. #7
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    Quote Originally Posted by kenryuakuma View Post
    Let me tell you what I really hate programming, for real...Really hate it. But if you wanna create a video game or gain access to video gaming industry, you must know or have some decent programming skills. No choice.
    Like a surgeon that faints at the sight of blood? Seriously, if you hate programming don't even bother getting into the software development industry, as I'm happy to tell you its mostly about programming. You won't make a good manager either, because you loath the programming you will not do an effective job of managing progrmmers, so basically you have no future in the industry and will just take a job away from someone that would enjoy it. You should consider a different career path.
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

  8. #8
    Registered User
    Join Date
    Sep 2008
    Posts
    65
    Quote Originally Posted by abachler View Post
    Like a surgeon that faints at the sight of blood? Seriously, if you hate programming don't even bother getting into the software development industry, as I'm happy to tell you its mostly about programming. You won't make a good manager either, because you loath the programming you will not do an effective job of managing progrmmers, so basically you have no future in the industry and will just take a job away from someone that would enjoy it. You should consider a different career path.
    I mean because it is hard to learn...I do love it but the main thing is if you don't understand something, and you keep asking for help, I am just afraid that everybody will get annoyed and feel bothered...Because I am really fond of video games...But creating a video game such as those developed and published by CAPCOM or NAMCO, you will need some programming skills. The more sophisticated, the better...I used to take a programming class, of which teacher taught BlueJ sun-Java...and I wasn't really good at that. But in order to accomplish something in my career, video game that's to say, I really need programming...Without which, just like you say, don't even bother.

  9. #9
    Registered User
    Join Date
    Sep 2008
    Posts
    65
    OK this is the code written by a C++ Professional, which is vastly different from any of the beginners including myself. But this is not the code what I want...If somebody could help me with the exercise by completely providing an example with explanation in great details, similar to the code I wrote and stick with while loop rather than for loop, that would be great and really helpful to a noob. I really wanna get past this exercise...The question posted above was extracted from the book recommended by this website named "C++ without fear which was published in 2005 and the second edition was 2007."

    Code:
    #include <iostream>
    
    // math.h is the old C header. Since you are using C++,
    // use the C++ header for math functions
    #include <cmath>
    
    // Most of the original comments are useless because with
    // properly named variables, they wouldn't be needed and/or
    // they don't add any new information about the code.
    
    // Comments should document the 'why' of the code, not
    // the 'how'. The 'how' is already given by the code itself.
    int main()
    {
    	// To declare using namespace globally is considered
    	// bad practise as all the objects and functions you
    	// now use are defaulted to the namespace declared
    	// which can lead to wrong objects/functions being used
    	// Prefer to place the using directive in the same
    	// scope that you intend to use it in like I have
    	// done here or even better, not use it at all and
    	// prefix the objects and functions with the namespace.
    	// Eg. std::cout, std::cin
    
    	// Above all else, do not declare using namespace in
    	// headers as it will default the namespace whenever
    	// you include the header in source files which can
    	//lead to interesting problems.
    
    	using namespace std;
    
    	// Always declare variables with meaningful names, as
    	// close as possible to where you use them (the
    	// compiler can optimise better) and ALWAYS initialise
    	// them on instantiation.
    
    	// Get a number from the keyboard
    	cout << "Enter a number and press ENTER: ";
    
    	int primeNumberTest = 0;
    	cin >> primeNumberTest;
    
    	// Prefer floats over doubles unless you need the extra
    	// precision. Doubles are generally use double
    	// the memory as floats and generally slower to operate on.
    	float primeNumberTestSqrt  = sqrtf( static_cast<float>(primeNumberTest) );
    	int primeNumberTestSqrtFloor = static_cast<int>( floorf(primeNumberTestSqrt) );
    
    	// In C++, there is a boolean base datatype. Using
    	// ints as boolean flags is a left-ism from C
    	bool primeNumberValid = true;
    
    	// Prefer preincrement operators over postincrement
    	// unless you need the previous value in the same
    	// operation. Reference, Item 6 in Exceptional C++ by
    	// Sutter
    	for( int division = 2; division <= primeNumberTestSqrtFloor; ++division )
    	{
    		// Tip: Put const variables and literals on the left
    		// hand side of a equality check. This
    		// prevents typo mistakes such as:
    		// if( blah = 0 )
    		// Which the compiler won't give warnings about
    		// If you put the literal on the left hand side
    		// if( 0 = blah )
    		// The compiler will give an error because it cannot
    		// assign a value to a literal.
    
    		if( 0 == primeNumberTest % division )
    		{
    			// The number inputed is now known not to be
    			// prime, so we break out of the loop and not
    			// waste more CPU time going through the rest
    			// of the loop.
    			primeNumberValid = false;
    			break;
    		}
    	}
    
    	if( primeNumberValid )
    	{
    		cout << "Number is prime.";
    	}
    	else
    	{
    		cout << "Number is not prime.";
    	}
    
    	// No need to call return 0 as the C++ standard states
    	// that if it isn't declared in main(), then it
    	// automatically returns 0 when it reaches the end.
    
    	// Avoid using system function calls. They are not cross
    	// platform. If you want the program to 'stop'
    	// here, put a breakpoint at the closing brace.
    }
    The source code looks awesome and crystal-clear. However, I would like somebody use the code I posted and optimize it and provide me with an explanation in great details about why we have to do this with this statement and how it works.....I will be grateful to that. A noob always need somebody to steer him or her from gotcha. But I am sure by making mistakes repeatedly, one will acquire knowledge and things from there.

  10. #10
    Registered User
    Join Date
    Jun 2005
    Posts
    6,259
    Quote Originally Posted by kenryuakuma View Post
    The source code looks awesome and crystal-clear.
    As a code for a tutorial, yes. For code designed by a professional to be maintained by a professional, the comments are excessive. The best codes I've ever seen required almost no comments, because they used descriptive variable and function names, and did everything in a clear manner.
    Quote Originally Posted by kenryuakuma View Post
    However, I would like somebody use the code I posted and optimize it and provide me with an explanation in great details about why we have to do this with this statement and how it works.....I will be grateful to that.
    I'm sure you would, but that won't happen here - unless you're lucky and catch someone having a "soft in the head" moment. However, it's still your homework, so it is better if you optimise your code, comment it completely, and post it for review. You will learn more that way.
    Quote Originally Posted by kenryuakuma View Post
    A noob always need somebody to steer him or her from gotcha. But I am sure by making mistakes repeatedly, one will acquire knowledge and things from there.
    Maybe so, but that does not justify your request for others to do your homework.

  11. #11
    Registered User
    Join Date
    Sep 2008
    Posts
    65
    Well...Grumpy this is not homework. This is just the exercise question from the book. I am learning this all by myself without anybody's help and without instructors. Before I take some programming classes, I have no have some knowledge of it. That's why this website exists and the book C++ without fear is recommended by this website. The thing is nobody around me will steer me from the gotcha.....It won't be easy to learn this by myself and hence I made a request of that and have somebody optimize it and let me see how it works. SO that I could use it as my reference like ow the code has to be written like this and done like way.

  12. #12
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    The instructions you gave are pretty clear on exactly how to optimize it. I think the lesson is less about optimizing prime number checks and more about reading and figuring out someone elses code, then modifying it for a specific purpose.
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

  13. #13
    Registered User
    Join Date
    Feb 2003
    Posts
    595
    I'll probably get flamed for all the color, but oh well...

    Code:
    #include <iostream>
    #include <math.h>  //post #9 explains how to fix this
    
    //using namespace std;   //post #9 explains about this
    
    int main()
    {
        // Declare four variables n, i, an, and is_prime respectively.
    //Preferably use descriptive names, i.e. numberToTest instead of n
        int n;        // Number to test for primeness
        int i;        // Loop counter
    //The code will be easier to follow if you declare this near to
    //where you use it, particularly since it is used only once.
    //    double an;    // Optimization
        bool is_prime;   //post #9 explains about this
    
        // Assuming that the number is prime until proven otherwise
        is_prime = true;
    
        // Prompt user input
    // note use of std:: instead of "using namespace std;"
        std::cout << "Please enter a number for the primeness number test: ";
        std::cin >> n;
    
        // Test for prime-ness by checking for divisibility
        // by all whole numbers from 2 to sqrt(n)
        i = 2;
    //You seem to have missed the point of the new variable
    // as you are not using it to do anything useful
    //    an = n;
    //The point was, although you may need to USE the square
    //root of n many times in the while loop, you only need to
    // CALCULATE it once for each n.  Making unnecessary calls to
    //the sqrt function wastes processing time.  Therefore,
    //declare a new variable before the while loop, store the
    //square root of n in it, and use that new variable in the while
    //loop's test expression.
        double rootN = sqrt(static_cast<double>(n));
    //    while(i <= sqrt(static_cast<double>(n))){
    //In the while loop, you are searching for a number that divides
    //n evenly.  If you find one, then n is not prime & you set
    //is_prime to false.  If you get all the way to rootN without
    //finding a number that divides n evenly, then n must be prime.
        while(i <= rootN){
            if(n &#37; i == 0){
                is_prime = false;
    //The code in here (in the if{} block) is executed only when
    //the test expression (n % i == 0) is true.  So, if you increment i
    //here, and if 2 doesn't evenly integer-divide the n that you input,
    //the value of i will never change and the while loop
    //continues to test the same n forever.
    //            i++;
    //If you find an i that evenly divides n, then n is not prime and
    //any more testing is a waste of time.  break gets out of the while loop
    //avoiding unnecessary iterations.
                 break;
            }
            ++i;  // post #9 talks about this
        }
    
        if(is_prime){
            std::cout << "The number is prime." << std::endl;
        }else{
            std::cout << "The number is not prime." << std::endl;
        }
    
        return 0;
    }
    Last edited by R.Stiltskin; 12-15-2008 at 09:32 AM. Reason: to correct my garbled explanation of the integer-divide test, and added comment about "break"

  14. #14
    Registered User
    Join Date
    Sep 2008
    Posts
    65

    Thumbs up

    Awesome R.Stiltskin. U are the lifesaver...It is pretty clear and really understandable. Then I could proceed the next chapter about function. Great help...I will save it as my reference.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Calculating prime factor of a huge number.
    By Bakster in forum C Programming
    Replies: 15
    Last Post: 02-20-2009, 11:06 AM
  2. prime number program with function
    By mackieinva in forum C Programming
    Replies: 17
    Last Post: 09-20-2007, 08:36 AM
  3. prime numbers, counters, help!
    By vege^ in forum C++ Programming
    Replies: 1
    Last Post: 03-10-2003, 03:32 PM
  4. Prime Wonder
    By vasanth in forum A Brief History of Cprogramming.com
    Replies: 2
    Last Post: 10-07-2002, 11:49 PM
  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