Prime Numbers and Primality Testing

A prime is an integer greater than one with no positive divisors besides one and itself. Prime testing appears in factorization, modular arithmetic and combinatorial constructions. Trial division is an exact deterministic method suitable for moderate input values: if a composite number exists, one of its factors is at most its square root. This lesson makes the bound and performance limit explicit rather than claiming a square-root scan is fast for every 64-bit integer.

Prerequisites: Divisibility; loops; complexity.

Build the idea

1. 1. Separate small and exceptional values

   Values below 2 are not prime. Two is the only even prime. An even number greater than 2 is composite, so return immediately. These branches also avoid starting an odd-divisor loop on meaningless cases such as zero and one. Prime does not mean odd: nine and twenty-five are odd composites.

2. 2. Prove the square-root test

   If n=u·v with both u,v greater than one and both above √n, their product would exceed n. Thus a composite n has a divisor at most √n. Conversely, finding such a divisor certifies compositeness. If none exists after checking all candidates, no nontrivial factorization is possible, so n is prime.

   $$u·v=n\Rightarrow \min (u,v)\le \sqrt{n}$$

3. 3. Skip even candidates safely

   After rejecting even n, try 3,5,7,… . The condition divisor≤n/divisor includes the square-root boundary without overflowing divisor*divisor or relying on floating-point sqrt rounding. It is fine to test odd composite candidates too; skipping them with a sieve is an optimization, not a correctness requirement.

4. 4. Trace a prime and a square

   For 97, test 3,5,7,9; each leaves a nonzero remainder, and 11>97/11, so the answer is PRIME. For 49, the loop must include 7; 49%7==0 returns COMPOSITE. Using divisor<divisor-bound or stopping strictly before √n would miss perfect squares. For 1, print NOT PRIME rather than calling it composite.

5. 5. Match the method to workload

   The program handles q values individually. With values near 10^12, one worst-case test performs roughly half a million odd checks; a hundred such tests can be substantial. For many values in a small range use a sieve. For truly large 64-bit primality queries, more advanced methods such as carefully implemented deterministic Miller–Rabin are appropriate, but are not taught as an unqualified replacement here.

This is a complete program. Compile with C++17 and enter the input described below.

// Key idea: 3. Skip even candidates safely After rejecting even n, try 3,5,7,… .
#include<iostream>
bool isPrime(long long n){
    if(n<2){
        return false;
    }
    if(n%2==0){
        return n==2;
    }
    for(long long divisor=3;divisor<=n/divisor;divisor+=2){
        if(n%divisor==0){
            return false;
        }
    }
    return true;
}
int main(){
    int q;
    std::cin>>q;
    while(q--){
        long long n;
        std::cin>>n;
        std::cout<<(n<2?"NOT PRIME":isPrime(n)?"PRIME":"COMPOSITE")<<'\n';
    }
}

Complexity analysis

O(√n) trial divisions per worst-case input, O(1) auxiliary space. Across q inputs use O(Σ√nᵢ), not merely O(√max n). Early factor discovery can be much faster, but does not improve the worst-case guarantee. The demonstration allows q≤100 and n≤10^12.

Example input and output

Read q (0..100), then q integers n in 0..10^12. Print NOT PRIME for n<2, PRIME for prime n, otherwise COMPOSITE.

Input

4
1
2
49
97

Output

NOT PRIME
PRIME
COMPOSITE
PRIME

One is neither prime nor composite; two is prime; 49 has divisor 7; 97 has no divisor up to its square root.

Practical applications

Use for a few moderate values, validating factors and small reference solvers. Use Eratosthenes for many queries up to a common manageable maximum. Choose stronger number-theory algorithms when square-root work exceeds the constraints.

Check your understanding

Why must the divisor scan include √n when it is an integer?

Put it into practice

Compare this test with a sieve for every n up to 10000.