Prime Number in C

Loops

Determine primality using trial division and a safe stopping condition.

Complete program

#include <stdio.h>

int main(void) {
    int n, prime = 1;
    printf("Integer (up to 1000000): ");
    if (scanf("%d", &n) != 1 || n > 1000000) return 1;
    if (n < 2) prime = 0;
    for (int d = 2; prime && d <= n / d; ++d) {
        if (n % d == 0) prime = 0;
    }
    puts(prime ? "Prime" : "Not prime");
    return 0;
}

Try in Circuit →

Opens a new program without replacing your saved code. Press Run when you are ready.

How it works

A composite number has a factor no greater than its square root. Testing divisors beyond that point repeats work. The condition d <= n / d avoids multiplying d by itself, which could overflow for larger integers.

Numbers smaller than two are not prime. The prime flag also ends the loop after finding a divisor. Try 1, 2, 9, and 29 to exercise the special case, smallest prime, square, and ordinary prime.

Sample input

29

Enter these values when prompted. The transcript below includes typed responses.

Expected output

Integer (up to 1000000): 29
Prime

Concepts to practice

• Trial division
• Short-circuit conditions
• Remainder

Predict a different input or change one value, then compare the result with your prediction. Keep changes within the documented bounds and read warnings before trusting an answer.