Unit 2: Primality Testing - Subjective Questions

Primality testing is the process of determining whether a given integer is prime.

• A prime number is an integer greater than that has exactly two positive divisors: and itself.
• A composite number is an integer greater than $1 that has more than two positive divisors.
• The numbers and are neither prime nor composite.

Primality testing is important because many problems require finding prime factors, generating primes, checking prime palindromes, or applying number-theoretic algorithms. An efficient test reduces the time complexity of these operations, especially when the input contains many or large numbers.

To test whether is prime, check whether any integer from through divides .

Algorithm:

• If , return composite.
• For every from to :
  • If , then is composite.
• If no divisor is found, return prime.

The algorithm works because if and both and were greater than , then their product would be greater than . Therefore, every composite number must have at least one factor less than or equal to .

The time complexity is and the extra space complexity is .

An optimized test first handles the special cases and then checks only odd divisors.

Steps:

• If , return false.
• If , return true.
• If is even, return false.
• Start with and test while .
• If any divisor is found, return false; otherwise return true.

A pseudocode representation is:

Only about half of the possible divisors are tested after excluding even values. The asymptotic time complexity remains , while the constant factor is improved. The space complexity is .

Factorization expresses an integer as a product of smaller integers. Prime factorization expresses it as a product of prime numbers.

For example:

Trial-division method:

• Start with a divisor .
• While :
  • Repeatedly divide by while .
  • Record the number of divisions as the exponent of .
  • Move to the next possible divisor.
• After the loop, if the remaining value of is greater than , it is a prime factor.

The remaining value is prime because all possible factors up to its square root have already been tested. Trial division is simple and uses extra space, but it can be slow for very large numbers or for a large number of queries.

Suppose the current value is . If is composite, it has a factor pair . At least one member of this pair must satisfy . Thus, testing divisors up to the square root is sufficient to discover a factor.

For :

• Test : . Divide repeatedly:
  
• Test : . Divide:
  
• The remaining value is , which is prime.

Therefore:

After removing each factor, the current value becomes smaller, so checking up to the square root of the current value improves practical performance.

Primality testing and prime factorization have different purposes.

Use primality testing when only a yes-or-no answer is required. Use factorization when the problem needs divisors, greatest common divisors based on factors, divisor counts, or prime powers. For many values within a fixed range, a sieve is generally more efficient than applying trial division independently to every value.

Binary exponentiation computes using the binary representation of the exponent .

The recurrence is:

An iterative version maintains result = 1 and repeatedly processes the bits of :

• If is odd, multiply result by .
• Replace with .
• Replace with .
• Continue until .

For modular exponentiation, every multiplication is performed modulo :

The exponent is halved at every iteration, so the time complexity is instead of .

The exponent is:

Therefore:

Repeated squaring gives:

Multiplying the powers corresponding to the set bits of :

Only squaring and multiplication steps are needed. The same method can compute the result modulo by reducing every intermediate product modulo , preventing unnecessarily large values.

Fermat's Little Theorem states that if is prime and is not divisible by , then:

Fermat primality test:

• Select a base such that .
• Compute using binary exponentiation.
• If the result is not , then is definitely composite.
• If the result is , then is probably prime with respect to that base.
• Repeat with several bases to reduce the probability of an incorrect conclusion.

The test is fast because modular exponentiation takes time per base. However, some composite numbers called Carmichael numbers satisfy the Fermat congruence for many bases. Therefore, Fermat's test can incorrectly classify a composite number as probably prime and should not be treated as a deterministic test without additional guarantees.

For a chosen base :

• If , then is definitely composite. This conclusion is guaranteed by the contrapositive of Fermat's theorem.
• If , then is only a probable prime for that base. The result does not prove that is prime.

Multiple bases are used because a composite number may pass the test for one base but fail for another. Testing bases such as , , , and lowers the chance of accepting a composite number. Nevertheless, Carmichael numbers can pass Fermat tests for many bases, so a stronger test such as Miller-Rabin is preferred when deterministic reliability is required.

The Sieve of Eratosthenes finds all primes from through by repeatedly marking multiples of known primes as composite.

Algorithm:

• Create a Boolean array isPrime[0...N] initialized to true.
• Set isPrime[0] and isPrime[1] to false.
• For each from while :
  • If isPrime[p] is true, mark as false.
• Every index that remains true is prime.

Marking starts at because smaller multiples of have already been marked by smaller prime factors.

The time complexity is and the space complexity is . The sieve is efficient when many prime queries are required within a known bounded range.

Initially, all numbers from to are considered candidates.

• The first prime is . Mark its multiples greater than :
  
• The next unmarked number is . Mark its multiples greater than $3:
  
  Multiples such as , , , and are already marked.
• The next unmarked number is . Since , mark:
  
• The next candidate is , but , so the sieving process stops.

The remaining numbers are:

These are exactly the prime numbers not exceeding .

A Segmented Sieve finds primes in an interval without allocating an array of size .

Steps:

• Generate all primes up to using the ordinary Sieve of Eratosthenes.
• Create a Boolean segment representing the numbers from to .
• For every base prime , find the first multiple of in the interval:
  
• Mark all multiples of in the segment as composite.
• Treat the value as non-prime if it lies in the interval.
• The unmarked values are the primes in .

The space complexity is , which is much smaller than when the interval length is relatively small. It is useful for large ranges, such as intervals near very large values.

The multiples of are for positive integers . The first multiple that is at least is:

Using integer arithmetic, this is often written as:

However, marking must begin at:

The reason is that a multiple with has a factor smaller than . Such a number should already have been marked by a smaller prime. More importantly, if the interval contains itself, marking it would incorrectly classify the prime as composite. Starting at prevents this error.

After finding the starting multiple, mark it and then mark every value obtained by adding until the value exceeds .

The problem is solved by identifying the rule that generates Mansi's series and then testing the required terms or numbers against that rule. When the series is based on prime numbers, the central operation is efficient primality testing.

A general approach is:

• Read the required term, range, or query values.
• Determine whether a term is prime, composite, or derived from prime factors.
• For a single moderate-sized value, use the test.
• For many values in a bounded range, precompute primes with the Sieve of Eratosthenes.
• If the values lie in a large interval, use a Segmented Sieve.
• Generate terms in order and stop when the requested position or boundary is reached.

Boundary cases must be handled carefully:

• is not prime.
• The value is the only even prime.
• Duplicate or repeated terms should follow the exact series definition.
• Integer overflow should be avoided when checking conditions such as ; use when necessary.

The exact recurrence or membership condition supplied in the problem statement determines the final implementation.

When multiple queries ask whether numbers belong to a prime-based series, testing each number independently may repeat the same work. Preprocessing avoids this repetition.

Efficient strategy:

• Find the maximum value needed by all queries.
• Run the Sieve of Eratosthenes up to that maximum.
• Store either a Boolean primality array or the ordered list of primes.
• Answer each query in time for direct primality checks or time using binary search in the prime list.
• If the series requires a cumulative property, build a prefix array over the precomputed values.

For example, if a query asks how many primes occur in , construct:

Then the answer is:

The preprocessing cost is and each range query can be answered in time.

When objects are represented by integers and must be grouped according to their common properties, prime factorization provides a canonical representation.

For each pen value :

• Factorize into distinct or repeated prime factors, depending on the statement.
• Store the factorization as a list, set, or exponent map.
• Use the required relationship to group pens. For example:
  • Equal prime-factor sets can be grouped together.
  • Common factors can be found using the greatest common divisor.
  • The number of divisors can be computed from the exponents.

If:

then the number of positive divisors of is:

For moderate values, trial division up to the square root is sufficient. For many values, precompute the smallest prime factor for every number. Each value can then be factorized by repeatedly dividing by its smallest prime factor, making repeated queries efficient.

An SPF sieve stores the smallest prime factor of every integer up to a limit .

Construction:

• Initialize spf[i] = i for every .
• For each prime up to , visit its multiples.
• If a multiple has not yet received a smaller factor, set its SPF to .

Factorization:

• While :
  • Read .
  • Record .
  • Divide by repeatedly to obtain its exponent.

For example, if , then repeated divisions produce:

and the factorization is .

A normal sieve costs time and space. Each SPF factorization requires approximately divisions. Repeated trial division can require time per number, so SPF is much better for many queries within a known limit.

A prime palindrome is a number that is both prime and a palindrome. A palindrome reads the same from left to right and right to left. Examples include , , , , , and .

Basic algorithm:

• Set candidate = N + 1.
• Repeat:
  • Check whether candidate is a palindrome by reversing its digits or comparing digit pairs.
  • If it is a palindrome, test it for primality.
  • If both tests succeed, return it.
  • Otherwise increment the candidate.

The primality test can use trial division up to for moderate values. For many queries or a bounded maximum, precompute primes with a sieve and check primality in constant time.

A useful observation is that every even-length palindrome greater than is divisible by . Therefore, after handling , the search can focus primarily on odd-length palindromes, reducing the number of candidates.

Let an even-length palindrome have digits:

The divisibility rule for states that a number is divisible by if the alternating sum of its digits is divisible by .

In an even-length palindrome, corresponding digits are equal and occur at positions with opposite signs in the alternating sum. Therefore, the terms cancel in pairs:

Since is divisible by , every even-length palindrome is divisible by .

Thus, every even-length palindrome greater than is composite. In a next-prime-palindrome algorithm:

• Check separately.
• Skip even-length palindromes greater than .
• Generate odd-length palindromes and test only those for primality.

This substantially reduces the search space.