Divisor Sum Implementations

Revision en9, by SPyofgame, 2020-06-06 17:26:20

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

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)) Very Long Complex

-------------

Planning:


  • Add relative blogs

  • Add some more implementations

  • Add tutorial & reasoning for each implementation

Tags #divisors_sum, #implementation, #miller-rabin, #primality_test, #pollard_rho, #primes, #sieve

History

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