If the goal is to decompose an integer into its prime factors, is it better to use a sieve (such as the Sieve of Eratosthenes) or trial division up to the square root? Wikipedia has the statement
(source)
A prime sieve is…the most efficient way to obtain a large range of
primes; however, to find individual primes, direct primality tests are
more efficient.
I don't understand the claim. Of course testing if a signal number is prime is easier than generating a whole bunch of primes.
Best Answer
It depends. I hate to use that statement here, but the "best" solutions typically change with the size of the input, or depending on what we're optimizing (speed, space, programmer time, complexity, portability, etc.). You also have multiple different tasks being discussed: primality, generating primes, and factoring.
For generating primes in sequence with relatively small bounds, the segmented Sieve of Eratosthenes is the fastest method in practice. For small inputs (e.g. generating the first million or billion), the simple 4-line SoE from Wikipedia is surprisingly good, and will probably be all that's needed. The segmented sieve is more attractice for larger inputs or ranges (technically there are two different things -- segmenting and ranges). Generating crypto-size random primes is quite different and involves primality testing, not sieving. Generating a range of primes by trial division for each candidate is definitely sub-optimal.
For inputs larger than "tiny" size, primality tests such as deterministic Miller-Rabin, BPSW, or probabilistic Miller-Rabin will be more efficient than trial division. Once into small inputs such as 32-bit to 64-bit, these primality or compositeness tests are much more efficient. We can still do some preliminary trial division if we expect arbitrary input, so this question is still somewhat relevant even for large inputs (e.g. 1000 digits). I can speculate that this is what the quote "however, to find individual primes, direct primality tests are more efficient" is meant to convey -- something that seems obvious from the asymptotic complexities as well as any implementation. Compositeness and primality testing of 1000 digit numbers is no longer a hard computational task, but sieving to $10^{500}$ is just as infeasible as ever.
For factoring we find a similar situation. When expecting arbitrary inputs, it is typically most efficient to do a little trial division to get small factors. If the input is tiny, then that's all we need. As the input grows, this exponential method slows down far too much and moving to better factoring methods (e.g. Pollard's Rho with or without Brent's improvements, Pollard's P-1, SQUFOF, ECM, QS, etc.) will be better.
Now to look more directly at the statement regarding factoring. Assume we don't care about better algorithms and just want to use trial division. Some choices:
Trial divide by each integer from $2$ .. $\lfloor{\sqrt{N}}\rfloor$. Easy. Slow.
Trial divide by 2 then each odd from $3$ .. $\lfloor{\sqrt{N}}\rfloor$. Pretty easy. Half the number of divisibility tests!
Trial divide by 2, 3, then each $6i + \{1,5\}$ from $5$ .. $\lfloor{\sqrt{N}}\rfloor$. Also quite easy to code (e.g. alternate incrementing 2 and 4) and cuts out a bunch more tests.
Trial divide by 2, 3, and 5, then each $30i + \{1,7,11,13,17,19,23,29\}$ from $7$ .. $\lfloor{\sqrt{N}}\rfloor$. We don't gain as much, and coding is more complex, but it still provides a noticeable gain.
Continue these wheel factorization methods to mod 210 or mod 2310. Tables are getting large and the gain keeps going down. Some sieves and other codes use these, but they're fairly rare.
Sieve primes and do trial division by them. Guarantees the minimum number of divisibility tests, but at the expense of generating primes. Note we can use a segmented or incremental sieve so we generate primes as needed -- storage isn't an issue if you do this right.
The question is: does the additional culling of trial division save more time than generating the primes? The answer if comparing to a naive method like our first one (test every integer) is almost certainly yes. If using a more reasonable comparison such as the 8/30 wheel then it's not as clear.
My opinion is that usually a 2/6 or 8/30 wheel is more attractive than using a sieve. This is debatable and will vary based on the operation (e.g. are we saving a single native modulo, or a GMP operation on a 1000 digit input -- the latter being far more expensive). It's up to you to benchmark for your typical inputs as well as answer the code complexity, memory, and one-time-use-vs-multiple-use performance tradeoffs.