# Complexity of brute force primality test in the number of digits

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?

• What do you think? What have you tried? This site encourages you to show your thoughts or partial progress toward solving the problems. People can then make the answers more helpful for you and for future readers. Jan 20 '19 at 19:27
• @Apass.Jack Yes I added my thoughts. Thank you! Jan 20 '19 at 19:37

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.
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.