杭电oj2073

### HDU OJ 2073 Problem Description and Solution The problem **HDU OJ 2073** titled *"Find the closest prime number"* requires finding the nearest prime number to a given integer \( N \). If two primes are equally close, output the smaller one. #### Input Specification Multiple test cases exist. Each test case contains an integer \( N \), where \( 1 \leq N \leq 2^{31} - 1 \). #### Output Specification For each input value \( N \), output its closest prime number on a new line. --- To solve this problem efficiently, we can use the following approach: 1. **Prime Checking Function**: Implement a function `is_prime(x)` to check whether a number \( x \) is prime by testing divisibility up to \( \sqrt{x} \)[^4]. ```python import math def is_prime(n): if n < 2: return False for i in range(2, int(math.sqrt(n)) + 1): if n % i == 0: return False return True ``` 2. **Search Strategy**: Starting from \( N \), search both upwards (\( N+1, N+2, ... \)) and downwards (\( N-1, N-2, ... \))[^5]. Stop when the first prime is found. ```python def find_closest_prime(N): lower = upper = N while True: if is_prime(lower): return lower elif is_prime(upper): return upper lower -= 1 upper += 1 ``` 3. **Handling Multiple Test Cases**: Read multiple inputs until EOF (End of File) or as specified in the contest environment[^6]. ```python import sys lines = sys.stdin.read().splitlines() results = [] for num_str in lines: N = int(num_str.strip()) result = find_closest_prime(N) results.append(result) print("\n".join(map(str, results))) ``` This algorithm ensures correctness because it systematically checks numbers around \( N \) using efficient primality tests. The time complexity depends heavily on how far away the next prime lies but remains manageable within reasonable bounds due to optimizations like square root checking during primality verification. --- ### Example Walkthrough Given \( N = 10 \): - Check downward: \( 9 \rightarrow \text{not prime}, 8 \rightarrow \text{not prime}, ..., 7 \rightarrow \text{prime!} \). - Return \( 7 \) since no closer prime exists above \( 10 \). If another example were provided with \( N = 15 \): - Check upward: \( 16 \rightarrow \text{not prime}, 17 \rightarrow \text{prime!} \). - Since \( |17 - 15| = 2 \) matches any potential downward candidate's distance, choose the smallest among them—here still \( 17 \). Thus, outputs align accordingly based upon proximity rules defined earlier. ---