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.