Divisor Sum Implementations

Правка en13, от 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 relative blogs

  • Add some more implementations

  • Add tutorial & reasoning for each implementation

Теги #divisors_sum, #implementation, #miller-rabin, #primality_test, #pollard_rho, #primes, #sieve

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
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)