Prime Numbers

[ResidentBiscuit]

bool primeCheck(unsigned long long n)
{
    if(n % 2 == 0)
        return false;
    for(unsigned int i = 3; i < (n/2); i = i + 2)
    {
            if(n % i != 0)
            {
                return false;
            }

    }
    return true;
}

I was bored so I decided to make a prime checker. This seems to work, though it I'm not sure as it gives an answer almost instantly even with close the largest number I can stick in there (unsigned long long, 17 digit number)

EDIT:
Up to 19 digits, max I can stick in there it seems like. With GCC4.7

[Volatile Pulse]

This isn't right:

            if(n % i != 0)
            {
                return false;
            }

Have you tried 9? Or 1?

[ResidentBiscuit]

Oh wow! Haha, I don't know how I missed that. I think I had two different trains of thoughts going there, and they collided.

bool primeCheck(unsigned long long n)
{
    if(n % 2 == 0)
        return false;
    for(unsigned int i = 3; i < (n/2); i = i + 2)
    {
            if(n % i == 0)
            {
                return false;
            }

    }
    return true;
}

Better? :)

EDIT:
I'm curious though, why did it work so often before? I was trying some pretty big numbers, and cross checking with wolfram and it was working

[Volatile Pulse]

They could have all been divisible by two? Either that, or they were breaking something. I have a very good example of a Prime checker. It needs to be speed optimized yet, but it's a smart checker, storing primes into a vector and cross checking them against the new number.

Code:

std::vector<long long> vPrimes;

// Definition of IsPrime
bool IsPrime(long long number) {
    // Loop through all known primes
    for (unsigned int i = 0; i < vPrimes.size(); i ++)
        // If number is divisible, it's not prime, return
        if (number % vPrimes[i] == 0)
            // Return false, was not prime
            return false;

    // Number was prime, add to vector
    vPrimes.push_back(number);
    // Return true, was prime
    return true;
}

[ResidentBiscuit]

Well I wasnt using even numbers for my tests. Just read about the Sieve of Eratosthenes. I'd heard of it before, but never had a reason to actually look it up. It looks really slick, I think I'm gonna work on implementing it.

I like how you did that. When I was doing mine above (I spent about 7 minutes on that lol) I was thinking about using a vector like you did there. May be faster traversing it with a pointer or iterator. But then again, the bracket operator probably uses pointers internally anyway. Someone correct me if I'm wrong.

[Volatile Pulse]

I think I spent more time writing my comments in than I did actually coding the function. My main isn't pretty either, but took a mere minute to write that as well.

[helios]

But then again, the bracket operator probably uses pointers internally anyway.

Yes.

Strictly speaking, to prove the primality of n you only need to check divisibility by all positive primes <=sqrt(n). Although I can't say for sure that iterating an array is faster than just checking all naturals <=sqrt(n).

[Volatile Pulse]

Why couldn't you do both? In main where I call IsPrime, I have:

    for (long long i = 2; i < 2000000; i ++)
        if (IsPrime(i))

I could make it faster by doing...

    for (long long i = 2; i < sqrt(2000000); i ++)
        if (IsPrime(i))

But I'm not sure how much faster it could get without using a different method altogether like the sieve.

[helios]

If you only need one prime, that's far slower than either method.

[Volatile Pulse]

It was for a summation of primes. All primes under 2000000...which means...I can't use the sqrt either -.-