DEV Community

Discussion on: Best Code to check if number is Prime

View post
Collapse
 
basox70 profile image
Basox70 • • Edited

this doesn't work for all numbers
tested with 1111111 & 121111

[EDIT1]replace the loop by

for(int i = 5 ; i*i <= n; i = i + 4){
        if(n % i == 0 || n % (i+2) == 0) return false;
    }
    return true;
Enter fullscreen mode Exit fullscreen mode

[EDIT2] to explain : the return true in the for loop will always return true on the first try, and the && in the if need to be a ||
to test if it works, take high odd number, and if you wanna be sure, add printf("%d %% %d = %d | ", n, i, n%i); and printf("%d %% %d = %d | ", n, i+2, n%(i+2)); in the for loop (that's a fastest way instead of debug)

Collapse
 
naveennamani profile image
naveennamani • • Edited

It's i + 6 not i + 4, the only issue was the return inside the for loop.
And n == 2 || n == 3 can be simplified as n < 4 or n <=3

Collapse
 
basox70 profile image
Basox70 •

the only thing is that i+4 will check all odd number, even those divided by 3, where the i+6 won't check the 5+6*i number
I admit it's not usefull, because all (5+6*i)+4 numbers can be divided by 3

Collapse
 
hebashakeel profile image
hebaShakeel •

Hey thank you so much for the correction!