Answer: A number n ≥ 2 is prime if no number from 2 to \( \sqrt{n} \) divides it.
Logic: numbers less than 2 are not prime. Otherwise test divisors i = 2, 3, … while i × i ≤ n; if any divides n exactly, n is not prime.
Program:
#include <stdio.h>
int main()
{
int n, i, isPrime = 1;
printf("Enter a number: ");
scanf("%d", &n);
if (n < 2)
isPrime = 0;
for (i = 2; i * i <= n; i++)
{
if (n % i == 0)
{
isPrime = 0;
break;
}
}
if (isPrime)
printf("%d is a prime number\n", n);
else
printf("%d is not a prime number\n", n);
return 0;
}Sample output (actual run):
Enter a number: 29
29 is a prime numberEnter a number: 21
21 is not a prime number