Prime Number

[incognitocpp]

task:
Function prototype: Should return a `bool` (because it answers a yes/no question) and should take in a single int (to ask whether it's prime).
- An int greater than 2 is prime if it is not divisible by any number between 2 and itself, not including itself.
- Use this function to print out the primes less than 50. Check it against my list:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

bool prime(int&x)
{
    if (x%2==1)
        return true;
    else
        return false;
}

int main()
{
    for (int i = 0; i < 50; i++)
        if ( prime(i) )
            cout << i << " ";

    return 0;
}

im not getting the required numbers. Any ideas?

[Catfish3]

Your prime() function is incorrect in checking for primes.

bool prime(int x)
{
    for (int d = 2; d < x/2; ++d)
        if (x % d == 0)
            return false;

    return true;
}

Even the above function isn't 100% correct. (Will it return correct answers for zero, and one, and two?)

[writetonsharma]

you are just testing if the number is divisible by 2 or not.

there should be a loop from 2 to number/2 and check if that number is not divisible by any number in the loop.

edit: my reply clashed.

@catfish - its always better to tell the solution or give hints rather than giving full working code.

[incognitocpp]

@catfish - the code is still printing out 1,2,3,4,5,7,11,13,17,19,23,29,31,41,43,47

[incognitocpp]

@writetonsharma-your words confused me a bit .

[writetonsharma]

Taking your definition.
for example, if I want to test 15 is a prime or not, I will keep on dividing 15 from 2 - 8 (15/2) and if it can be divided by any of the numbers in between, its not a prime. This is what I have written and @catfish has coded for you.
the result looks correct, isn't it ? (a couple of things are not correct, but I guess you can correct them)

[SamuelAdams]

Primes are so much fun, and yet so demanding.

To quickly search for a prime
you only need to divide by odd numbers up to the square root of the number your checking.
You want to search for primes in order so you will want 2 loops I think.

(pseudo code)
// may not be 100% correct but it's to give you the idea.
// you start with 3 and add 2 which means you only check the odd numbers.
// since you are not checking even numbers, you don't need to divide by 2.

while (num<=50)
{
   int num=3;
   find the sqrt(num)
     while (x<=sqrt(num))
     {
     if (num%x!=0)
             return false;
         else
             return true;
     x=x=2;
     }
num=num+2;
}

PS. when your done I'd love to see it if you would share.

[Catfish3]

This whole prime thing can be optimized further by building a prime sieve and saving it for reuse, but that's very nasty business.

[knos]

In the program above there is two errors:
In main():
for (int i = 0; i < 50; i++)
should be corrected to:
for (int i = 2; i < 50; i++)

and in prime():
for (int d = 2; d < x/2; ++d)
should be corrected to:
for (int d = 2; d <= x/2; ++d)
or even better:
for (int d = 2; d <= sqrt(x); ++d)