# Thread: My loop is not so infinite?

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

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?
http://cpwiki.sf.net/Indentation

3. Elysia, I did it like that but it wouldn't work. It didn't give me any errors, it just wouldn't abort when I entered 0.

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

5. I mean I used it in one of the first drafts of the program. I'll keep experimenting and see what I can come up with.

Thanks for the information you all have given

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

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

8. as I said, its probably the slowest 'fast' method out there, not really optimized at all other than to only test factrs less than the sqrt of the number in question. When I said there were faster methods, i wasnt refering to code level optimizations, btu rather algorithms that inherently prove or disprove primality faster. For example, not only will any composite number have a factor less than or equal to its square root, it will have a prime factor less than its square root. The proof is that any non-prime factor can itself be factored into smaler numbers, which will either be prime or can e further factored until some prime number is found. Any factor of a number A is also a factor of some number A * B.

A much faster method then is to only check the prime numbers less than or equal to sqrt(X). This is the method I used to generate the list of all 32 bit primes. The file doesnt in fact contain the number 2 although 2 is prime. Most algorithms exclude even numbers outright, so this isnt really an issue.

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