Why does this keep returning true?

[ResidentBiscuit]

So I haven't done any programming in awhile, so this is probably a blatant mistake. Anyway, this prime check always returns true, and I don't see why:

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

[Zephilinox]

it works fine for me.

[vlad from moscow]

Why do you use n += 2 in the loop? You should use n++.

[Zephilinox]

doing n++ would give you a number divisible by two if it currently isn't, if i is divisible by a number that is divisible by two, then i is divisible by two, and as such is a waste of time as it has already been checked if i is divisible by two.

[mik2718]

avoiding even numbers which have already been tested

however, you can avoid some cycles by using n < sqrt(i) instead of i/2

[vlad from moscow]

@Zephilinox
doing n++ would give you a number divisible by two if it isn't divisible by two, if it is divisible by two it isn't a prime number

A good remark. Thanks.

But if the source number is even then you will think that it is a prime number because you did not check it by divising by 2.:)

[ResidentBiscuit]

Hmm, not sure why it's not working for me. What compiler are you using Zeph?

[Dash]

I passed 6 to the function and it returned 0.

[Zephilinox]

gcc 4.7, not that it matters, any c++ compiler in the last who-knows-how-long (maybe even some of the first ones?) would work, its basic C++ syntax.

edit: apart from long long

try deleting the generated object files for your program and re-build.

[ResidentBiscuit]

Maybe I should post the whole thing:

bool primalityCheck(unsigned long long i);

int main()
{
    unsigned int counter = 0;
    unsigned long long i;
    for(i = 2; counter < 10001; i++)
    {
        if(primalityCheck)
        {
            counter++;
        }
    }
    std::cout << "10001st prime is: " << i;
    return 0;
}

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

Outputs 10003 every time. When I build, it warns me that primalityCheck will always evaluate as true.

EDIT:
Wooooow, nevermind haha. It was blatant -_-

[mik2718]

Tip r.e. testing for primality

Suppose you want to test N for primality, everyone is using a loop like this

for(i=2;i<N/2;++i)
...

or similar (good plan to deal with divisor 2 first)

But you don't need to go up to N/2, int(sqrt(N)+0.5) is as far as you need to go. After this the quotient is getting smaller so you are retesting possible divisors you have done before, this time as the quotient.

Suppose N is a large prime around 1000000, then using int(sqrt(N)+0.5) you are trying divisors 2 to ~1000, but with N/2 you are trying divisors 2 to ~500000. A 500:1 performance ratio!

[ResidentBiscuit]

Yea I realize it can be much more efficient. I plan on getting fancy here in a bit and implementing a sieve. I think it would be fun.

[Zephilinox]

Ooh, a sieve, thanks for the idea, I'll have to have a go implementing it.

and no problem vlad, although it has already been tested if it is divisible by 2 (i % 2 == 0)

[Script Coder]

I do not know if the problem is solved:
line 9: you are not calling the function

[ResidentBiscuit]

line 9: you are not calling the function

Yea I realized that awhile ago. Silly mistake

[ModShop]

mik2718 wrote:

however, you can avoid some cycles by using n < sqrt(i) instead of i/2

Not to be that guy, but I thought I would point this out. Any cycles you save by only looping to the square root rather than half of the number are going to be nothing compared to the amount of cycles used to calculate sqrt() every iteration. If you are going to go that route, for the sake of efficiency, store the return value of sqrt() in a variable rather than recalculating it every iteration. Even then, you're only saving time when checking larger numbers, so adding an if to determine whether to use sqrt() or just half could be added for further efficiency.