Need help with C++ programming....

[ice91785]

Basically its what the title says. It's a real simple program dealing with prime numbers, I don't know much about modular division though....

The user inputs a number and then the program checks to see if the number is PRIME. There is a looping statement to be included that uses modular division of the input number including all integers up to the sq. root of the input number.

Like I said, I don't know very much at all about modular division or using it to find PRIME numbers......the actual programming part I shouldn't have a problem with, but I just need a push on generally what the looping statement COULD look like.

 

[eakers]

modular division gives the remainder of a number divided by another

for example:
10%3 = 1
10%2 = 0

a prime number isn't divisable by any number except for 1 and itself therefore it won't ever have x%y = 0 (provided y!=1 and y!=x)

 

[Cooler]

A simple loop starting at 2 to number/2 will tell you if its prime or not.

 

[eakers]

couldn't you just go 2-9 or number/2 whichever is smaller?

 

[DaveSimmons]

Does your homework list a specific algorithm that you should be following? What are your instructions for the assignment?

 

[ice91785]

The project goes as follows (summarized):

Design and implement a program that carries out the following steps:

1. It prompts for and reads a positive integer from the terminal.
2. It determines if the integer is prime.
3. It reports whether the value is prime or not to the terminal.

As suggested in the introduction, determine if a value is prime by trying to divide it by 2 and then by every odd number up to the value's square root. Use the % (mod) operator to find if one integer divides another: b divides a if and only if (a mod b) is zero.

 

[imported_quasi]

Originally posted by: Cooler
A simple loop starting at 2 to number/2 will tell you if its prime or not.

You only need to check from 2 to the square root of the number to determine if it is prime.

I haven't used C++ for several years (Python FTW), so sorry if this code isn't correct/complete, but it would go something like:

if (n % 2 == 0) {
cout << "Not Prime";
}
for(i=3; i < (sqrt(n)+1); i +=2) {
if(n % i == 0) {
cout << "Not Prime"
}
}

 

[ice91785]

Hmm....I think I am getting ya here. Thanks a bunch guys. If anyone has additional input you are more than welcome to add. I'll try and make myself a program tonight and see how it works.

 

[Matthias99]

if (n % 2 == 0) {
cout << "Not Prime";
}
for(i=3; i < (sqrt(n)+1); i +=2) {
if(n % i == 0) {
cout << "Not Prime"
}
}

While your assignment probably doesn't require any kind of optimization -- calling sqrt() each time in the loop will slow this down considerably (it's a fairly expensive computation involving floating point math). You should calculate it once beforehand and then just loop up until that value.

 

[Aikouka]

Heh, that algorithm will say that '2' isn't a prime number... oh golly jeez, I sure bet it is .

EDIT: It also won't work for numbers that are only divisible by 1, the number itself and the number's square root (such as 4, 9, etc).

The one I've attached should work fine. Personally I haven't tested it, so I won't put 100% faith in it, but it addresses the problems I mentioned in this post.

EDIT 2: My code doesn't check 1 and 2.. it actually won't even let you enter them. But reading over your description, it SHOULD check those numbers as well (as they're both positive integers). Just modify mine to allow 1 and 2 and throw in an if statement to capture them . 1 and 2 are too special to try to encapsulate in a loop without adding unnecessary logic.

 

[Matthias99]

The code I quoted works (other than 2 being reported as non-prime). It loops while i is less than (sqrt(n) + 1), so if sqrt(n) is odd it will cover it.

The code you just posted has major problems. It checks this:

(num % 2 == 0)
(num % 4 == 0)
(num % 6 == 0)
...

This will mistakenly identify numbers only divisible by odd numbers as prime (such as 15).

You need to check divisibility by 2, then by (3, 5, 7, ...), or else just check the divisibility of all numbers (although this is about half as fast). Of course, there are other algorithms, but this is probably the simplest.

 

[Aikouka]

Originally posted by: Matthias99
The code I quoted works (other than 2 being reported as non-prime). It loops while i is less than (sqrt(n) + 1), so if sqrt(n) is odd it will cover it.

The code you just posted has major problems. It checks this:

(num % 2 == 0)
(num % 4 == 0)
(num % 6 == 0)
...

This will mistakenly identify numbers only divisible by odd numbers as prime (such as 15).

You need to check divisibility by 2, then by (3, 5, 7, ...), or else just check the divisibility of all numbers (although this is about half as fast). Of course, there are other algorithms, but this is probably the simplest.

Ahh true, forgot that I was adjusting the starting point without fixing the offset .

Change the offset to this: i += (i % 2) + 1

That will work. It will go from 2 to 3, 3 to 5, 5 to 7, 7 to 9, etc.

Also, no, there is more wrong with it than you think and I mentioned it above. Numbers such as 4 and 9 will be reported as prime with that code and they are not prime. The reason? It only goes up to the square root and not up to and including. This is a problem when the only number that divides the input (other than 1 and the input) is the square root of the input.

EDIT: Forgot the '+'.

 

[Matthias99]

Change the offset to this: i += (i % 2) + 1

Doing the modular math each pass is also inefficient (although that expression will work properly). It's better to test for divisibility by 2 separately, then increment by a fixed amount.

Also, no, there is more wrong with it than you think and I mentioned it above. Numbers such as 4 and 9 will be reported as prime with that code and they are not prime. The reason? It only goes up to the square root and not up to and including. This is a problem when the only number that divides the input (other than 1 and the input) is the square root of the input.

Read the code. The loop conditional is (i < (sqrt(n) + 1)). For 9, sqrt(n) is 3, so the loop condition will be true as long as i < 4. On the first pass, when i == 3, (9 % i == 0) will be true. If n = 25, it will loop as long as i < 6, and will declare n to be non-prime when i == 5.

4 would have been caught by the initial test for (n % 2 == 0) (along with any other integer that has an even square root or factor).

 

[katastrophe]

For anybody looking for some serious optimization, I would recommend reading this. It talks about the Sieve of Erasthones and the Sieve of Atkin and a few other primality tests.

 

[Aikouka]

Originally posted by: Matthias99
Doing the modular math each pass is also inefficient (although that expression will work properly). It's better to test for divisibility by 2 separately, then increment by a fixed amount.

You will see no time difference between them using modular math. Maybe if you're checking a number like eleventy billion... you may see an extra couple milliseconds . Roughly, you can compare modular math to 3 simple math steps:

n % m = n - (m * (n / m))

Although I can't tell you if this is how C++ translates mod operations (as I don't know), 3 math ops * n iterations will probably not add up to much time.

Originally posted by: Matthias99
Read the code. The loop conditional is (i < (sqrt(n) + 1)). For 9, sqrt(n) is 3, so the loop condition will be true as long as i < 4. On the first pass, when i == 3, (9 % i == 0) will be true. If n = 25, it will loop as long as i < 6, and will declare n to be non-prime when i == 5.

4 would have been caught by the initial test for (n % 2 == 0) (along with any other integer that has an even square root or factor).

Bah, I missed it because it was poorly separated. I glance over code quickly and leaving out spaces (that are always highly recommended... for me... back in college... if you left those spaces out, you were docked points when it came to style) makes readability suffer. My mistake on not looking closer, but arithmetic should be spaced properly :|. Also, the n % 2 STILL catches '2', which is a problem unless you use one of my methods (not allowing '2' or using boolean logic to catch the pesky primes).

You're complaining about my inefficiency of using modular arithmetic and you're willing to use an extra iteration in a loop because you're too lazy to put an equal sign? You're also condoning an EXTRA loop through the ALU :Q. May God have mercy on your soul .

EDIT: Just as a note, the division in the beginning is integer division if you're wondering (as mod requires the inputs to be int-based anyway ).

 

[Matthias99]

Originally posted by: Aikouka

Originally posted by: Matthias99
Doing the modular math each pass is also inefficient (although that expression will work properly). It's better to test for divisibility by 2 separately, then increment by a fixed amount.

You will see no time difference between them using modular math. Maybe if you're checking a number like eleventy billion... you may see an extra couple milliseconds . Roughly, you can compare modular math to 3 simple math steps:

n % m = n - (m * (n / m))

Although I can't tell you if this is how C++ translates mod operations (as I don't know), 3 math ops * n iterations will probably not add up to much time.

But there's no need to do a modulo operation there at all (since after you hit 3, you will always increment by 2 each time). Given the minimal number of instructions in the body of that loop, adding an extra math operation in the conditional may be something like a 25% decrease in speed, maybe more. You're going from one ALU operation per pass to two (or maybe from two to three, since it has to increment the loop counter as well.)

How C++ compiles '%' depends on the platform (and if the operands are already in registers). On 32-bit x86, it should be one instruction in a simple loop like that.

Bah, I missed it because it was poorly separated. I glance over code quickly and leaving out spaces (that are always highly recommended... for me... back in college... if you left those spaces out, you were docked points when it came to style) makes readability suffer. My mistake on not looking closer, but arithmetic should be spaced properly :|. Also, the n % 2 STILL catches '2', which is a problem unless you use one of my methods (not allowing '2' or using boolean logic to catch the pesky primes).

Look. I didn't write it. I would have spaced it out better too (and if I were grading your program, yeah, I would have docked you points.)

But if you're going to tell someone repeatedly that their math/code is wrong, you need to double-check that sort of thing. And I said that it didn't catch 2 as prime after you pointed it out. I always seem to forget that 2 is considered prime...

You're complaining about my inefficiency of using modular arithmetic and you're willing to use an extra iteration in a loop because you're too lazy to put an equal sign? You're also condoning an EXTRA loop through the ALU :Q. May God have mercy on your soul .

Where does that code use an extra iteration through the loop? (i < sqrt(n) + 1) is the same as (i <= sqrt(n)), and you have to check sqrt(n).

EDIT: Just as a note, the division in the beginning is integer division if you're wondering (as mod requires the inputs to be int-based anyway ).

...you don't have a division ('/') anywhere in your code?

But yes, modular arithmetic is only defined for integers.

 

[imported_quasi]

Originally posted by: Aikouka
Heh, that algorithm will say that '2' isn't a prime number... oh golly jeez, I sure bet it is .

Damn, that was a stupid mistake in my code

Originally posted by: Aikouka
Bah, I missed it because it was poorly separated. I glance over code quickly and leaving out spaces (that are always highly recommended... for me... back in college... if you left those spaces out, you were docked points when it came to style) makes readability suffer. My mistake on not looking closer, but arithmetic should be spaced properly :|.

I always put a space between the outermost operators, but tend not to between inside expressions because I find it somewhat unnecessary. For instance, I write "(3+2) / (9-2)" But then again, I've only taken one formal programming class and other than that am self-taught.

 

[ice91785]

Soooo....I thought I had the hang of it here but you guys put a little doubt in there :-s Here is what my looping statement DID look like....though i haven't actually written the program yet.

{
m = sqrt(n);

if (n % 2 == 0)
cout << "Not Prime" << endl;

for(i=3; i < m+1); i +=2)
{
if(n % i == 0)
cout << "Not Prime"
}
else
cout << n << " is prime" << endl;
}


Am I missing anything HUGE in there?

 

[Matthias99]

Originally posted by: ice91785
Soooo....I thought I had the hang of it here but you guys put a little doubt in there :-s Here is what my looping statement DID look like....though i haven't actually written the program yet.

{
m = sqrt(n);

if (n % 2 == 0)
cout << "Not Prime" << endl;

for(i=3; i < m+1); i +=2)
{
if(n % i == 0)
cout << "Not Prime"
}
else
cout << n << " is prime" << endl;
}


Am I missing anything HUGE in there?

1) You need to check if they entered 1 or 2. In that case, you should just return 'prime' immediately without going into this loop.

2) The for loop you wrote is nonsensical (you have an 'else' coming off the 'for'). Also, you should break immediately if you find it is not prime (there's no sense in continuing to check more factors).

3) You're going to need to track somehow whether the number was found to not be prime in order to decide whether or not to print the "is prime" message.

 

[Aikouka]

Originally posted by: Matthias99
But there's no need to do a modulo operation there at all (since after you hit 3, you will always increment by 2 each time). Given the minimal number of instructions in the body of that loop, adding an extra math operation in the conditional may be something like a 25% decrease in speed, maybe more. You're going from one ALU operation per pass to two (or maybe from two to three, since it has to increment the loop counter as well.)

How C++ compiles '%' depends on the platform (and if the operands are already in registers). On 32-bit x86, it should be one instruction in a simple loop like that.

Then I don't see it being a big deal :x. Yeah, if I was writing it for work, I'd try to squeeze every utmost piece of efficiency that I could out of it, but sometimes when writing programs for assignments, I tried to figure out the "niftier" but still relatively efficient way to do it. So don't get me wrong, I try to push for at least a decent level of efficiency. It's like when I took an automata class and made a 13 state FSM (what I believe is the smallest possible for that problem) and someone else made a 30+ state FSM for the same problem :Q.

Originally posted by: Matthias99
Look. I didn't write it. I would have spaced it out better too (and if I were grading your program, yeah, I would have docked you points.)

But if you're going to tell someone repeatedly that their math/code is wrong, you need to double-check that sort of thing. And I said that it didn't catch 2 as prime after you pointed it out. I always seem to forget that 2 is considered prime...

I know you didn't write it . When I originally wrote that post, I mentioned that, but I rewrote that entire section and left that part out since I didn't think I had to mention it. I'm usually never sure if 2 is a prime so I just wiki'd it .

Originally posted by: Matthias99
Where does that code use an extra iteration through the loop? (i < sqrt(n) + 1) is the same as (i <= sqrt(n)), and you have to check sqrt(n).

Yeah nevermind. Must've been thinking off for some reason (tend to do that at work). Don't get to code often and I kind of miss it . I found nothing more enjoyable than sitting with a pad of paper writing out some obscene formula that solves some weird problem in one fel swoop (and efficiently too ).

Originally posted by: Matthias99
...you don't have a division ('/') anywhere in your code?

But yes, modular arithmetic is only defined for integers.

I mean that when I was talking about division up top with the mod operator (as in my math explosion into "simple terms"). Because any math dork who read it would be like "m cancels out m!"

Originally posted by: RockSolid
Damn, that was a stupid mistake in my code

No coder is ever perfect . You probably just wrote it and didn't test it or anything, which it's not like I did either lol. But had it been a project, testing would've been done and you would've caught it .

Originally posted by: RockSolid
[I always put a space between the outermost operators, but tend not to between inside expressions because I find it somewhat unnecessary. For instance, I write "(3+2) / (9-2)" But then again, I've only taken one formal programming class and other than that am self-taught.

Readability isn't something most books and such will talk about, but usually higher level CS courses will try and stress that more and more.

 

[Matthias99]

Then I don't see it being a big deal :x. Yeah, if I was writing it for work, I'd try to squeeze every utmost piece of efficiency that I could out of it, but sometimes when writing programs for assignments, I tried to figure out the "niftier" but still relatively efficient way to do it. So don't get me wrong, I try to push for at least a decent level of efficiency.

I know that efficiency is not really a concern here. However, to me, the loop conditional you wrote is not just potentially quite inefficient, but also significantly harder to understand. Being "nifty" is not all it's cracked up to be; maintainability is something that becomes very important in large software projects, and doing things in non-straightforward ways is often not such a great idea. I know that if I saw a loop written like this:

for (i = 2; i <= 1000; i += (i % 2) + 1)
{
function_call(i);
}

I would have no freaking clue what it did until I sat down and worked it out. Even with comments explaining what it was supposed to do, I wouldn't be sure at a glance that it was correct. Whereas:

function_call(2);

for (i = 3; i <= 1000; i += 2)
{
function_call(i);
}

is extremely obvious. It's one thing if you are using some tricky algorithm or doing something to significantly increase performance, but just getting fancy for the heck of it is usually not worthwhile. And in this case, it's both harder to read and slower (although the latter loop will take up a few more bytes of memory, but it's a lousy tradeoff).

It's like when I took an automata class and made a 13 state FSM (what I believe is the smallest possible for that problem) and someone else made a 30+ state FSM for the same problem.

If your 13-state FSM was a nightmare to understand and debug compared to the 30-state one, you could argue that it wasn't necessarily a 'better' way to solve the problem. Of course, if you absolutely need to squeeze out every last bit of performance, or totally minimize memory usage, it's a different story. Even then, IMO it's better to start with something straightforward and then optimize as necessary.

 

[imported_quasi]

Originally posted by: Matthias99
1) You need to check if they entered 1 or 2. In that case, you should just return 'prime' immediately without going into this loop.

From everything I've ever read, 1 is neither prime nor composite.

 

[Matthias99]

Originally posted by: RockSolid

Originally posted by: Matthias99
1) You need to check if they entered 1 or 2. In that case, you should just return 'prime' immediately without going into this loop.

From everything I've ever read, 1 is neither prime nor composite.

You see, this is why I went into pure CS instead of CE. I have the computer to do the math stuff for me.

 

[you2]

I'm not sure we should be doing your homework for you.

 

[Aikouka]

Originally posted by: Matthias99
I know that efficiency is not really a concern here. However, to me, the loop conditional you wrote is not just potentially quite inefficient, but also significantly harder to understand. Being "nifty" is not all it's cracked up to be; maintainability is something that becomes very important in large software projects, and doing things in non-straightforward ways is often not such a great idea. I know that if I saw a loop written like this: ...

That's not a hard equation... how could I not be able to write a comment that's understandable to any layperson? "Uses math to process 2 and then every odd number following." If you can't understand how that works with just that... I donno if you should be the one to maintain my code .

Originally posted by: Matthias99
If your 13-state FSM was a nightmare to understand and debug compared to the 30-state one, you could argue that it wasn't necessarily a 'better' way to solve the problem. Of course, if you absolutely need to squeeze out every last bit of performance, or totally minimize memory usage, it's a different story. Even then, IMO it's better to start with something straightforward and then optimize as necessary.

But it wasn't hard to understand and it was very easy to debug . Literally, it did whatever it needed to do and nothing more. It also combined each task into one "subroutine" instead of making one for each. Once I can actually get JFlap to download, I'll get a screen shot of this machine and show you . If I recall, it was a problem with order of dominance (an alphabetical food chain).

EDIT: I found it and took a screenshot. Here's the link: http://www.aikouka.com/TM2.gif . Although I warn you, it won't be easy to understand for most people. Just know that on a transition, the formula is: "input; replacement, movement"