Divisor Sum Implementations

Revision en13, by SPyofgame, 2020-07-09 17:21:47

### I found these implementations ^^

Sorry, I am not sure if there are some corner cases or I calculated wrong complexity. If there are, please correct me.

I am wondering if there are some other implementations ^^ (you can comment below and I will add to the post)

Implementation 0: Trivial
Implementation 1: Optimized Trivial
Implementation 2: Naive Factorization
Implementation 3: Factorization
Implementation 4: Miller-rabin
Implementation 5: Sieve + Factorization
Implementation 6: Sieve + Miller-rabin + Pollard-rho
Implementation 7: Divisor Sum Sieve

### Compilation:

Implementation Main Algorithm Time Complexity Space Complexity Coding Space Coding Complex
0. Trivial Implementation O(n) O(1) Short Simple
1. Trivial Implementation O(√n) O(1) Short Simple
2. Factorization + Math Math O(n ^ 2) ? O(1) Normal Normal
3. Factorization + Math Factorization O(n√n) O(1) Normal Normal
4. Factorization + Math Miller-rabin O(n * log^5(n)) O(1) Long Normal
5. Factorization + Math Sieve O(n) + O(log n) O(n) Normal Normal
6. Factorization + Math Pollard-rho O(√n) + O(√(√(n)) polylog n) query O(√n) + O(log n / log(log n)) query Very Long Complex

### Planning:

• Add tutorial & reasoning for each implementation

#### History

Revisions

Rev. Lang. By When Δ Comment
en13 SPyofgame 2020-07-09 17:21:47 288
en12 SPyofgame 2020-06-07 03:18:33 776
en11 SPyofgame 2020-06-06 17:29:51 262
en10 SPyofgame 2020-06-06 17:27:09 258
en9 SPyofgame 2020-06-06 17:26:20 10
en8 SPyofgame 2020-06-06 17:25:50 212
en7 SPyofgame 2020-06-06 17:18:09 1 Tiny change: 'iler>\n\n# Compilat' -> 'iler>\n\n## Compilat'
en6 SPyofgame 2020-06-06 17:17:49 1191
en5 SPyofgame 2020-06-06 16:56:29 205
en4 SPyofgame 2020-06-06 06:22:27 31
en3 SPyofgame 2020-06-06 06:15:08 33 Tiny change: '# Divisor Sum Implementations\n\n## I found' -> '## I found'
en2 SPyofgame 2020-06-06 06:14:49 5 Tiny change: 'ations\n\nI found th' -> 'ations\n\n## I found th'
en1 SPyofgame 2020-06-06 06:14:21 10906 Initial revision (published)