BG Programmers (Homework help)

[hey]

Don't think anyone argued with OP about using a bool. Those arguments were among other people.

[Fairy-Killer]

I agree Magus, sorry if I came off as a douche or anything. But I was honestly trying to explain to Aristio what a bool was as a lot of people were just throwing it at him. And I actually wasn't arguing about the whole bool thing, I was just trying to get across that both ways of doing it were correct since bools are the exact same as 0 or 1. I honestly didn't know if Raldo knew that a bool returned a 0 or a 1. I'm in no position to give anyone any sort of hell about programming as I was in the same boat as him three years ago. Granted, my classes were taught/supervised by Stroustrup himself so we got a pretty intimate look into how everything worked.

EDIT: Also, practicing good naming conventions was more of a heads up as we didn't really get taught that until now and boy are they grading hard on it now. If you start with good naming conventions now, it's much easier to manage a much larger program later on.

[Aristio]

Thank everyone, I -FINALLY- figured it out. Big thanks to Tidane, Raldo, hey, Fairy-Killer and Julian. Thanks Tajin for linking me that book, going to buy it in the morning.

Here's the final code:

#include <iostream>
using namespace std;

int recursive (int testNum, int devisor)
{
    if (devisor==1)
    {
        return 1;
    }
    if (testNum % devisor == 0)
    {
        return 0;
    }
    else
    {
        recursive (testNum, devisor - 1);
    }
}

int isPrime(int testNum)
{
    int devisor;
    devisor=testNum-1;
    return recursive(testNum, devisor);
}

int main ()
{
    int testNum;
    cout << "Please enter a number: ";
    cin >> testNum;

    if (isPrime(testNum))
    {
        cout << "The number " << testNum << " is a prime.";
    }
    else
    {
        cout << "The number " << testNum << " is not a prime.";
    }
    return 0;
}

[hey]

Do note that this will crash if you enter either 1, or a negative number. The easiest way to prevent that is to specifically check for these first. If the input is negative, ask for a new, positive, number. If it is 1 then immediately return 0, before dividing by 0.

Also, setting divisor to input/2 instead of -1 will make it slightly faster. Of course this program will already run instantly anyway, so it doesn't really matter, but it's such a simple optimization, so it doesn't hurt to change it.

Not sure if your teacher will care about that, but never hurts to include it. Either way, i'm glad you got it.

[Teorem]

The logic of the recursive function is still not quite right yet. The fix is very easy, and you can see the issue if you step through your code, line-by-line, on paper with a testNum of 3.

In other languages, such as Perl and Ruby, the code written similarly with this "error" would work as expected.

[Raldo]

The logic of the recursive function is still not quite right yet. The fix is very easy, and you can see the issue if you step through your code, line-by-line, on paper with a testNum of 3.

In other languages, such as Perl and Ruby, the code written similarly with this "error" would work as expected.

Just tested this, and C++ also handles it in a way where the "error" works as expected.

This might be giving it away, but the compiler should have spat out this warning for the issue that Teorem is referring to:
warning : 'recursive' : not all control paths return a value

[Aristio]

Do note that this will crash if you enter either 1, or a negative number. The easiest way to prevent that is to specifically check for these first. If the input is negative, ask for a new, positive, number. If it is 1 then immediately return 0, before dividing by 0.

Also, setting divisor to input/2 instead of -1 will make it slightly faster. Of course this program will already run instantly anyway, so it doesn't really matter, but it's such a simple optimization, so it doesn't hurt to change it.

Not sure if your teacher will care about that, but never hurts to include it. Either way, i'm glad you got it.

Are you talking about this? This ask for a number, if negative or 0, it says enter a positive number, tells you the number that you enter was not a prime, then ends.

    if (testNum <=1)
    {
        cout << "Please enter a positive number." << endl;
        return 0;
    }

So it should be testNum=divisor/2

[Cadsuane]

I think your program should be robust enough to check negative numbers. Just use the fact that if x is prime, -x is also prime.

Also, remember that 1 is not a prime number!

[Raldo]

I think your program should be robust enough to check negative numbers. Just use the fact that if x is prime, -x is also prime.

Also, remember that 1 is not a prime number!

Actually, assuming wikipedia is correct, negative numbers are not prime. I don't care enough about to subject to look up why, but the first line on the wikipedia page for prime numbers says this:

"A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself"



Personally, I would just change this

if (testNum <=1)
    {
        cout << "Please enter a positive number." << endl;
        return 0;
    }

to this

if (testNum <=1)
    {
        cout << "The number " << testNum << " is not a prime." << endl;
        return 0;
    }

... assuming this code came from the main() function, that is. If the check was in isPrime(), it could be even simpler.


All that said, I highly doubt picky little details about prime numbers and error checking was part of the assignment. Kudos if you add it though!

[hey]

Just tested this, and C++ also handles it in a way where the "error" works as expected.

As it turns out, it actually does not work in dev c++, but works fine in visual studio.

Are you talking about this? This ask for a number, if negative or 0, it says enter a positive number, tells you the number that you enter was not a prime, then ends.

    if (testNum <=1)
    {
        cout << "Please enter a positive number." << endl;
        return 0;
    }

So it should be testNum=divisor/2

That's the basic idea. Or as mentioned above, you can simply put that at the top of recursive, and return 0, so it comes back as not prime.

[Raldo]

As it turns out, it actually does not work in dev c++, but works fine in visual studio.

Very interesting! I suppose that's what they mean when the standard says something is undefined.

[Teorem]

Just tested this, and C++ also handles it in a way where the "error" works as expected.

This is what I'm referring to, and in C++ the behavior should be undefined (unless this has been changed in C++11, but I haven't looked at that standard). I just checked with a version of g++ and it does not evaluate properly. I then added an unrelated, non-fixing line and it does.

Are you talking about this? This ask for a number, if negative or 0, it says enter a positive number, tells you the number that you enter was not a prime, then ends.

This is not what I'm referring to, but to avoid confusing the issue, I should point out that what you are testing below your comment and what hey is suggesting in his second paragraph are two different things:

1) You can test the input (sanity check) for being a non-natural number by checking whether it is less than 1 (which you can do as long as you manage the control loop properly), and
2) You can speed up the process of checking potential divisors by knowing which numbers you can cut out from the list. There are no possible integer divisors of a number greater than that number divided by two (excluding itself).

[Cadsuane]

Actually, assuming wikipedia is correct, negative numbers are not prime. I don't care enough about to subject to look up why, but the first line on the wikipedia page for prime numbers says this:

"A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself"

Weeeeell... okay to be fair this is slightly semantical, but in the context of ring theory, the primes of the ring of integers can definitely be negative and wikipedia is really really wrong. Explanation in the spoiler:

Spoiler: show

since indeed, the integers comprise a commutative ring. If say, -149 has a unique factorization into primes as the fundamental theorem of arithmetic states, and -149 is not prime, then the only other factorizations are (-1)(149) or similar. However this factorization isn't unique since -1 is a unit (invertible). Hence -149 is prime in Z.

[Tidane]

Correct, negative numbers are not usually defined as prime numbers (but technically, you shouldn't care if the number is negative, because -3 and 3 are the same within most contexts), so validating that the input is greater than one is a valid way to go. I didn't want to give you all the answers, as a big component of programming is understanding the scope of the problem. I'm not sure what type of programming course this is (high school, college), but as a programmer, you need to fully understand a problem before you start coding it.

To whomever mentioned using doubles in their argument as to why bool should not have been suggested: I understand your point, but it is wrong for this problem. Prime numbers, by definition, are not doubles. Using any of the floating point datatypes is incorrect in the scope of this problem.

I am, however, slightly surprised that you didn't go over basic datatypes before being given an assignment. More advanced boolean stuff in spoiler.

Spoiler: show

As mentioned by others, a boolean is a true or false value. In C, this was done via a #DEFINE, which meant that anywhere TRUE or FALSE was typed, it was being seen as a 1 or 0 by the compiler. C++ actually has a bool datatype, which is probably defined as an 8 bit value. This (probably) means that it is being converted to a 32 bit integer, then having the least significant byte compared to whatever. I'm also guessing that some compilers may be able to optimize these instructions, but I've never looked into it.

The talk of starting the divisor had input / 2 is one of the optimizations I was talking about. For a first programming assignment, it complicates and obscures what the actual lesson is (in this case, recursion).

I don't know what your teacher is planning for the future, but I don't completely agree with some of the help that you were given. It isn't wrong, but it isn't instilling good habits for the future. For one, the idea of having a function called recursive is a bit confusing. My hope is that this is a segue into operator overloading. I assume you haven't talked about it, but a quick example of operator overloading follows:

Spoiler: show

If you are going to split the function into two functions, it should look more like this:

bool isPrime(int input);
bool isPrime(int input, int divisor);

The isPrime(int input) function would call the other is prime function. This would make the one argument method a wrapper for the two argument method. This would make sense to do if you were exposing the isPrime() method and didn't want it to be called incorrectly (for example, if someone called the two argument method with negative one as the second parameter, the method isn't going to be performing a prime test).

Without having been in the class with you, it is difficult to know what the teacher has taught you (every teacher has a different method, and not all these methods work for everyone). If you really need to understand programming, you'll probably need to do a bit of reading on your own time.

[Tidane]

Very interesting! I suppose that's what they mean when the standard says something is undefined.

In short: do not assume that any undefined functionality is the same across compilers. For non-trivial code, the problem often is that you don't know what is defined and what is undefined. Many people will compile something that works on their platform and assume that it is right, even though it isn't standards compliant. If you had to develop your code on multiple platforms, you'd quickly gain an understanding about why you need to code to the standards and not the compiler.

[Teorem]

Thinking about it pedagogically, I don't think introducing recursion early is really *that* bad. The students have already obviously been given some instruction in basic control structures (if-then loops) and conditionals, so hopefully the whole point of why recursion is used in the first place is/was stressed: to break down a large problem into smaller sub-problems that are solved in the same way.

I was flipping through a few old textbooks (including a Dietel & Dietel C++ 3rd ed. I have laying around) and they actually cover recursion pretty early (Chapter 3).

[Tajin]

This is a bit better, you dont need two functions.

#include <iostream>
using namespace std;

int IsPrime (int testNum,int devisor)
{
    if (devisor==1 || testNum==1 || testNum==2)
    {
        return 1;
    }
    if (testNum % devisor == 0)
    {
        return 0;
    }
    return IsPrime (testNum, devisor - 1);   
}

int main ()
{
    int testNum;
    cout << "Please enter a number: ";
    cin >> testNum;

    if (IsPrime(testNum,testNum-1)==1)
    {
        cout << "The number " << testNum << " is a prime.";
    }
    else
    {
        cout << "The number " << testNum << " is not a prime.";
    }
    return 0;
}

You pass testNum and testNum -1 as the function parameters, testNum stays testNum and testNum-1 becomes devisor in your fuction. I added the OR operator || in the case where the user inputs 1 as value.

This will still crash with negative numbers.

Edit: Hmm, I added the '==1' in the if, been a while since I programmed in C/C++ so not sure if it works without the comparison.

[hey]

This is a bit better, you dont need two functions.

The instructions ask for 2 functions.

[Tajin]

The instructions verbatim from pg.1

Write a C++ program to test if a number is prime. Create a function called isPrime that takes an integer called testNum and returns 1 if testNum is prime, 0 if testNum is not prime. Your main function should prompt the user for a number, call the isPrime function, check the return value, and print either "The number _ is prime!" or "The number _ is not prime." (where _ is the number the user entered)

A few hints: You will need at least two different functions: the isPrime function that gets called from main, and a second function that isPrime will call that takes the original testNum along with the recursively decreasing number to do the division check. This second function should call itself recursively. Your Programming 1 project this week tested if a number was evenly divisible by something - use the same concept here for checking divisibility.

Call your isPrime function from main after prompting the user for a number to check. For example, if the user enters 7, the isPrime function should return 1 and you can print "The number 7 is prime!" and if the user enters 4, it should return 0 and you can print "The number 4 is not prime." Try running your program plenty of times using different numbers to make sure it works correctly.

[Kaelan?]

Thinking about it pedagogically, I don't think introducing recursion early is really *that* bad. The students have already obviously been given some instruction in basic control structures (if-then loops) and conditionals, so hopefully the whole point of why recursion is used in the first place is/was stressed: to break down a large problem into smaller sub-problems that are solved in the same way.

I can't tell how much it's him having trouble grasping the concepts (which is fine, recursion is one of the hardest things to understand out of all programming concepts you learn early on) and how much it's the teacher doing a shitty job teaching it, but to me it just looks like this wasn't was presented very well in the class.

Introducing recursion before going through the basics of what native data-types are and how they work; as well as the relationships between function declarations, variables and valid operations on them is just rushing too much. It doesn't even seem like a proper explanation of the structure of your average recursive function was given.

Spoiler: show

i.e. always figuring out your terminating conditions first, the correct syntax to call a function within itself, how data gets passed down the recursive calls, then back up and out to the original calling function, etc.

@OP: If you're serious about programming, I'd say right now you should take some time to make sure you understand why the things you were trying to do weren't working, and why doing it like other people suggested would work, regardless of what the scope of the assignment was. Have a C++ reference handy and mess about with the code for a while so you get a sense of why doing things like:

int function(int arg)
{
   function = arg+1;
}

is a bad idea (and also doesn't do what you're trying to do), rather than just accepting that it's wrong. Understanding why all these things work or don't work is in the end a lot more useful than knowing how to solve any particular homework problem with them.

@Taijin: In C++ ints always evaluate to false if 0 and true if anything else