2
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Commented Jan 20, 2019 at 19:27
  • 1
    $\begingroup$ @Apass.Jack Yes I added my thoughts. Thank you! $\endgroup$ Commented Jan 20, 2019 at 19:37

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.