Amicable Numbers: Difference between revisions
methods |
→Methods: clarify |
||
| Line 34: | Line 34: | ||
3. Reducing search space | 3. Reducing search space | ||
As a result of these improvements, this projects algorithm - download the source code: [https://sech.me/ap/Amicable.zip '''''Amicable.zip'''''] - finds all amicable pairs < 10<sup>13</sup> in just ~24 minutes on Core i7-4770K (8 parallel threads). | |||
The asymptotic complexity of the algorithm seems to be O(N×log(log(N))). There is no strict proof, but run times for N=10<sup>10</sup>...10<sup>17</sup> align almost perfectly with C×N×log(log(N)). | The asymptotic complexity of the algorithm seems to be O(N×log(log(N))). There is no strict proof, but run times for N=10<sup>10</sup>...10<sup>17</sup> align almost perfectly with C×N×log(log(N)). | ||