PRIME1 - Editorial

editorial
, ,
1

Problem Link - Prime Generator Practice Problem in 1000 to 1400 difficulty problems

Problem Statement:

Ram wants to generate some prime numbers for his cryptosystem. Help him please! Your task is to generate all prime numbers between two given numbers.

Approach:

Primality Check Function:

  • The function checks if a given number n is prime using a trial division up to \sqrt{n}
  • If n≤1, it immediately returns false as numbers less than or equal to 1 are not prime.
  • It iterates from 2 to \sqrt{n} If n is divisible by any of these numbers, it returns false (indicating n is not prime). Otherwise, it returns true (indicating n is prime).

Generating Primes in the Given Range:

  • For each test case, iterate from m to n and use the Prime function to check if each number in this range is prime.
  • If a number is prime, it is printed to the output, each on a new line.

Complexity:

  • Time Complexity: The Prime function has a time complexity of O(\sqrt{n}). the code iterates over the range from m to n. If the range size is R=n−m+1, the main loop runs O(R) times. Total time complexity is O(R . \sqrt{n}).
  • Space Complexity: O(1) No extra space required.