update phi-function.md add segmented totient (find phi function from L to R) #1570
Conversation
|
Thanks for the PR! The algorithm seems to be correct, but there are a couple of integer overflow issues that need to be fixed first before merging:
|
Updated the segmented_phi function to handle long long types for larger ranges and adjusted related variables accordingly.
|
Clarify the φ(n) computation in the text description - right now it's underspecified. Move the relevant notes from comments into the main text so they're not overlooked. Also include the linear sieve preprocessing complexity. |
| **Complexity:** | ||
| - Preprocessing: $O(\sqrt{R})$ time and space for the linear sieve | ||
| - Query: $O((R - L + 1) \log \log R)$ for computing φ over the range |
There was a problem hiding this comment.
This is not query step. Combine all of the text into single paragraph with complexity and usage included. Also, it's better to move the whole section upper, placing it under the "Finding the totient from 1 to $n$ using the divisor sum property" section. As far as I understand, your idea does not use Gauss' divisor sum property.
There was a problem hiding this comment.
Once these issues are fixed, the section should be ready to be merged. Also, if possible, it would be great to add tests for the code in the test/ folder.
2 participants
No description provided.