Timeline for calculating Möbius function
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 19 at 4:12 | comment | added | qwr | Maybe you can modify the linear sieve at codeforces.com/blog/entry/54090 to compute this in linear time, although that's only slightly better than O(n log log n). | |
| Sep 19 at 2:02 | comment | added | qwr | You can trade memory for more computation by first just finding the primes using a standard sieve with bitarray, then multiplying by -1 like in john mangual's answer. Then the values in the array are all either -1, 0, 1 (2 bits, or just use a char) so you can fit more into cache. | |
| Mar 23, 2014 at 14:55 | comment | added | Rick Sladkey | It's not true that all the prime factors of a number are less than its square root. But, if there is such a factor, there can only be one. | |
| Mar 23, 2014 at 4:33 | comment | added | Steve Robbins | In Rick Sladkey's answer, it seems to me that after running through the sieve, mu[i] should be 0 or +/- i. So why have the extra conditions: else if (mu[i] < 0) mu[i] = 1; else if (mu[i] > 0) mu[i] = -1; ?? | |
| Jun 14, 2012 at 17:42 | comment | added | Rick Sladkey | @Gerry: Thanks. Fixed here ... and in all my other documents. | |
| Jun 14, 2012 at 16:58 | history | edited | Rick Sladkey | CC BY-SA 3.0 |
deleted 2 characters in body
|
| Jun 14, 2012 at 5:21 | comment | added | Gerry Myerson | So, how many different spellings of Eratosthenes can we accumulate in this thread? | |
| Jun 14, 2012 at 2:04 | comment | added | Igor Rivin | Doing it the second-most-stupid-way, as described in my answer with Mathematica takes 1sec. I did not try it using Gerhard's extra-stupid way, but it is safe to say that anything works in this range. | |
| Jun 14, 2012 at 1:58 | history | answered | Rick Sladkey | CC BY-SA 3.0 |