Who to check whether give number is prime number or not ?

Question

can any one explain me and write any language code to check the give number is prime number or not, I need full explanation how the condition works .

Answer 1

int i,n;
bool isPrime = true;

cout << "Enter a number: ";
cin >> n;

/*This loop checks whether the entered number is
prime or not incementally dividing it by all
numbers from 2 to n/2. If there exists any number in that range which divides n in that range then isPrime boolean variable will be set false*/

for(i = 2; i <= n / 2; i++)
{
if(n % i == 0)
{
isPrime = false;
break;
}
}

if (isPrime)
cout << "prime number"
else
cout << "not a prime number"

Answer 2

why only checking​ upto n/2 ?

Answer 3

can you show by example ?

Answer 4

Thanks so much, finally I know the full concept how it works thanks soo much.

Answer 5

To make stuff even faster you only have to check until and inclusive the square root of the number.

int root = sqrt(n); //Only calculate it once
for(int i = 2; i <= root; ++i)
//...

Answer 6

because there wont be any number beyond n/2 which can divide n thus making it composite

Answer 7

If we consider number 11 it is sufficient to check till 5 .The smallest number which we can multiply with is 2. So 5×2=10 and 6×2=12 so we know any number beyond 5 cannot divide 11. Therefore if we check whether 11 is divisible by all numbers from 2 to 5 we can decide whether its prime or not.

Answer 8

You are welcome :)

Answer 9

Here is my code that I made. It is the fastest way to test if a number is prime in c++.

https://code.sololearn.com/cytaG2cjBTO3

Answer 10

Here is my code, it's in java. The algorithm works in a similar way of the one of Zeke Williams, but instead of using the square root as a limit it uses the number you are checking, divided by the prime number the program used in the cycle before the current, and to this quotient I usually add 1 to be 100% sure that the code is working in the proper way

https://code.sololearn.com/cn1cz2EdhtBP

The algorithm can be understeand better with this example:
i have to find the factor of 91,
1) I divide 91 by 2, result is 45.5,
2)therfore the factor must be between 3 (2+1) and 45.5
3) I divide 91 by 3, resut is 30.33...
4)factor must be between 4 (3+1) and 30.33...
5)I divide 91 by 5
and so on
NOTE that dividing 91 by 4 is useless, because if 4 is a factor of 91, so is 2