PRIMALITY - Editorial

editorial
, , ,
1

Problem Link - Primality Test in Number theory

Problem Statement:

Alice and Bob are playing a math game where Alice announces a number, and Bob must quickly determine if it’s prime.

Approach:

  • See the reference: Sieve of Eratosthenes in Number theory
  • You initialize a boolean array prime where prime[i] will be true if i is a prime number. The algorithm iterates through each number starting from 2 and marks its multiples as non-prime.

Complexity:

  • Time Complexity: The sieve runs in O(n log ⁡log ⁡n) time for n=100,000
  • Space Complexity: The space used is O(n) for the prime array