Prime number detection

Question

Is there any other way than 'if' to check if an integer is a prime number ?? I really do not know :(((
https://code.sololearn.com/coRv4LTTdQBh/?ref=app

Answer 1

Phuong Pham
The program can accelerated a little if noticed that all prime numbers are larger than 2 and 3 in the form 6k−1 or 6k+1, where k≥1 ( of course, the opposite is not true ).

Indeed, the numbers of 6k, 6k+2 and 6k+4 are certainly even, divisible by 2, the numbers of the forms 6k+3 are divisible by 3, so the only remaining ones are 6k+1 and 6k+5, the latter being certainly 6k′−1 ( for k′=k+1 ).

So instead of checking divisibility with all odd numbers smaller than the root, we can check divisibility with all 6k−1 or 6k+1 numbers, thus avoiding one with every three odd numbers and speeding up the program so.

if (n == 1 ||
(n % 2 == 0 && n != 2) ||
(n % 3 == 0 && n != 3))
return false;

for (int k=1; (6*k -1)*(6*k -1)<=n; k++){
if (n % (6*k +1) == 0 ||
n % (6*k -1) == 0)
return false;
}
return true;

Ace Please,
Can you check this one:
• https://code.sololearn.com/c91941ZiLAdL/?ref=app

Answer 2

Phuong Pham Thank you! 😊

Sorry,
I didn't mention, I wrote an addition for Ace's solution above.👍

[ Edited: ] here's another one,
you can play around and practicing👍
https://code.sololearn.com/cWcAymcKrid0/?ref=app

Answer 3

I still recognize you. This is not the first time you helped me. You are really enthusiastic and kind. Your explanation will help me a lot. Thanks for your help and compliments :))

Answer 4

Danijel lvanovíc
Good code. Thank you very much 😍

Answer 5

https://code.sololearn.com/c9C3YT2h8xD8/?ref=app

here flag is used for the same purpose as litmus paper is used in chemistry experiments

and the loop starts from 2 and checks till given_numner(p) /2

the loop breaks once it finds the given number is composite

it doesn't check further and is thus time saving 😊

Answer 6

Anthony
Short and effective code is one of the top criteria when I program. I really like your code. Thanks for your interest in this question❤

Answer 7

this prime number haunted me a lot when I was small now I feel myself defeating my fear

thanks to your compliment Phuong Pham

Answer 8

Anthony
Don't be so modest. Have a nice day 😆