<span class="git-revision-date-localized-plugin git-revision-date-localized-plugin-date" title="December 6, 2025 18:54:47 UTC">December 6, 2025</span>&emsp;

<p>If we need the totient of all numbers between <span class="arithmatex">$L$</span> and <span class="arithmatex">$R$</span>, we can use the <a href="sieve-of-eratosthenes.html#segmented-sieve">segmented sieve</a> approach.</p>

<p>The algorithm works by first precomputing all primes up to <span class="arithmatex">$\sqrt{R}$</span> using a <a href="prime-sieve-linear.html">linear sieve</a> in <span class="arithmatex">$O(\sqrt{R})$</span> time and space. Then, for each number in the range <span class="arithmatex">$[L, R]$</span>, we apply the standard φ formula <span class="arithmatex">$\phi(n) = n \cdot \prod_{p | n} \left(1 - \frac{1}{p}\right)$</span> by iterating over the precomputed primes. We maintain a <code>rem</code> array to track the remaining unfactored part of each number; if <code>rem[i] &gt; 1</code> after processing all small primes, then the number has a large prime factor greater than <span class="arithmatex">$\sqrt{R}$</span>, which we handle in a final pass.</p>

<p><strong>Complexity:</strong></p>

<li>Preprocessing: <span class="arithmatex">$O(\sqrt{R})$</span> time and space for the linear sieve</li>

<li>Query: <span class="arithmatex">$O((R - L + 1) \log \log R)$</span> for computing φ over the range</li>

<p><strong>Usage:</strong> Call <code>primes = linear_sieve(sqrt(MAX_R) + 1)</code> once at startup. Then <code>phi[i - L]</code> gives <span class="arithmatex">$\phi(i)$</span> for each <span class="arithmatex">$i \in [L, R]$</span>.</p>

<ul class="contributors" data-bi-name="contributors"><li><a href="https://github.com/jakobkogler" title="jakobkogler" data-bi-name="contributorprofile" target="_blank">jakobkogler</a> (30.92%)</li><li><a href="https://github.com/Elghrabawy" title="Elghrabawy" data-bi-name="contributorprofile" target="_blank">Elghrabawy</a> (20.23%)</li><li><a href="https://github.com/tanmay-sinha" title="tanmay-sinha" data-bi-name="contributorprofile" target="_blank">tanmay-sinha</a> (18.32%)</li><li><a href="https://github.com/samsidx" title="samsidx" data-bi-name="contributorprofile" target="_blank">samsidx</a> (9.16%)</li><li><a href="https://github.com/adamant-pwn" title="adamant-pwn" data-bi-name="contributorprofile" target="_blank">adamant-pwn</a> (5.73%)</li><li><a href="https://github.com/Morass" title="Morass" data-bi-name="contributorprofile" target="_blank">Morass</a> (4.58%)</li><li><a href="https://github.com/tcNickolas" title="tcNickolas" data-bi-name="contributorprofile" target="_blank">tcNickolas</a> (2.67%)</li><li><a href="https://github.com/jxu" title="jxu" data-bi-name="contributorprofile" target="_blank">jxu</a> (1.91%)</li><li><a href="https://github.com/RodionGork" title="RodionGork" data-bi-name="contributorprofile" target="_blank">RodionGork</a> (1.91%)</li><li><a href="https://github.com/wikku" title="wikku" data-bi-name="contributorprofile" target="_blank">wikku</a> (0.76%)</li><li><a href="https://github.com/algmyr" title="algmyr" data-bi-name="contributorprofile" target="_blank">algmyr</a> (0.76%)</li><li><a href="https://github.com/Harpreet287" title="Harpreet287" data-bi-name="contributorprofile" target="_blank">Harpreet287</a> (0.38%)</li><li><a href="https://github.com/Animmah" title="Animmah" data-bi-name="contributorprofile" target="_blank">Animmah</a> (0.38%)</li><li><a href="https://github.com/SiddharthEEE" title="SiddharthEEE" data-bi-name="contributorprofile" target="_blank">SiddharthEEE</a> (0.38%)</li><li><a href="https://github.com/iAngkur" title="iAngkur" data-bi-name="contributorprofile" target="_blank">iAngkur</a> (0.38%)</li><li><a href="https://github.com/lrvideckis" title="lrvideckis" data-bi-name="contributorprofile" target="_blank">lrvideckis</a> (0.38%)</li><li><a href="https://github.com/rkharsan" title="rkharsan" data-bi-name="contributorprofile" target="_blank">rkharsan</a> (0.38%)</li><li><a href="https://github.com/harshhx17" title="harshhx17" data-bi-name="contributorprofile" target="_blank">harshhx17</a> (0.38%)</li><li><a href="https://github.com/likecs" title="likecs" data-bi-name="contributorprofile" target="_blank">likecs</a> (0.38%)</li></ul>