Square Root Primality Test

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 :

Prime Number of Set Bits in Binary Representation

Prime Palindrome