Originally Posted by 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:

Help with Code Tags

C++ Syntax (Toggle Plain Text)

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

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

Originally Posted by JasonHippy

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:

Help with Code Tags

C++ Syntax (Toggle Plain Text)

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

// 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:

Help with Code Tags

C++ Syntax (Toggle Plain Text)

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

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

Cheers for now,
Jas.

Originally Posted by 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:

Help with Code Tags

C++ Syntax (Toggle Plain Text)

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

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

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

Help with Code Tags

C++ Syntax (Toggle Plain Text)

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

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

Help with Code Tags

C++ Syntax (Toggle Plain Text)

		limit = numIn / testNum;

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.