Anyone explain the complexity of the code?

Question

https://code.sololearn.com/cWOPqXt3J2jF/?ref=app

Answer 1

Actually what I recommend is try ChatGPT for this.
https://chat.openai.com
(Or you can also use the mobile app)
You can ask a question like "explain this code in detail" and paste your code.
It can give a line by line interpretation, and you can even ask follow up questions about any specific detail.

Some partof chatgpt answer:

This C++ program checks whether a given number is prime or not. Let's break down the code:

1. Header includes:

#include <iostream>
#include <math.h>

These lines include necessary headers for input-output operations (iostream) and mathematical functions (math.h).

2. Namespace declaration:

using namespace std;

This line makes it possible to use elements from the standard C++ library without specifying the namespace (e.g., cout instead of std::cout).

3. Function Prototype:

bool checkprime(int);

This line declares a function named checkprime that takes an integer as an argument and returns a boolean value.

Answer 2

Also from ChatGPT:

The time complexity of the provided code is O(sqrt(n)), where 'n' is the input number.

Explanation:
- The loop in the `checkprime` function runs from 2 to the square root of the input number `n` (`for (int i = 2; i <= sqrt(n); i++)`).
- The loop stops when 'i' exceeds the square root of 'n' because, if there is a factor larger than the square root, there must be a corresponding factor smaller than the square root, making it redundant to check beyond this point.
- Each iteration of the loop involves a constant time operation, checking if `n` is divisible by 'i'.

Therefore, the overall time complexity is determined by the number of iterations in the loop, which is O(sqrt(n)).

The space complexity of the code is O(1) because it uses a constant amount of additional space regardless of the input size.

Answer 3

Chatgpt seems to be wrong here.... I think the time complexity is singular exponential because of the extra condition inside the loop but I may wrong too

Answer 4

U can do better than O(sqrt(n))
Just precompute all those primes upto the upperbound first