# Ulam's Spiral: Has it been explained or not?

**URL:** <https://boards.straightdope.com/t/ulams-spiral-has-it-been-explained-or-not/316757>\
**Category:** Factual Questions\
**Created:** [August 12, 2005, 5:27pm UTC](https://boards.straightdope.com/t/ulams-spiral-has-it-been-explained-or-not/316757 "2005-08-12T17:27:18Z")\
**Posts on this page:** 1\
**Page:** 3

<div class="post-metadata">

**Author:** ![Omphaloskeptic](https://avatars.discourse-cdn.com/v4/letter/o/bcef8e/32.png) [@Omphaloskeptic](https://boards.straightdope.com/u/Omphaloskeptic)\
**Post date:** [August 15, 2005, 6:24pm UTC](https://boards.straightdope.com/t/ulams-spiral-has-it-been-explained-or-not/316757/41 "2005-08-15T18:24:36Z")

</div>

> [@ultrafilter](#):
>
> Instead of having sqrt(n) trial divisors, you’d have roughly sqrt(n)/ln(sqrt(n)). You could still choose a large enough key that it would be difficult to factor by brute force, but it would become significantly less complex in a technical sense.

Hmm. This would slightly speed up the naive O(sqrt(n)) algorithm, true, but not by enough to make it competitive with the best algorithms known. If all we can do is efficiently generate the primes in sequence, then it’s not clear to me how that would substantially speed up algorithms like ECM which don’t perform large numbers of trial divisions. (Primality testing is already polynomial, so it’s not like the efficiency gain would be huge anyway.)

[Previous page](https://boards.straightdope.com/t/ulams-spiral-has-it-been-explained-or-not/316757.md?page=2)