The square root primality test is a method used to determine if a number is prime or not. It is based on the observation that if a number n is composite (not prime), it must have at least one divisor other than 1 and n itself. This divisor will be less than or equal to the square root of n.

In the C++ implementation provided, the function

`isPrime`

takes an integer `n`

as input and returns a boolean value indicating whether `n`

is prime or not.The first step in the function is to handle some base cases. If

`n`

is less than or equal to 1, it is not considered prime, so the function returns `false`

in that case.Next, the square root of

`n`

is computed using the `std::sqrt`

function from the `<cmath>`

library. The `sqrtN`

variable holds this square root value.The function then enters a loop from 2 to

`sqrtN`

. For each `i`

in this range, it checks if `n`

is divisible by `i`

. If `n`

is divisible by `i`

, it means `n`

is composite and not prime, so the function returns `false`

.If the loop completes without finding any divisors, it means

`n`

is prime, and the function returns `true`

.By checking divisors up to the square root of

`n`

, this method effectively reduces the number of divisions required for primality testing, making it more efficient than a naive approach that checks all possible divisors up to `n-1`

.The square root primality test is a simple algorithm to determine whether a given integ

`#include<bits/stdc++.h> using namespace std; bool isPrime(int num) { if(num<=1) return false; int sqrt_num = sqrt(num); for(int i=2; i<=sqrt_num; i++) { if(num%i==0) return false; } return true; } int main() { int n; cin >> n; if(isPrime(n)) cout << "Prime" << endl; else cout << "Not Prime" << endl; return 0; }`

In this code, the

`isPrime()`

function takes an integer `num`

as input and returns `true`

if it is prime, and `false`

otherwise. The function first checks if `num`

is less than or equal to 1, in which case it is not prime.Next, it initializes

`sqrt_num`

to be the square root of `num`

, since any factor of `num`

greater than `sqrt_num`

must also have a corresponding factor less than `sqrt_num`

. The function then checks if any divisor `i`

is a factor of `num`

by iterating from 2 to `sqrt_num`

.If a divisor is found, the function immediately returns

`false`

, indicating that `num`

is not prime. If no divisor is found, the function returns `true`

, indicating that `num`

is prime.Finally, in the

`main()`

function, the user inputs a number `n`

and the `isPrime()`

function is called to check if it is prime. The program then outputs either "Prime" or "Not Prime" depending on the result of the primality test.The time and space complexity of the square root primality test in the provided C++ implementation are as follows:

**Time Complexity:**

- The time complexity of the square root primality test is O(sqrt(n)). This is because the loop iterates from 2 to sqrtN, which is the square root of n. So the number of iterations is approximately sqrt(n), resulting in a time complexity of
`O(sqrt(n)).`

**Space Complexity:**

- The space complexity of the implementation is O(1) because it uses a constant amount of additional space. The variables
`n`

,`sqrtN`

, and`i`

are the only variables used, and their space requirements do not depend on the input size. Thus, the space complexity is constant or`O(1)`

.

**PRACTICE PROBLEMS :**