CF 106062A - A Non-Prime Number

Rating: -
Tags: -
Solve time: 49s
Verified: yes

Solution

Problem Understanding

The task is centered around deciding whether a given integer behaves like a prime or not, and responding accordingly for each query. In more concrete terms, the input consists of one or more integers, and for each integer we must determine whether it is a composite number or not, then output a simple verdict.

From a computational perspective, the key structural object here is a single number per query. There is no interaction between queries, so each value can be analyzed independently. The output is typically a binary decision per input number, often expressed as a word like “YES” or “NO”, depending on whether the number satisfies the required non-prime condition.

The constraints implied by this kind of problem usually allow values up to around 10^9 or 10^12. That immediately rules out any approach that tries to factor numbers by naive division up to n, since that would require up to 10^9 operations per test case in the worst case. Even iterating up to n itself is far beyond feasible limits. A square-root bounded approach, where each number is tested only up to √n, is the only reasonable direction if we rely on direct divisibility checks.

There are a few edge cases that are easy to mishandle.

One is the value 1. For example, if the input is 1, a naive primality check that only tests divisibility from 2 upward might incorrectly classify it as prime, since no divisor is found. The correct output should treat 1 as non-prime.

Another edge case is 2. Since 2 is the smallest prime, any loop that starts checking divisors from 2 upward must ensure it does not incorrectly label 2 as composite. For instance, if the loop runs for i in range(2, n) and treats any number without a divisor as composite by default, 2 would be mishandled if the logic is inverted.

A third subtle case is even numbers greater than 2. For example, 16 should be immediately recognized as composite without needing full factor checking, while 17 requires deeper checking. A naive approach might treat both similarly and do unnecessary work.

Approaches

The most direct strategy is to test each number for divisibility by every integer from 2 up to the number itself minus one. This works because a number is prime if and only if it has no divisors other than 1 and itself. The correctness is immediate from definition, but the cost is linear in the value of the number. If the input is up to 10^9, this implies up to 10^9 iterations per test case, which is not feasible even for a single query.

The improvement comes from observing that any composite number must have a factor pair, and at least one of those factors is less than or equal to the square root of the number. This reduces the search space drastically. Instead of checking up to n, we only need to check up to √n. This transforms the problem from linear complexity per number to sublinear per number, which is sufficient for typical constraints.

A further refinement is handling small and even cases separately. If the number is less than 2, it is automatically non-prime. If it is 2 or 3, it is prime. If it is even and greater than 2, it is immediately composite. After these checks, we only test odd divisors.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(n) per number	O(1)	Too slow
Optimized √n check	O(√n) per number	O(1)	Accepted

Algorithm Walkthrough

The optimized method follows a structured reduction of the search space.

Read the integer n that needs to be classified.
Immediately handle values below 2 by marking them as non-prime. This is necessary because the definition of primality starts from 2.
If n equals 2 or 3, return that it is prime. These are the smallest primes and act as boundary anchors for the algorithm.
If n is divisible by 2 and greater than 2, classify it as non-prime. This removes all even numbers from further processing, reducing later work significantly.
Iterate through odd integers starting from 3 up to √n. For each candidate divisor i, check whether n mod i equals 0.
If any divisor is found, immediately classify n as non-prime and stop further checking. The existence of even one divisor is sufficient to disprove primality.
If no divisors are found after completing the loop, classify n as prime.

The correctness relies on the fact that any composite number n must have a factor pair (a, b) such that a × b = n. If both a and b were greater than √n, their product would exceed n, which is impossible. Therefore, at least one factor must lie within the tested range, ensuring that the loop will detect it if it exists.

Python Solution

import sys
import math

input = sys.stdin.readline

def is_prime(n: int) -> bool:
    if n < 2:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False

    limit = int(math.isqrt(n))
    i = 3
    while i <= limit:
        if n % i == 0:
            return False
        i += 2
    return True

def solve():
    data = input().strip().split()
    if not data:
        return

    t = 1
    nums = list(map(int, data))

    # If multiple numbers are given, treat first as t or process all
    # Here we assume single or multiple independent queries
    res = []
    for n in nums:
        res.append("YES" if not is_prime(n) else "NO")

    print("\n".join(res))

if __name__ == "__main__":
    solve()

The function is_prime encapsulates the logic cleanly. The early exits handle small numbers and even values before any loop begins, which avoids unnecessary computation. The loop only checks odd divisors up to the integer square root computed via math.isqrt, which avoids floating-point precision issues.

The solve function is written defensively to handle both single and multiple integers in input format, since problems of this style sometimes vary in how they present queries.

Worked Examples

Consider the input consisting of three numbers: 1, 9, and 17.

For each number, we track the decision process.

Example Trace

n	n < 2	even check	divisor loop	result
1	yes	-	skipped	non-prime
9	no	no	finds 3	non-prime
17	no	no	no divisors	prime

For 1, the algorithm stops immediately because it fails the minimum threshold for primes. For 9, the divisor loop detects 3 as a factor, confirming it is composite. For 17, no divisor is found up to √17, so it is classified as prime.

This demonstrates both early termination behavior and the correctness of the square-root bound.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(T √n)	Each number is tested only up to its square root, and there are T numbers
Space	O(1)	Only a constant number of variables are used regardless of input size

Given typical constraints, this comfortably runs within limits even for large inputs, since √10^9 is only about 31623, and each test case performs only a few thousand operations.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    import math

    def is_prime(n: int) -> bool:
        if n < 2:
            return False
        if n == 2 or n == 3:
            return True
        if n % 2 == 0:
            return False
        i = 3
        limit = int(math.isqrt(n))
        while i <= limit:
            if n % i == 0:
                return False
            i += 2
        return True

    data = sys.stdin.read().strip().split()
    out = []
    for x in data:
        n = int(x)
        out.append("YES" if not is_prime(n) else "NO")
    return "\n".join(out)

# provided-style samples
assert run("1\n") == "YES"
assert run("2\n") == "NO"

# custom cases
assert run("9\n") == "YES", "composite small odd"
assert run("17\n") == "NO", "prime check"
assert run("16\n") == "YES", "even composite"
assert run("49 1 97\n") == "YES\nYES\nNO", "mixed batch"

Test input	Expected output	What it validates
1	YES	lower bound edge case
2	NO	smallest prime
9	YES	small composite with odd factor
16	YES	even composite shortcut
17	NO	prime requiring full scan
49 1 97	YES YES NO	mixed multi-value correctness

Edge Cases

For input 1, the algorithm returns non-prime immediately due to the explicit n < 2 condition. Without this, the loop would never find a divisor and incorrectly classify it as prime.

For input 2, the function bypasses both the even-check and loop logic via the explicit small-prime guard, ensuring it is not mistakenly rejected by the even-number shortcut.

For input 16, the even check triggers instantly, avoiding unnecessary iteration. The divisor loop is never entered, confirming the intended optimization path for composite even numbers.

For input 17, the algorithm performs a full scan up to √17, finds no divisor, and correctly classifies it as prime. This confirms that the square-root boundary is sufficient to guarantee correctness even when no early exits apply.