Algorithm

1. Handle small inputs: If n < 2, report Not prime.
2. Start testing: Set divisor = 2.
3. Test possible divisors: Continue while divisor <= n / divisor.
4. Check the remainder: If n % divisor == 0, report Not prime and stop.
5. Increase divisor: If it does not divide n, test the next integer.
6. Report Prime: If the tests finish without finding a divisor, n is prime.

Reason for the square-root limit

If n has a factor pair a × b = n, at least one factor is not greater than √n. Otherwise their product would be greater than n. So it is enough to look for a divisor up to and including √n. The program uses divisor <= n / divisor instead of multiplying divisor by itself, to avoid a possible multiplication overflow.

Examples

For n = 29, the values 2, 3, 4 and 5 do not divide it. The number is prime. For n = 49, divisor 7 gives a zero remainder, so 49 is not prime. The boundary must include 7. The values 0 and 1 are not prime, while 2 is prime.

Common mistakes

Testing only divisibility by 2 misses odd composite numbers such as 9 and 25. Stopping before the square-root boundary misses perfect squares such as 49. Also, do not count divisors only up to n/2 and then expect two divisors; that mixes two different methods.

Time and space complexity

In the worst case, about √n possible divisors are checked. Hence time is O(√n), where n is the number being tested. A fixed number of variables is used, so extra space is O(1).

Reference table

Diagram or flowchart

C program and output

/* CodeBhavya | PPS AR25 | Learning example */
#include <stdio.h>
int main(void)
{
    int n;
    if (scanf("%d", &n) != 1) {
        puts("Invalid input");
        return 1;
    }
    if (n < 2) {
        puts("Not prime");
        return 0;
    }
    for (int divisor = 2; divisor <= n / divisor; ++divisor) {
        if (n % divisor == 0) {
            puts("Not prime");
            return 0;
        }
    }
    puts("Prime");
    return 0;
}

49

Not prime

Key points

• Numbers below 2 are not prime.
• The square-root boundary is inclusive.