C Program to Check Prime Number Using a Function
C Program to Check Prime Number Using a Function
A student claims that any odd number is prime. A divisor test can show why odd composites such as nine still fail.
A prime integer is at least two and has no positive divisors other than one and itself. A factor test only needs candidates through its square-root boundary.
Before this exercise, review loops and stopping conditions and functions and parameters. The worked program below applies those ideas to this specific problem.
Explain
Explain why prime function uses this sequence of operations.
Trace
Trace the sample values and predict the printed result.
Apply
Use one as the candidate and explain why it is not prime.
Prime Function: follow the data
Given data
A student claims that any odd number is prime. A divisor test can show why odd composites such as nine still fail.
Rule
A prime integer is at least two and has no positive divisors other than one and itself. A factor test only needs candidates through its square-root boundary.
Observed result
49: not prime
Understand the operation
If a composite has factors a and b, at least one is no greater than its square root. The condition divisor <= value / divisor reaches that boundary without computing divisor * divisor, which could overflow for large values.
Return false immediately when a divisor leaves remainder zero. Return true only after every required divisor was tried. A named helper makes the input-to-result contract explicit.
Read the complete C program
The input values are written into this complete C17 example so the calculation can be reproduced without an unavailable service. Change the named data, rebuild and compare the actual output with your prediction.
C17 · complete program
#include <stdio.h>
static int is_prime(int value) {
if (value < 2) return 0;
for (int divisor = 2; divisor <= value / divisor; divisor++) {
if (value % divisor == 0) return 0;
}
return 1;
}
int main(void) {
int number = 49;
printf("%d: %s\n", number, is_prime(number) ? "prime" : "not prime");
return 0;
}
Expected output
49: not prime
Follow the values through the code
C17 · code used in this explanation
#include <stdio.h>
static int is_prime(int value) {
if (value < 2) return 0;
for (int divisor = 2; divisor <= value / divisor; divisor++) {
if (value % divisor == 0) return 0;
}
return 1;
}
int main(void) {
int number = 49;
printf("%d: %s\n", number, is_prime(number) ? "prime" : "not prime");
return 0;
}
The candidate is 49; the helper first rejects values less than two.
Each tested divisor is a possible witness of compositeness. A successful remainder-zero test stops that candidate’s search; finding no witness within the bound confirms it.
Follow the worked calculation
Start with the sample
The candidate is 49; the helper first rejects values less than two.
Apply the rule
Each tested divisor is a possible witness of compositeness. A successful remainder-zero test stops that candidate’s search; finding no witness within the bound confirms it.
Check the result
49: not prime
49: not prime
Try a small variation
C17 · code used in this explanation
#include <stdio.h>
static int is_prime(int value) {
if (value < 2) return 0;
for (int divisor = 2; divisor <= value / divisor; divisor++) {
if (value % divisor == 0) return 0;
}
return 1;
}
int main(void) {
int number = 49;
printf("%d: %s\n", number, is_prime(number) ? "prime" : "not prime");
return 0;
}
Use one as the candidate and explain why it is not prime.
Worked answer
The first guard rejects one before entering the divisor loop. A loop with no iterations is not sufficient by itself to establish primality.
C17 · complete program
#include <stdio.h>
static int is_prime(int value) {
if (value < 2) return 0;
for (int divisor = 2; divisor <= value / divisor; divisor++) {
if (value % divisor == 0) return 0;
}
return 1;
}
int main(void) {
int number = 1;
printf("%d: %s\n", number, is_prime(number) ? "prime" : "not prime");
return 0;
}
Expected output
1: not prime
Recognize the important boundaries
Zero, one and negative integers are not primes. Equality at the divisor boundary matters: a square such as 49 must test divisor seven.
This trial-division helper is useful for small classroom values; listing very large intervals efficiently needs a more suitable algorithm, such as a sieve.
Check your understanding
Choose the answer, then compare the reasoning for every option.
Use the idea independently
A prime integer is at least two and has no positive divisors other than one and itself. A factor test only needs candidates through its square-root boundary.
Continue with function contracts.
Continue with all factors.
Language reference: WG14 C11 committee draft. These examples use the C17-compatible subset of the explained language features.
Reaching the recap and completing the quizzes are separate milestones.