Skip to main content

Primes, Factorization and Small-Input Algorithms

What this concept is​

A prime is an integer greater than 1 with no positive divisors except 1 and itself. A composite integer greater than 1 has a nontrivial factorization. One is neither prime nor composite. Every integer greater than 1 has a factorization into primes, unique up to order; this does not mean there is always a fast known way to find it for large inputs.

Why it matters here​

Prime assumptions affect algorithms and cancellation rules. A plausible shortcut that misclassifies a square can invalidate a whole computation.

Concrete example​

To test 49 by trial division, try divisors through 7 inclusive. If n = uv is composite and both positive factors were greater than the square root of n, their product would exceed n. Therefore some nontrivial factor is at most the square root. Implement the bound as d*d <= n to avoid floating-point square-root rounding. Testing only strictly smaller divisors misses prime squares.

For 84, repeated division yields 84 = 2*2*3*7. Verify the product and verify that each listed factor is prime. A divisor not found among a few hand-picked primes is not a primality proof.

Common confusion / misconception​

Prime and coprime are different: 8 and 15 are both composite but gcd(8,15)=1. A prime modulus makes every nonzero residue invertible; a composite modulus still has some invertible residues. Small examples do not justify a scalable cryptographic implementation.

How to use it​

For one small integer, trial division is simple and inspectable. Its worst-case division count is on the order of the square root of n, which is exponential in the bit length of n. For all primes up to a modest N, an optional sieve marks multiples of each unmarked prime starting at its square; this is a different workload and uses a memory array.

Check yourself​

Classify -7, 0, 1, 2, 49 and 97. Answers: only 2 and 97 are prime. Explain the square-root bound for 97 rather than checking every smaller integer.

Mini drill or application​

Factor 90 and 126. Use the minimum exponent of each shared prime to recover their gcd, then compare with Euclid. State why this is a verification exercise, not a recommendation to factor before every gcd computation.

Read this only if stuck​

Source backbone: Mathematics for Computer Science reference. For the freely available original, use MIT’s 2015 Chapter 8 readings. See the reading guide for topic selection; chapter numbering can differ across editions.