Thread: My loop is not so infinite?

Originally Posted by Caduceus

Aha! I never thought of using logical-or! I tried to implement a break if the user enters zero, but that didn't work :P Sorry to keep asking questions, but I've read the short tutorial, and I can't figure it out, how does break work?

Though you may not need break here, a break keyword simple aborts a loop, the loop it is written in:

Code:

int main()
{
	for (int i = 0; i < 100000; i++)
	{
		if (i == 100) break;
	}
	return 0;
}

When i hits 100, the loop aborts due to the break keyword.

Originally Posted by abachler

Personally I woudl do this ---

What's with the poor indentation?
Perhaps you need to read
http://cpwiki.sf.net/Indentation

The use of a loop in your code is not needed. I just demonstrated how the keyword break works.

If abachler's code confused you a little, here it is a little simpler. It will take a bit longer to run though.

Code:

#include <iostream>
using namespace std;
 
// Prime number function - Tests number for remainder. If none is found, return false. Otherwise, return true.
 
bool PrimeFunction()
{
    int n;
 
    cin >> n;
    cin.ignore();
 
    for (int i = 2; i < n; i++)
    {
        if (n%i == 0)
        {
            cout << "Number is not prime";
            return false;
        }
    } 
    cout << "Number is prime";
    return true;
}

The code works by testing every factor of a number to see if it has no remainder, and if one such number evenly divides "n," n cannot be prime. You could replace "i < n" with "i * i < n", because you only need to test the factors up to the square root of n. If a factor of n is greater than the square root of n, then its corresponding factor is less than "n" so you would have found it anyways. IE, if n = 15, then you wouldn't need to test the factor "5" because the factor "3" would have been tested already.

Originally Posted by abachler

the original way will not accurately determine if a number is prime, it will only determine if a number is odd, not all odd numbers are prime ( 9 and 15 for example). The method I posted will absolutely determine if its prime or not. Although the method I gave you is probably the slowest 'fast' method there is, its also the simplest. There are far faster methods otu there, but the maths gets thick.

I think he may have been referring to this line:

Code:

    if (((n/temp)*temp) == n){

It could be optimised and simplified to this:

Code:

    if (n % temp == 0){

Your while loop also involves a multiplication upon each loop, whereas sqrt(n) could be precalculated instead, saving that multiplication.

Actually that's about the slowest implementation of the slowest algorithm.
For algorithmic improvements you'd need to look into:
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
and
http://en.wikipedia.org/wiki/Sieve_of_Atkin
and more.

Not meaning to pick on you though. My main point is that it was written in an unnecessarily complicated way as recognised by the OP.