Prime Number Program in C, C++ and Java

The prime number check appears in every placement coding round that screens for basic C or Java competence, from AMCAT Automata to in-campus assessments for CSE and ECE students.

Four approaches cover every format that interviewers and automated judges use: for-loop, function-based, recursive, and the sqrt-optimised variant. The implementations below cover C, C++, and Java.

What Makes a Number Prime

According to the standard mathematical definition, a positive integer n is prime if and only if it has exactly two distinct positive factors: 1 and n itself.

Three edge cases that every implementation must handle correctly:

• 0 and 1 are not prime. Neither satisfies the two-factor rule. Treat any input below 2 as non-prime.
• 2 is prime. It is the smallest prime number and the only even one. Its factors are 1 and 2.
• Negative numbers are not prime by the standard definition. The two-factor rule applies to positive integers only.

The basic check: find whether any integer from 2 to n-1 divides n without a remainder. If none does, n is prime. Both the n/2 and sqrt(n) loop bounds below are optimisations on that baseline; the section on square root explains why they are valid.

Prime Number Programs in C

For-Loop Approach

The loop runs from 2 to n/2. Any factor of n above n/2 would have to pair with a factor below 2, which is impossible for positive integers greater than 2. The break on a match avoids unnecessary iterations.

#include <stdio.h>

int main() {
    int n, i, is_prime = 1;
    printf("Enter a number: ");
    scanf("%d", &n);
    if (n < 2) {
        printf("%d is not a prime number\n", n);
        return 0;
    }
    for (i = 2; i <= n / 2; i++) {
        if (n % i == 0) {
            is_prime = 0;
            break;
        }
    }
    if (is_prime)
        printf("%d is a prime number\n", n);
    else
        printf("%d is not a prime number\n", n);
    return 0;
}

Sample runs:

• Input: 7 → 7 is a prime number
• Input: 12 → 12 is not a prime number
• Input: 1 → 1 is not a prime number

Function-Based Approach

Separating the primality logic into its own function makes the code testable and reusable. The main() function stays lean; the check is isolated and named clearly.

#include <stdio.h>

int is_prime(int n) {
    int i;
    if (n < 2) return 0;
    for (i = 2; i <= n / 2; i++) {
        if (n % i == 0) return 0;
    }
    return 1;
}

int main() {
    int n;
    printf("Enter a number: ");
    scanf("%d", &n);
    if (is_prime(n))
        printf("%d is a prime number\n", n);
    else
        printf("%d is not a prime number\n", n);
    return 0;
}

This is the pattern interviewers prefer to see in face-to-face rounds: the function is independently testable, and its return type (int acting as boolean) communicates intent without ambiguity.

Recursive Approach

The recursive version passes the current divisor as a parameter and increments it on each call. The base case returns 1 (prime) when the divisor’s square exceeds n, making this version implicitly sqrt-optimised.

#include <stdio.h>

int is_prime_helper(int n, int divisor) {
    if (n < 2) return 0;
    if (divisor * divisor > n) return 1;
    if (n % divisor == 0) return 0;
    return is_prime_helper(n, divisor + 1);
}

int main() {
    int n;
    printf("Enter a number: ");
    scanf("%d", &n);
    if (is_prime_helper(n, 2))
        printf("%d is a prime number\n", n);
    else
        printf("%d is not a prime number\n", n);
    return 0;
}

The recursive version works for small inputs. For large n, each call adds a stack frame, and the call depth reaches sqrt(n) before the base case fires. For inputs above a few thousand, the iterative version is safer in online judge submissions.

For similar check-pattern problems in the same C/C++/Java format, the palindrome string check follows the same structure: a loop that tests a property index by index and exits early on a mismatch.

Prime Number Programs in C++

C++ allows a cleaner syntax: bool return type, cin/cout, and std::sqrt from <cmath>. The logic is identical to the C version, but the types and I/O are more expressive.

#include <iostream>
#include <cmath>
using namespace std;

bool is_prime(int n) {
    if (n < 2) return false;
    int limit = static_cast<int>(sqrt(static_cast<double>(n)));
    for (int i = 2; i <= limit; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

int main() {
    int n;
    cout << "Enter a number: ";
    cin >> n;
    if (is_prime(n))
        cout << n << " is a prime number" << endl;
    else
        cout << n << " is not a prime number" << endl;
    return 0;
}

The static_cast<int>(sqrt(...)) conversion matters. Floating-point precision can cause sqrt(49) to return 6.9999..., and comparing the raw double result against an integer loop variable can give the wrong answer for perfect squares. Casting to int truncates cleanly and avoids the issue.

Prime Number Program in Java

Java’s Math.sqrt() returns a double. The same casting discipline applies. The isPrime method is declared static so it can be called from main() without an object instance.

import java.util.Scanner;

public class PrimeCheck {

    static boolean isPrime(int n) {
        if (n < 2) return false;
        int limit = (int) Math.sqrt(n);
        for (int i = 2; i <= limit; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter a number: ");
        int n = sc.nextInt();
        if (isPrime(n))
            System.out.println(n + " is a prime number");
        else
            System.out.println(n + " is not a prime number");
        sc.close();
    }
}

Sample runs:

• Input: 17 → 17 is a prime number
• Input: 25 → 25 is not a prime number

The sc.close() call at the end prevents resource-leak warnings in static analysis tools and online judges that check for it.

Optimising the Check with Square Root

The loop-to-n/2 approach is correct but does unnecessary work. The improvement is to loop only up to sqrt(n).

Why it works: if n is composite, it has a factor pair (f, n/f) where one member of the pair is at most sqrt(n). No composite number can hide all its factors above sqrt(n). So if the loop finds no divisor from 2 up to sqrt(n), n is prime. See the cppreference sqrt() page for notes on the return type and precision guarantees across platforms.

Comparison of the three approaches:

Approach	Loop bound	Time complexity
Basic for-loop	n/2	O(n)
Sqrt-optimised	sqrt(n)	O(sqrt(n))
Sieve of Eratosthenes (ranges)	n	O(n log log n) per full range

For a single number check, the sqrt-optimised version is the expected answer in any interview or online judge. The sieve becomes the right choice when you need all primes below n, because calling the single-number check in a loop repeats work that the sieve avoids entirely.

The find smallest and largest element in an array tutorial covers the same principle from a different angle: both problems have an obvious O(n) solution and a tighter one that an interviewer will ask you to justify with a complexity argument.

Where This Appears in Placement Tests

Service-tier placement coding rounds test the prime check in two common formats:

• Direct: “Given n, print whether it is prime or not.” The sqrt-optimised function scores full marks and takes under a minute to write once you’ve practised it.
• Extended: “Print all primes from 1 to n.” The expected answer shifts to the Sieve or repeated calls to is_prime, depending on the constraint on n.

AMCAT Automata and CoCubes coding sections both include the single-check variant as a baseline problem. For Tier-2 and Tier-3 college students in service-tier hiring pools, answering it correctly and quickly leaves more time for the harder problems that follow in the same assessment. The 20 most-asked data structures interview questions provides the next layer of problems that appear after the warm-up checks.

The progression from O(n) to O(sqrt(n)) for a single number, and then to the sieve’s O(n log log n) for a full range, is the kind of step-by-step complexity reasoning that separates students who understand what they wrote from those who only memorised the code. TinkerLLM applies that same reasoning to AI-specific algorithms at ₹299; it is where the logic of “test only what you need to test” transfers from primality checks to how models process inputs.