Odd Integers

[PDB1982]

I'm trying to figure out a way to create a program that has a user input a positive integer, and output a statement to the user that if the the number entered is 1 - "Number must be 2 or larger...Please enter another Positive Integer", 2 - "Number is an EVEN number", but I'm getting stuck on how to let the user know that the number entered is an ODD integer.....I just don't know how to tell the computer to compute whether or not it's odd....any ideas!?!

This is what I have so far:

#include <iostream>
#include <iomanip>
using namespace std;

void main()
{
	int posnum;
	int oddint;
	int i;
	
	while (true)
	{
		cout << "Please Enter a Positive Integer: ";
		cin >> posnum;
		cout << endl;

		if (posnum == 1)
			cout << "Number must be 2 or larger...Please enter another Positive Integer\n";
		else if (posnum == 2)
			cout << "Number is an EVEN number\n";
		
	}
	cout << endl;
}

[JasonHippy]

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:

#include <iostream>
#include <iomanip>
using namespace std;

void main()
{
	int posnum;
	int oddint;
	int i;
	
	while (true)
	{
		cout << "Please Enter a Positive Integer: ";
		cin >> posnum;
		cout << endl;

                // error here: what if the user enters something less than 1?
		// if (posnum == 1)
               // Do this instead
               if(posnum <2)
			cout << "Number must be 2 or larger...Please enter another Positive Integer\n";
		else
                {
                     // if modulus returns 1, the number is odd
                     if(posnum%2)
                           cout << "Number is an ODD number\n";
                     else  // number is even
			    cout << "Number is an EVEN number\n";
                   
	        }
	}
	cout << endl;
}

By the way, I hope you realise that you've got an infinite loop in your program!
Users will have to press ctrl+z and then enter to break out of the loop!
You may want to inform them of that...Alternatively break out of the loop if the number entered is less than 2.
Cheers for now,
Jas.

[PDB1982]

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:

if ( posnum / 1 = posnum/posnum)
     cout << "Number is Prime";
else
     cout << "Number is NOT prime";

[JasonHippy]

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:

if ( posnum / 1 = posnum/posnum)
     cout << "Number is Prime";
else
     cout << "Number is NOT prime";

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:

// 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;
}

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:

if(IsPrime(posnum))
	cout << "Number is Prime\n";
else
	cout << "Number is NOT Prime\n";

Cheers for now,
Jas.

[Gaiety]

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:

// 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;
}

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:

if(IsPrime(posnum))
	cout << "Number is Prime\n";
else
	cout << "Number is NOT Prime\n";

Cheers for now,
Jas.

one change is needed in the jas's code ,

the prime numbers starts form 2 .
forgot to check for that !

any number divisible by itself and by 1 is a prime number.
it always have only two factors.1 and itself.

so in that case, the code below
when the numIn is 2, 2%2 = 0

!0 is true
returns flase

if(!(numIn%2))
	return false;

hence not correct.

the correct way is:

int isprime(int num)
{
    int div;
    for( div =2;div < num;div++)
       {
            if(0==num % div)
              {
                      return 0;
               }
        } 
      if(num==div)
                 return 1;
     else
               return  0;
}
}

then in main function use it as

int main()
         {
               int nums[]={2,3,11,8,100,102,76,59,-1};
               int i=0;
               while(nums[i]!= -1)
               {

               if(isprime(nums[i]))
                      cout<<"num : "<< nums[i] <<" is prime"<<endl;
               else
                     cout<<"num : "<< nums[i] <<" is not prime"<<endl;
               i++;
                }
        return 0;
}

[JasonHippy]

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:

if(numIn==2)
        return true;
else if(!(numIn%2))
	return false;

So my final code looks like this: (comments stripped out!)

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;

}

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...

limit = numIn / testNum;

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 <- 19 is not 2
numIn(19)%2=1 <- 19 is not even

So the number in is not even and is not 2..
Now into the while loop...
First iteration:
Initially limit(19) is greater than testNum(3), so we enter the loop...
numIn%testNum returns 1 (19%3=1), so 19 doesn't divide evenly by 3.

limit is set to numIn/testNum (remember we're using whole ints!)
limit = 19 / 3 = 6

testNum is incremented by 2:
testnum = 5

The loop reiterates:
2nd iteration
limit = 6, testNum=5
limit is still greater than testNum, so we enter the loop...
numIn % testNum returns 4, (19 % 5 = 4) therefore 19 does not divide evenly by 5.

limit is set to numIn / testNum = 19/5 = 3

testNum is incremented by 2:
testNum=7

At the end of the 2nd iteration:
limit=3
testNum=7

Because limit is now less than testNum, we break out of the while loop and return true, indicating that the number 19 is prime.

By the time limit goes below the value of testNum we can be pretty certain that we've at least tested numIn against the square root of itself, (or an int value near it).

So my algorithm is actually quite optimised compared to yours, it does the job in fewer operations, it's relatively simple and most of all it works!

BTW: If you modify my function to use bigger int values (like unsigned int, unsigned long or unsigned long long) it will be able to test much higher numbers to see if they're prime!

Also despite it's neat little tricks, my algo is still a fairly simple brute force algorithm. There are other more advanced/optimised methods like the Sieve of Eratosthenes, miller-rabin primality test, Solovay-Strassen primality test etc. etc.

Anyway, I hope I've proved my point! heh heh! ;)
Cheers for now,
Jas.

[Gaiety]

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:

if(numIn==2)
        return true;
else if(!(numIn%2))
	return false;

So my final code looks like this: (comments stripped out!)

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;

}

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...

limit = numIn / testNum;

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 <- 19 is not 2
numIn(19)%2=1 <- 19 is not even

So the number in is not even and is not 2..
Now into the while loop...
First iteration:
Initially limit(19) is greater than testNum(3), so we enter the loop...
numIn%testNum returns 1 (19%3=1), so 19 doesn't divide evenly by 3.

limit is set to numIn/testNum (remember we're using whole ints!)
limit = 19 / 3 = 6

testNum is incremented by 2:
testnum = 5

The loop reiterates:
2nd iteration
limit = 6, testNum=5
limit is still greater than testNum, so we enter the loop...
numIn % testNum returns 4, (19 % 5 = 4) therefore 19 does not divide evenly by 5.

limit is set to numIn / testNum = 19/5 = 3

testNum is incremented by 2:
testNum=7

At the end of the 2nd iteration:
limit=3
testNum=7

Because limit is now less than testNum, we break out of the while loop and return true, indicating that the number 19 is prime.

By the time limit goes below the value of testNum we can be pretty certain that we've at least tested numIn against the square root of itself, (or an int value near it).

So my algorithm is actually quite optimised compared to yours, it does the job in fewer operations, it's relatively simple and most of all it works!

BTW: If you modify my function to use bigger int values (like unsigned int, unsigned long or unsigned long long) it will be able to test much higher numbers to see if they're prime!

Also despite it's neat little tricks, my algo is still a fairly simple brute force algorithm. There are other more advanced/optimised methods like the Sieve of Eratosthenes, miller-rabin primality test, Solovay-Strassen primality test etc. etc.

Anyway, I hope I've proved my point! heh heh! ;)
Cheers for now,
Jas.

thanks for your patient description jason
ofcourse i am aware of that.

[JasonHippy]

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:

if(numIn==2)
        return true;
else if(!(numIn%2) || numIn==1)
	return false;

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.