Complexity of brute force primality test in the number of digits

Question

I'm wondering how to express the complexity of a brute force primality testing algorithm in the number of digits the number under test has. The brute force algorithm just checks whether $n$ is prime by checking if there is a number $k$ from $2 \leq k \leq \lfloor\sqrt{n}\rfloor$ that cleanly divides $n$. How would I go about expressing the complexity of this algorithm in the number of digits $n$ has?

My initial thought would be that in the worst case we would have to check every number $k$ $2 \leq k \leq \lfloor\sqrt{n}\rfloor$ and $n$ is very close to $10^p$ where $p$ is the amount of digits in $n$. So this would give us at least an upper bound of $\mathcal{O}(\lfloor\sqrt{10^p}\rfloor)$. Is my thought process correct?

Answer 1

In the worst case we would have to check every number $k$ $2 \leq k \leq \lfloor\sqrt{n}\rfloor$ and $n$ is very close to $10^p$ where $p$ is the amount of digits in $n$. So this would give us at least an upper bound of $\mathcal{O}(\lfloor\sqrt{10^p}\rfloor)$

You are on the right track. The upper bound $\mathcal{O}(\lfloor\sqrt{10^p}\rfloor)$ is pretty good.

We can simplify the formula a little bit and strength the result a little bit.

Proposition. The number of integers between $2$ and $\sqrt n$ (inclusively) is $\Theta(10^{\frac p2})$, where $p$ is the number of digits of $n$ in base 10.

Proof. Since $p$ is the number of digits of $n$ in base 10, we know $10^{p-1}\le n<10^p$. The number of integers between 2 and $\sqrt n$ is $\lfloor\sqrt n\rfloor-1$. I will leave the rest of the proof to you.