There are lots of methods. Here are some :

- Trial division : try to divide

by a number between

and

. It is always a worst case since any number can be picked.

- Fermat's factorization algorithm : note that if you set

with

and

, then it becomes

or

. It becomes clear that the nearer a prime factor is from the square root of

, the easier the algorithm becomes. However, if a prime factor is very small, then this algorithm is possibly the worst ever.

- Linear sieve : start from

, and try divisions by increasing

by

each time. The worst case will be if

. That must be your point.

There are lots of better methods, like the quadratic sieve or general number field sieve, but I'm not really good at explaining them so I will let Wikipedia do it

The worst case for factoring semiprimes in terms of arithmetic complexity really depends on the method used.