✅

Hi, I am the SymPy bot. I'm here to help you write a release notes entry. Please read the guide on how to write release notes.

Your release notes are in good order.

Here is what the release notes will look like:

• ntheory
  • Speed up totientrange. (#25631 by @yuanyelele)

This will be added to https://github.com/sympy/sympy/wiki/Release-Notes-for-1.13.

This code runs significantly faster in both Python 3.11.3 and PyPy 7.3.12.

```
Python 3.11.3
old: 21.9998 seconds
new: 7.23461 seconds
204% faster

PyPy 7.3.12
old: 11.6819 seconds
new: 5.69909 seconds
105% faster
```

Benchmark code:
```python
import time
import sympy
a = time.time()
list(sympy.sieve.totientrange(10**7, 2 * 10**7))
b = time.time()
print(b - a)
``` 

<!-- BEGIN RELEASE NOTES -->
* ntheory
  * Speed up `totientrange`.
<!-- END RELEASE NOTES -->

Update

The release notes on the wiki have been updated.

Can you explain the idea behind the change here?

The original idea is that $\sum_{d\mid n}\varphi(d)=n$, so $\varphi(n) = n - \sum_{d\mid n, d < n}\varphi(d)$.
The new algorithm is simply based on the fact that $\varphi(n) =n \prod_{p\mid n} \left(1-\frac{1}{p}\right)$.
That is, for each prime number $p$ dividing $n$, let $\varphi(n)$ = $\varphi(n) \cdot (1 - \frac{1}{p})$, or $\varphi(n)$ -= $\varphi(n) / p$.

The speed-up is attributed to the fact that, while division is a slow operation, only some of the divisors of $n$ are prime numbers.