## Featured Replies in this Discussion

- by JasonHippyAnother thing that was pointed out by one of my math-geek colleagues was that my algorithm would also incorrectly flag 1 as prime. Now I always thought that 1 was prime (it only divides evenly by itself and 1, so it kinda fits the criteria). However, according to my colleague; traditionally that was the case, but nowadays there is a slightly different school of thought and 1 is no longer considered prime, for reasons I…

All you need to do is use the modulus operator %.
So check the value of posnum % 2
What this does is it divides posnum by 2 and returns the remainder.
Here's a brief look at what is returned.
1 % 2 returns 1
2 % 2 returns 0
3 % 2 returns 1
4 % 2 returns 0
..... and so on
99 % 2 returns 1
100 % 2 returns 0
so if you use %2, you can easily test if a value is odd or even!
If it is odd, 1 is returned, if it is even 0 is returned.
likewise if you used %4 you get this...
1%4 returns 1
2%4 returns 2
3%4 returns 3
4%4 returns 0
5%4 returns 1
6%4 returns 2
.......and so on
99%4 returns 3
100%4 returns 0
Anyway, you need to use %2 to test for odd/even. So what you need to do is this:
[CODE]
#include

[QUOTE=PDB1982;1014918]Thanks for the help! Is there a way to determine if the numbers are prime or not, based on the code above? could you say: [code] if ( posnum / 1 = posnum/posnum) cout testNum) { // if the input number divides exactly by the test number // it is not prime! if(!(numIn % testNum)) return false; // alter the limit...think about it! limit = numIn / testNum; // Check the next odd number testNum+=2; } // if we managed to get this far, then the number is prime return true; } [/CODE] Note: I haven't compiled or tested the above code, but it shouldn't be too far off the mark..Unless my maths skills have gone completely out of the window! Then when you want to test the primality of a number you simply call the function like this: [CODE=C++] if(IsPrime(posnum)) cout

[QUOTE=JasonHippy;1015235]For starters; in your code just above you need to use the == (equality) operator to test for equality, not the = (assignment) operator. Also, that is definitely not the correct formula for determining a prime number! If you look at the first part of your expression: 'posnum/1' would always evaluate to the value of posnum, for example if posnum was 7 (which IS a prime number), then the result of posnum/1 would be 7 (because 7/1=7) Also : 'posnum/posnum' will always evaluate to 1, again using 7 as an example: 7/7=1 So your algorithm would decide that the number 7 is not prime, which is utterly wrong! Incidentally, the only time that your algorithm (posnum/1==posnum/posnum) would say that posnum is prime is when the value of posnum is 1. What I'd do is create a function which tests whether a number is prime and returns a boolean. Something like this: [CODE=C++] // tests if the passed in integer is prime // returns true if prime, false if not prime. bool IsPrime(int numIn) { // we'll test this value against numIn using the % operator int testNum=3; // Note: we only want to test numIn against ODD numbers // So we'll set it to 3 initially as it is the first odd number of interest // (everything divides by 1, so no point using it!) // This value will affect the condition of the loop, initially set to the input value int limit=numIn; // if numIn is even don't bother going any further // it's definitely not prime! if(!(numIn%2)) return false; // Now we get down to testing..... while(limit > testNum) { // if the input number divides exactly by the test number // it is not prime! if(!(numIn % testNum)) return false; // alter the limit...think about it! limit = numIn / testNum; // Check the next odd number testNum+=2; } // if we managed to get this far, then the number is prime return true; } [/CODE] Note: I haven't compiled or tested the above code, but it shouldn't be too far off the mark..Unless my maths skills have gone completely out of the window! Then when you want to test the primality of a number you simply call the function like this: [CODE=C++] if(IsPrime(posnum)) cout

Hey Gaiety! Good point, the original code was just quickly bashed out, off the top of my head and yes I missed 2 out!.. OK, so if the passed in number is 2 we need to return true (Prime), otherwise if it is divisible by 2 we need to return false (not Prime) So the only needed change in my original code is this: [CODE] if(numIn==2) return true; else if(!(numIn%2)) return false; [/CODE] So my final code looks like this: (comments stripped out!) [CODE] bool IsPrime(int numIn) { if(numIn==2) return true; else if(!(numIn%2)) return false; int testNum=3, limit = numIn; while(limit>testNum) { if(!(numIn%testNum)) return false; limit = numIn / testNum; testNum+=2; } return true; } [/CODE] And that solves the problem! Now 2 will be returned as a prime number! My code does pretty much what yours does, but mine is a tiny bit more efficient as it immediately discounts all even numbers and it uses a few other little tricks which I'll explain shortly! Comparing the algos: Your algorithm checks against everything from 2 upwards, so if the number we were testing was 19: Your algorithm would check against 2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19 before deciding it was prime (18 calculations) Whereas using my algorithm with the above change; if the number is 2 it's instantly flagged as prime, if it's even it's instantly flagged as not Prime.. Using 19 as our number, calling my function would not trigger either of those conditions, so it would check 19 against: 3 and 5 before deciding that 19 was prime! But why does it do that?? well, typically you don't need to test above the square root of the number to find whether it is prime or not. I've approximated that with the condition on the while loop and this line of code... [CODE] limit = numIn / testNum; [/CODE] How does it work? ok lets take a look. We'll imagine we're calling the function, passing the number 19 again and step through it to see what happens: (incidentally the square root of 19 is 4.35, so as long as we test up to 5 or thereabouts, we can be pretty certain whether or not 19 is prime!) numIn=19 testNum=3 limit is assigned the value of numIn, so that will be 19 at the start too: limit=19 numIn(19) != 2

[QUOTE=JasonHippy;1015531]Hey Gaiety! Good point, the original code was just quickly bashed out, off the top of my head and yes I missed 2 out!.. OK, so if the passed in number is 2 we need to return true (Prime), otherwise if it is divisible by 2 we need to return false (not Prime) So the only needed change in my original code is this: [CODE] if(numIn==2) return true; else if(!(numIn%2)) return false; [/CODE] So my final code looks like this: (comments stripped out!) [CODE] bool IsPrime(int numIn) { if(numIn==2) return true; else if(!(numIn%2)) return false; int testNum=3, limit = numIn; while(limit>testNum) { if(!(numIn%testNum)) return false; limit = numIn / testNum; testNum+=2; } return true; } [/CODE] And that solves the problem! Now 2 will be returned as a prime number! My code does pretty much what yours does, but mine is a tiny bit more efficient as it immediately discounts all even numbers and it uses a few other little tricks which I'll explain shortly! Comparing the algos: Your algorithm checks against everything from 2 upwards, so if the number we were testing was 19: Your algorithm would check against 2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19 before deciding it was prime (18 calculations) Whereas using my algorithm with the above change; if the number is 2 it's instantly flagged as prime, if it's even it's instantly flagged as not Prime.. Using 19 as our number, calling my function would not trigger either of those conditions, so it would check 19 against: 3 and 5 before deciding that 19 was prime! But why does it do that?? well, typically you don't need to test above the square root of the number to find whether it is prime or not. I've approximated that with the condition on the while loop and this line of code... [CODE] limit = numIn / testNum; [/CODE] How does it work? ok lets take a look. We'll imagine we're calling the function, passing the number 19 again and step through it to see what happens: (incidentally the square root of 19 is 4.35, so as long as we test up to 5 or thereabouts, we can be pretty certain whether or not 19 is prime!) numIn=19 testNum=3 limit is assigned the value of numIn, so that will be 19 at the start too: limit=19 numIn(19) != 2

Another thing that was pointed out by one of my math-geek colleagues was that my algorithm would also incorrectly flag 1 as prime. Now I always thought that 1 was prime (it only divides evenly by itself and 1, so it kinda fits the criteria). However, according to my colleague; traditionally that was the case, but nowadays there is a slightly different school of thought and 1 is no longer considered prime, for reasons I can't be arsed to go into! He did explain but I kinda zoned out...heh heh! What?! It's early! I haven't had any coffee yet!! ;) Apparently 1 hasn't been considered prime since the 1950's or thereabouts...So not wanting to be stuck in the past (without a DeLorean fitted with a flux capacitor, heh heh!), we could alter my algorithm to flag 1 as not prime like this: [CODE=C++] if(numIn==2) return true; else if(!(numIn%2) || numIn==1) return false; [/CODE] Incidentally, I was a little bored at work yesterday, so at lunchtime while I was waiting for a long build to finish I altered the function to work with unsigned long long integers and then created a quick little program which used my little function to calculate all the primes in the range from 1 up to the value returned by std::numeric_limits<_ulonglong>::max() (which on my pc returns as 18,446,744,073,709,551,615...a very large number indeed!) and output them to a text file.... I let it run for a few hours while I got on with some work, I then shut the program down (it was nowhere near finished, that would probably take weeks! heh heh) and I had an 87 meg text file with the first 8,877,370 primes...According to my text file the 8,877,371st prime number is 158,166,523. Anyway, going off topic a bit there, the main point was about the primality of 1 (or not as the case may be!) Cheers for now, Jas.