For each integer \(n\), let \(p\) and \(q\) be the consecutive primes satisfying \(p \lt \sqrt n \lt q\). The number \(n\) is called semidivisible when exactly one of those two primes divides it. The task is to compute
$$S(L)=\sum_{\substack{n\le L\\ n\text{ semidivisible}}} n$$
for the given limit \(L=999966663333\).
A direct search over all \(n\le L\) would be hopeless. The successful idea is to stop thinking about individual integers and instead group them by the pair of consecutive primes surrounding \(\sqrt n\). Once that pair is fixed, the semidivisible condition becomes a clean inclusion-exclusion calculation on an interval.
The three implementations all exploit the same structure: partition the line into prime-square bands, compute one closed-form contribution for each band, and add those contributions.
Suppose \(p\) and \(q\) are consecutive primes. Then the condition
$$p \lt \sqrt n \lt q$$
is equivalent to
$$p^2 \lt n \lt q^2.$$
So every semidivisible number belongs to exactly one interval between two consecutive prime squares. Inside that whole band, the lower surrounding prime is always \(p\) and the upper surrounding prime is always \(q\). For a fixed pair \((p,q)\), the relevant interval is therefore
$$A=p^2+1,\qquad B=\min(L,q^2-1).$$
The final band may be cut off by the global limit \(L\), but the logic is the same.
Inside the band \((p^2,q^2)\), a number is semidivisible exactly when it is divisible by one of \(p\) or \(q\), but not both. That is an XOR condition:
$$p\mid n \;\text{ xor }\; q\mid n.$$
Define \(M_d(A,B)\) to be the sum of all multiples of \(d\) in the closed interval \([A,B]\). Then the contribution of the band determined by consecutive primes \(p\) and \(q\) is
$$\mathcal{B}(p,q)=M_p(A,B)+M_q(A,B)-2M_{pq}(A,B).$$
Why does this work? Every multiple of \(p\) contributes once through \(M_p\), every multiple of \(q\) contributes once through \(M_q\), and numbers divisible by both are counted twice. Because \(p\) and \(q\) are distinct primes, being divisible by both means being divisible by \(pq\), so subtracting \(2M_{pq}(A,B)\) removes exactly those forbidden cases and leaves only numbers divisible by exactly one of the two primes.
For any divisor \(d\), the multiples of \(d\) in \([A,B]\) are
$$d\,k_0,\ d(k_0+1),\ \dots,\ d\,k_1,$$
where
$$k_0=\left\lceil\frac{A}{d}\right\rceil,\qquad k_1=\left\lfloor\frac{B}{d}\right\rfloor.$$
If \(k_0 \gt k_1\), there are no such multiples and the sum is \(0\). Otherwise the terms form an arithmetic progression, so
$$M_d(A,B)=d\cdot\frac{(k_0+k_1)(k_1-k_0+1)}{2}.$$
This is the key collapse. Instead of inspecting potentially millions of integers in one band, the implementations evaluate three closed-form sums: one for multiples of \(p\), one for multiples of \(q\), and one for multiples of \(pq\).
The first relevant consecutive-prime pairs are \((2,3)\) and \((3,5)\).
For \((2,3)\), the band is \(4 \lt n \lt 9\), so \(A=5\) and \(B=8\). The multiples are:
$$M_2(5,8)=6+8=14,\qquad M_3(5,8)=6,\qquad M_6(5,8)=6.$$
Hence
$$\mathcal{B}(2,3)=14+6-2\cdot 6=8.$$
The only semidivisible number there is \(8\): \(6\) is excluded because it is divisible by both \(2\) and \(3\).
For \((3,5)\), the global limit truncates the band to \(10\le n\le 15\). Now
$$M_3(10,15)=12+15=27,\qquad M_5(10,15)=10+15=25,\qquad M_{15}(10,15)=15.$$
Therefore
$$\mathcal{B}(3,5)=27+25-2\cdot 15=22,$$
which comes from the semidivisible numbers \(10\) and \(12\). Summing the two bands gives
$$S(15)=8+22=30.$$
Once the band formula is known, the whole problem is just
$$S(L)=\sum_{\substack{(p,q)\text{ consecutive primes}\\ p^2\le L}} \mathcal{B}(p,q),$$
with \(B=\min(L,q^2-1)\) in the last active band. No semidivisible number is ever generated explicitly; every contribution comes from prime pairs and arithmetic-series identities.
The C++, Python, and Java implementations first generate all primes up to slightly beyond \(\sqrt L\). That is enough because any relevant band is determined by a prime \(p\) with \(p^2\le L\) and the next prime \(q\). The code therefore prepares a prime list through about \(\sqrt L\) and makes sure there is at least one additional prime above that threshold for the final band.
It then scans adjacent prime pairs \((p,q)\). For each pair it computes the band endpoints \(A=p^2+1\) and \(B=\min(L,q^2-1)\). If \(A\gt B\), the band contributes nothing. Otherwise the implementation evaluates the three interval sums \(M_p(A,B)\), \(M_q(A,B)\), and \(M_{pq}(A,B)\) from the first multiple, the last multiple, and the arithmetic-progression formula, and adds
$$M_p(A,B)+M_q(A,B)-2M_{pq}(A,B)$$
to the running total.
Everything is done with integer arithmetic. The C++ implementation uses wider intermediate integers for safety, Python relies on arbitrary-precision integers, and Java stays within signed 64-bit arithmetic for this problem size. All three implementations stop as soon as the lower prime square \(p^2\) exceeds \(L\).
Let \(N=\lfloor\sqrt L\rfloor+O(1)\). In these implementations, prime generation is done with a linear-sieve style method, so producing the prime table costs \(O(N)\) time and \(O(N)\) memory. The subsequent scan over consecutive prime pairs performs only constant work per pair, so it adds \(O(\pi(\sqrt L))\) operations, which is smaller than the sieve itself.
Therefore the overall complexity is
$$O(\sqrt L)\text{ time and }O(\sqrt L)\text{ memory}.$$
The important point is not just the asymptotic bound, but the structural reduction: the algorithm replaces a search across almost \(10^{12}\) integers by a pass over primes near \(\sqrt L\), with each band handled in constant time.
Zu jeder ganzen Zahl \(n\) betrachten wir die benachbarten Primzahlen \(p\) und \(q\) mit \(p \lt \sqrt n \lt q\). Die Zahl \(n\) heißt semidivisibel, wenn genau eine dieser beiden Primzahlen \(n\) teilt. Gesucht ist also
$$S(L)=\sum_{\substack{n\le L\\ n\text{ semidivisibel}}} n$$
für die gegebene Schranke \(L=999966663333\).
Eine direkte Prüfung aller Zahlen bis fast \(10^{12}\) wäre viel zu langsam. Der entscheidende Schritt besteht darin, nicht Zahlen einzeln zu untersuchen, sondern ganze Bereiche zu bündeln, in denen die um \(\sqrt n\) liegenden Primzahlen gleich bleiben.
Alle drei Implementierungen benutzen dieselbe Zerlegung: Intervalle zwischen aufeinanderfolgenden Primzahlquadraten, eine exklusive Teilbarkeitsbedingung innerhalb jedes Intervalls und eine Summenformel für arithmetische Folgen.
Seien \(p\) und \(q\) benachbarte Primzahlen. Dann ist
$$p \lt \sqrt n \lt q$$
genau äquivalent zu
$$p^2 \lt n \lt q^2.$$
Damit gehört jede relevante Zahl genau zu einem Band zwischen zwei aufeinanderfolgenden Primzahlquadraten. Innerhalb dieses gesamten Bandes sind die beiden umgebenden Primzahlen fest, nämlich \(p\) und \(q\). Für ein festes Paar \((p,q)\) arbeiten wir also mit
$$A=p^2+1,\qquad B=\min(L,q^2-1).$$
Nur das letzte aktive Band kann durch die globale Schranke \(L\) abgeschnitten werden.
Innerhalb des Bandes ist \(n\) genau dann semidivisibel, wenn \(n\) durch \(p\) oder durch \(q\) teilbar ist, aber nicht durch beide. Formal ist das eine XOR-Bedingung:
$$p\mid n \;\text{ xor }\; q\mid n.$$
Bezeichne mit \(M_d(A,B)\) die Summe aller Vielfachen von \(d\) im Intervall \([A,B]\). Dann ist der Beitrag des Bandes
$$\mathcal{B}(p,q)=M_p(A,B)+M_q(A,B)-2M_{pq}(A,B).$$
Der Grund ist einfach: Vielfache von \(p\) werden in \(M_p\) erfasst, Vielfache von \(q\) in \(M_q\). Zahlen, die durch beide Primzahlen teilbar sind, wurden damit zweimal gezählt. Da \(p\) und \(q\) verschieden und prim sind, sind genau die Vielfachen von \(pq\) doppelt gezählt, und durch das Subtrahieren von \(2M_{pq}(A,B)\) bleiben exakt die Zahlen übrig, die durch genau eine der beiden Primzahlen teilbar sind.
Für einen festen Teiler \(d\) sind die Vielfachen von \(d\) in \([A,B]\)
$$d\,k_0,\ d(k_0+1),\ \dots,\ d\,k_1,$$
wobei
$$k_0=\left\lceil\frac{A}{d}\right\rceil,\qquad k_1=\left\lfloor\frac{B}{d}\right\rfloor.$$
Falls \(k_0 \gt k_1\), gibt es keine Vielfachen und die Summe ist \(0\). Andernfalls liegt eine arithmetische Folge vor, also
$$M_d(A,B)=d\cdot\frac{(k_0+k_1)(k_1-k_0+1)}{2}.$$
Damit reduziert sich jeder Bandbeitrag auf genau drei Summen in geschlossener Form: für \(p\), für \(q\) und für \(pq\).
Die ersten relevanten Primzahlpaare sind \((2,3)\) und \((3,5)\).
Für \((2,3)\) gilt \(4 \lt n \lt 9\), also \(A=5\) und \(B=8\). Dann
$$M_2(5,8)=6+8=14,\qquad M_3(5,8)=6,\qquad M_6(5,8)=6.$$
Somit ist
$$\mathcal{B}(2,3)=14+6-2\cdot 6=8.$$
In diesem Band ist also nur \(8\) semidivisibel; die \(6\) fällt heraus, weil sie durch beide Primzahlen teilbar ist.
Für \((3,5)\) wird das Band durch \(L\) auf \(10\le n\le 15\) abgeschnitten. Hier erhält man
$$M_3(10,15)=12+15=27,\qquad M_5(10,15)=10+15=25,\qquad M_{15}(10,15)=15.$$
Daraus folgt
$$\mathcal{B}(3,5)=27+25-2\cdot 15=22,$$
also die Zahlen \(10\) und \(12\). Insgesamt ergibt das
$$S(15)=8+22=30.$$
Ist der Beitrag eines einzelnen Bandes bekannt, lautet die gesamte Aufgabe einfach
$$S(L)=\sum_{\substack{(p,q)\text{ benachbarte Primzahlen}\\ p^2\le L}} \mathcal{B}(p,q).$$
Es werden also niemals alle semidivisiblen Zahlen einzeln erzeugt; statt dessen summiert man nur über aufeinanderfolgende Primzahlpaare.
Die C++-, Python- und Java-Implementierungen erzeugen zuerst alle Primzahlen bis leicht über \(\sqrt L\). Mehr wird nicht benötigt, weil jedes relevante Band von einer Primzahl \(p\) mit \(p^2\le L\) und der unmittelbar folgenden Primzahl \(q\) bestimmt wird. Deshalb genügt eine Primzahlliste bis ungefähr \(\sqrt L\) plus der ersten Primzahl darüber.
Anschließend werden benachbarte Primzahlpaare \((p,q)\) durchlaufen. Zu jedem Paar berechnet die Implementierung die Bandgrenzen \(A=p^2+1\) und \(B=\min(L,q^2-1)\). Ist \(A\gt B\), trägt das Band nichts bei. Andernfalls werden die drei Summen \(M_p(A,B)\), \(M_q(A,B)\) und \(M_{pq}(A,B)\) direkt aus erstem Vielfachen, letztem Vielfachen und der Formel der arithmetischen Folge bestimmt und als
$$M_p(A,B)+M_q(A,B)-2M_{pq}(A,B)$$
zum Gesamtergebnis addiert.
Die Rechnung bleibt vollständig ganzzahlig. Die C++-Version verwendet breitere Zwischenwerte, Python nutzt beliebig große Ganzzahlen, und Java bleibt für diese Problemgröße innerhalb des 64-Bit-Bereichs. Alle drei Implementierungen brechen ab, sobald \(p^2\) größer als \(L\) wird.
Sei \(N=\lfloor\sqrt L\rfloor+O(1)\). In diesen Implementierungen wird die Primzahlerzeugung mit einem linearen Sieb-artigen Verfahren durchgeführt, also in \(O(N)\) Zeit und \(O(N)\) Speicher. Der anschließende Durchlauf über benachbarte Primzahlpaare benötigt nur konstante Arbeit pro Paar und kostet daher \(O(\pi(\sqrt L))\), also weniger als das Sieb.
Damit ergibt sich insgesamt
$$O(\sqrt L)\text{ Zeit und }O(\sqrt L)\text{ Speicher}.$$
Der eigentliche Gewinn liegt in der Modellierung: Statt fast \(10^{12}\) Zahlen einzeln zu prüfen, betrachtet man nur Primzahlen in der Umgebung von \(\sqrt L\) und behandelt jedes Band mit einer konstanten Anzahl geschlossener Formeln.
Her tam sayı \(n\) için, \(p \lt \sqrt n \lt q\) koşulunu sağlayan ardışık asalları alalım. \(n\), bu iki asalın tam olarak biri tarafından bölünüyorsa semidivisible olarak adlandırılır. İstenen büyüklük
$$S(L)=\sum_{\substack{n\le L\\ n\text{ semidivisible}}} n$$
olup burada \(L=999966663333\) verilir.
Yaklaşık \(10^{12}\) sayıyı tek tek kontrol etmek pratik değildir. Çözümün özü, sayıları tek tek incelemek yerine, \(\sqrt n\)'in etrafındaki asal çiftinin sabit kaldığı bantlara ayırmaktır. O anda semidivisible koşulu, aralık içindeki katların toplamına indirgenir.
Üç uygulama da aynı matematiksel iskeleti kullanır: ardışık asal kareler arasındaki bantları bul, her bant için kapalı form bir katkı yaz ve bunları topla.
\(p\) ve \(q\) ardışık asallar olsun. O zaman
$$p \lt \sqrt n \lt q$$
koşulu tam olarak
$$p^2 \lt n \lt q^2$$
koşuluna denktir. Böylece her ilgili sayı, iki ardışık asal karesi arasındaki tam olarak bir banda düşer. Bu bandın tamamında alt çevreleyen asal \(p\), üst çevreleyen asal ise \(q\) olarak sabit kalır. Dolayısıyla sabit bir \((p,q)\) çifti için çalışılan aralık
$$A=p^2+1,\qquad B=\min(L,q^2-1)$$
şeklindedir. Son bant gerekirse \(L\) yüzünden kısalır.
Bu bant içinde \(n\), tam olarak biri tarafından bölündüğünde semidivisible olur:
$$p\mid n \;\text{ xor }\; q\mid n.$$
\([A,B]\) aralığındaki \(d\) katlarının toplamını \(M_d(A,B)\) ile gösterelim. O zaman bu bandın katkısı
$$\mathcal{B}(p,q)=M_p(A,B)+M_q(A,B)-2M_{pq}(A,B)$$
olur. Gerekçe şudur: \(p\)'nin katları ilk toplamda, \(q\)'nun katları ikinci toplamda birer kez sayılır. Her ikisinin ortak katları iki kez sayılmış olur. \(p\) ve \(q\) farklı asal olduğundan her ikisine birden bölünebilmek \(pq\)'ya bölünebilmekle aynıdır. Bu yüzden \(2M_{pq}(A,B)\) çıkarmak, yasak durumları tam olarak temizler ve yalnızca iki asalın birine bölünen sayıları bırakır.
Sabit bir \(d\) için \([A,B]\) içindeki katlar
$$d\,k_0,\ d(k_0+1),\ \dots,\ d\,k_1$$
biçimindedir; burada
$$k_0=\left\lceil\frac{A}{d}\right\rceil,\qquad k_1=\left\lfloor\frac{B}{d}\right\rfloor.$$
Eğer \(k_0 \gt k_1\) ise bu aralıkta hiç kat yoktur ve toplam \(0\) olur. Aksi halde terimler aritmetik dizi oluşturur ve
$$M_d(A,B)=d\cdot\frac{(k_0+k_1)(k_1-k_0+1)}{2}$$
elde edilir. Böylece bir bant için milyonlarca sayıyı dolaşmak yerine yalnızca üç kapalı form toplam hesaplanır: \(p\), \(q\) ve \(pq\) için.
İlk iki asal çifti \((2,3)\) ve \((3,5)\) olur.
\((2,3)\) için bant \(4 \lt n \lt 9\) olduğundan \(A=5\), \(B=8\):
$$M_2(5,8)=6+8=14,\qquad M_3(5,8)=6,\qquad M_6(5,8)=6.$$
Dolayısıyla
$$\mathcal{B}(2,3)=14+6-2\cdot 6=8.$$
Bu bantta semidivisible olan tek sayı \(8\)'dir; \(6\) hem \(2\)'ye hem \(3\)'e bölündüğü için çıkarılır.
\((3,5)\) için bant, küresel sınır nedeniyle \(10\le n\le 15\) olur. Bu kez
$$M_3(10,15)=12+15=27,\qquad M_5(10,15)=10+15=25,\qquad M_{15}(10,15)=15.$$
Buradan
$$\mathcal{B}(3,5)=27+25-2\cdot 15=22$$
çıkar; bu da \(10\) ve \(12\)'nin toplamıdır. İki bandı birleştirince
$$S(15)=8+22=30$$
elde edilir.
Artık genel formül doğrudan yazılabilir:
$$S(L)=\sum_{\substack{(p,q)\text{ ardışık asallar}\\ p^2\le L}} \mathcal{B}(p,q).$$
Yani çözüm, semidivisible sayıları üretmekten değil, ardışık asal çiftlerinin bant katkılarını toplamaktan oluşur.
C++, Python ve Java uygulamaları önce \(\sqrt L\)'in biraz ötesine kadar tüm asalları üretir. Bunun yeterli olmasının sebebi şudur: Her aktif bant, \(p^2\le L\) koşulunu sağlayan bir asal \(p\) ve ondan sonraki asal \(q\) tarafından belirlenir. Son aktif bant için \(\sqrt L\)'in hemen üstündeki ilk asala da ihtiyaç vardır.
Daha sonra ardışık asal çiftleri \((p,q)\) tek tek gezilir. Her çift için bant uçları \(A=p^2+1\) ve \(B=\min(L,q^2-1)\) hesaplanır. Eğer \(A\gt B\) ise katkı yoktur. Aksi halde uygulama, ilk katı ve son katı bularak \(M_p(A,B)\), \(M_q(A,B)\) ve \(M_{pq}(A,B)\) toplamlarını aritmetik dizi formülüyle çıkarır ve
$$M_p(A,B)+M_q(A,B)-2M_{pq}(A,B)$$
ifadesini toplam sonuca ekler.
Tüm hesap tam sayı aritmetiğiyle yapılır. C++ sürümü ara değerlerde daha geniş tam sayılar kullanır, Python doğal olarak büyük tamsayıları destekler, Java ise bu problem boyutunda işaretli 64 bit aralığında kalır. Üç sürüm de \(p^2\) artık \(L\)'yi geçtiğinde döngüyü durdurur.
\(N=\lfloor\sqrt L\rfloor+O(1)\) olsun. Bu uygulamalarda asal üretimi lineer-elek tarzında yapıldığı için zaman maliyeti \(O(N)\), bellek maliyeti de \(O(N)\) olur. Ardından gelen ardışık asal çifti taraması, her çift için sabit sayıda işlem yaptığı için \(O(\pi(\sqrt L))\) ek yük getirir ve bu, asal üretiminden küçüktür.
Dolayısıyla toplam karmaşıklık
$$O(\sqrt L)\text{ zaman ve }O(\sqrt L)\text{ bellek}$$
şeklindedir. Asıl kazanç, yaklaşık \(10^{12}\) adayı tek tek denemek yerine yalnızca \(\sqrt L\) çevresindeki asalları dolaşıp her bandı sabit zamanda çözmektir.
Para cada entero \(n\), tomamos los primos consecutivos \(p\) y \(q\) tales que \(p \lt \sqrt n \lt q\). El número \(n\) se llama semidivisible si es divisible por exactamente uno de esos dos primos. Lo que se pide es
$$S(L)=\sum_{\substack{n\le L\\ n\text{ semidivisible}}} n$$
con \(L=999966663333\).
Probar uno por uno casi \(10^{12}\) valores sería inviable. La clave es agrupar los enteros por el par de primos consecutivos que rodea a \(\sqrt n\). Dentro de cada grupo, la condición de semidivisibilidad se transforma en una cuenta limpia con inclusión-exclusión.
Las tres implementaciones usan exactamente la misma idea: partir la recta numérica en franjas delimitadas por cuadrados de primos consecutivos y calcular la contribución de cada franja con una fórmula cerrada.
Si \(p\) y \(q\) son primos consecutivos, entonces
$$p \lt \sqrt n \lt q$$
equivale a
$$p^2 \lt n \lt q^2.$$
Por tanto, cada número relevante pertenece a una única franja entre dos cuadrados de primos consecutivos. En toda esa franja, los primos que rodean a \(\sqrt n\) son siempre los mismos: \(p\) por abajo y \(q\) por arriba. Para un par fijo \((p,q)\), el intervalo útil es
$$A=p^2+1,\qquad B=\min(L,q^2-1).$$
Solo la última franja puede quedar recortada por el límite global \(L\).
Dentro de la franja \((p^2,q^2)\), un número es semidivisible si es múltiplo de \(p\) o de \(q\), pero no de ambos:
$$p\mid n \;\text{ xor }\; q\mid n.$$
Sea \(M_d(A,B)\) la suma de todos los múltiplos de \(d\) en \([A,B]\). Entonces la contribución de la franja es
$$\mathcal{B}(p,q)=M_p(A,B)+M_q(A,B)-2M_{pq}(A,B).$$
La razón es directa. Los múltiplos de \(p\) aparecen una vez en \(M_p\), los de \(q\) una vez en \(M_q\), y los números divisibles por ambos quedan contados dos veces. Como \(p\) y \(q\) son primos distintos, ser divisible por ambos equivale a ser múltiplo de \(pq\). Al restar \(2M_{pq}(A,B)\), desaparecen exactamente esos casos prohibidos.
Para un divisor fijo \(d\), los múltiplos de \(d\) en \([A,B]\) son
$$d\,k_0,\ d(k_0+1),\ \dots,\ d\,k_1,$$
donde
$$k_0=\left\lceil\frac{A}{d}\right\rceil,\qquad k_1=\left\lfloor\frac{B}{d}\right\rfloor.$$
Si \(k_0 \gt k_1\), no hay múltiplos y la suma vale \(0\). En caso contrario, los términos forman una progresión aritmética y se obtiene
$$M_d(A,B)=d\cdot\frac{(k_0+k_1)(k_1-k_0+1)}{2}.$$
Ese es el colapso esencial del problema: cada franja se resuelve con tres sumas cerradas, no enumerando todos sus enteros.
Los primeros pares de primos consecutivos relevantes son \((2,3)\) y \((3,5)\).
Para \((2,3)\), la franja es \(4 \lt n \lt 9\), así que \(A=5\) y \(B=8\). Entonces
$$M_2(5,8)=6+8=14,\qquad M_3(5,8)=6,\qquad M_6(5,8)=6.$$
Por tanto,
$$\mathcal{B}(2,3)=14+6-2\cdot 6=8.$$
El único número semidivisible allí es \(8\); el \(6\) se descarta porque es múltiplo de \(2\) y de \(3\).
Para \((3,5)\), el límite global corta la franja y queda \(10\le n\le 15\). En ese caso
$$M_3(10,15)=12+15=27,\qquad M_5(10,15)=10+15=25,\qquad M_{15}(10,15)=15.$$
Luego
$$\mathcal{B}(3,5)=27+25-2\cdot 15=22,$$
que corresponde a \(10+12\). En total,
$$S(15)=8+22=30.$$
Con la contribución de una franja ya derivada, el problema completo se escribe como
$$S(L)=\sum_{\substack{(p,q)\text{ primos consecutivos}\\ p^2\le L}} \mathcal{B}(p,q).$$
Ningún número semidivisible se genera explícitamente; solo se suman contribuciones de franjas asociadas a pares de primos consecutivos.
Las implementaciones en C++, Python y Java generan primero todos los primos hasta un poco más allá de \(\sqrt L\). Eso basta porque cada franja activa está determinada por un primo \(p\) con \(p^2\le L\) y por el siguiente primo \(q\). Por eso el código prepara una tabla de primos alrededor de \(\sqrt L\) y se asegura de disponer de un primo adicional por encima para cerrar la última franja.
Después recorre los pares consecutivos \((p,q)\). Para cada uno calcula los extremos \(A=p^2+1\) y \(B=\min(L,q^2-1)\). Si \(A\gt B\), no hay aportación. Si no, evalúa \(M_p(A,B)\), \(M_q(A,B)\) y \(M_{pq}(A,B)\) a partir del primer múltiplo, del último múltiplo y de la fórmula de progresión aritmética, y añade
$$M_p(A,B)+M_q(A,B)-2M_{pq}(A,B)$$
al acumulado global.
Todo se hace con aritmética entera. La versión en C++ usa enteros intermedios más amplios, Python usa enteros de precisión arbitraria y Java permanece dentro del rango de 64 bits para este tamaño de entrada. Las tres versiones detienen el proceso cuando \(p^2\) supera \(L\).
Sea \(N=\lfloor\sqrt L\rfloor+O(1)\). En estas implementaciones, la generación de primos usa un método de tipo criba lineal, así que cuesta \(O(N)\) tiempo y \(O(N)\) memoria. El recorrido posterior por pares de primos consecutivos hace trabajo constante por par, por lo que añade \(O(\pi(\sqrt L))\), menor que el coste de la propia criba.
En consecuencia, la complejidad total es
$$O(\sqrt L)\text{ tiempo y }O(\sqrt L)\text{ memoria}.$$
La mejora conceptual es la parte importante: el algoritmo evita revisar casi \(10^{12}\) enteros y los reemplaza por una pasada sobre primos cercanos a \(\sqrt L\), con una cuenta cerrada para cada franja.
对每个整数 \(n\)，设 \(p\) 和 \(q\) 是满足 \(p \lt \sqrt n \lt q\) 的一对相邻素数。如果 \(n\) 恰好能被这两个素数中的一个整除，而不能同时被两个都整除，那么 \(n\) 就称为 semidivisible 数。题目要求计算
$$S(L)=\sum_{\substack{n\le L\\ n\text{ 是 semidivisible 数}}} n$$
其中给定上界 \(L=999966663333\)。
如果对每个 \(n\le L\) 单独寻找 \(\sqrt n\) 两侧的素数，再判断是否满足条件，规模会大到完全不可行。真正有效的做法是把整数按“\(\sqrt n\) 落在哪两个相邻素数之间”来分组。分组以后，每一组都能化成一个固定区间上的整除求和问题。
三份实现使用的是同一个数学框架：先按相邻素数平方之间的区间切分，再为每个区间写出闭式贡献，最后把所有区间加起来。
设 \(p\) 和 \(q\) 是相邻素数，那么
$$p \lt \sqrt n \lt q$$
与
$$p^2 \lt n \lt q^2$$
完全等价。也就是说，每个需要考虑的整数都会唯一地落在某个由相邻素数平方围成的开区间里。在整个这段区间中，\(\sqrt n\) 下方的相邻素数始终是 \(p\)，上方的相邻素数始终是 \(q\)。
因此，对一个固定的相邻素数对 \((p,q)\)，实际需要处理的闭区间可以写成
$$A=p^2+1,\qquad B=\min(L,q^2-1).$$
如果这是最后一个有效区间，它可能会被全局上界 \(L\) 截断；除此之外，所有区间都完整地延伸到 \(q^2-1\)。
一旦区间固定为 \((p^2,q^2)\)，决定 \(n\) 是否 semidivisible 的只剩下两个素数 \(p\) 和 \(q\)。条件可以直接写成
$$p\mid n \;\text{ xor }\; q\mid n.$$
记 \(M_d(A,B)\) 为闭区间 \([A,B]\) 内所有 \(d\) 的倍数之和，那么这个区间的总贡献就是
$$\mathcal{B}(p,q)=M_p(A,B)+M_q(A,B)-2M_{pq}(A,B).$$
原因非常直接。所有 \(p\) 的倍数在 \(M_p\) 中各出现一次，所有 \(q\) 的倍数在 \(M_q\) 中各出现一次。若某个数同时被 \(p\) 和 \(q\) 整除，它就会被重复计算两次。由于 \(p\) 与 \(q\) 是不同的素数，同时被二者整除等价于被 \(pq\) 整除，所以减去 \(2M_{pq}(A,B)\) 恰好把这些不合法的情况全部删掉，只保留“恰好被一个整除”的数。
对任意正整数 \(d\)，区间 \([A,B]\) 内的所有 \(d\) 的倍数一定形如
$$d\,k_0,\ d(k_0+1),\ \dots,\ d\,k_1,$$
其中
$$k_0=\left\lceil\frac{A}{d}\right\rceil,\qquad k_1=\left\lfloor\frac{B}{d}\right\rfloor.$$
如果 \(k_0 \gt k_1\)，说明区间里没有任何 \(d\) 的倍数，于是 \(M_d(A,B)=0\)。否则这些项组成公差为 \(d\) 的等差数列，所以
$$M_d(A,B)=d\cdot\frac{(k_0+k_1)(k_1-k_0+1)}{2}.$$
这一步就是整个题目的核心简化。原来看似需要逐个检查区间中的整数，现在只需要对 \(p\)、\(q\) 和 \(pq\) 各算一次闭式求和。
最前面的两个相邻素数对是 \((2,3)\) 与 \((3,5)\)。
对 \((2,3)\) 而言，区间是 \(4 \lt n \lt 9\)，所以 \(A=5\)，\(B=8\)。这时
$$M_2(5,8)=6+8=14,\qquad M_3(5,8)=6,\qquad M_6(5,8)=6.$$
因此该区间贡献为
$$\mathcal{B}(2,3)=14+6-2\cdot 6=8.$$
这里真正 semidivisible 的只有 \(8\)。数字 \(6\) 虽然能被 \(2\) 整除，也能被 \(3\) 整除，但正因为同时满足两个条件，所以必须剔除。
再看 \((3,5)\)。由于全局上界只有 \(15\)，这个区间被截成 \(10\le n\le 15\)。于是
$$M_3(10,15)=12+15=27,\qquad M_5(10,15)=10+15=25,\qquad M_{15}(10,15)=15.$$
从而
$$\mathcal{B}(3,5)=27+25-2\cdot 15=22,$$
对应的正是 \(10\) 与 \(12\)。把这两段相加，就得到
$$S(15)=8+22=30.$$
区间贡献公式一旦成立，整体答案就是
$$S(L)=\sum_{\substack{(p,q)\text{ 为相邻素数}\\ p^2\le L}} \mathcal{B}(p,q).$$
因此，解法从头到尾都不需要显式枚举所有 semidivisible 数，只需要扫描相邻素数对，并对每个区间做常数次闭式计算。
C++、Python 和 Java 实现都会先生成直到略大于 \(\sqrt L\) 的全部素数。这已经足够，因为每个有效区间都由某个满足 \(p^2\le L\) 的素数 \(p\) 以及它后面的下一个素数 \(q\) 决定。为了处理最后一个有效区间，代码还会确保素数表中确实存在第一个大于 \(\sqrt L\) 的素数。
接下来，程序顺次扫描相邻素数对 \((p,q)\)。对每一对，它计算区间端点 \(A=p^2+1\) 和 \(B=\min(L,q^2-1)\)。如果 \(A\gt B\)，这个区间没有贡献；否则就分别计算 \(M_p(A,B)\)、\(M_q(A,B)\) 和 \(M_{pq}(A,B)\)，然后把
$$M_p(A,B)+M_q(A,B)-2M_{pq}(A,B)$$
加入总和。整个过程中没有任何“逐个测试候选数”的步骤，全部都靠区间端点和等差数列公式直接完成。
实现层面上，三种语言都坚持整数运算。C++ 版本为中间结果使用更宽的整数类型以保证安全，Python 天然支持大整数，Java 在本题给定范围内也能保持 64 位有符号整数安全。循环会在 \(p^2\) 首次超过 \(L\) 时停止。
设 \(N=\lfloor\sqrt L\rfloor+O(1)\)。在这三份实现里，素数生成采用的是线性筛风格的方法，因此建立素数表的代价是 \(O(N)\) 时间和 \(O(N)\) 空间。之后对相邻素数对的扫描，每一对只做常数次运算，所以额外代价是 \(O(\pi(\sqrt L))\)，被前面的筛法成本覆盖。
所以总复杂度为
$$O(\sqrt L)\text{ 时间，}O(\sqrt L)\text{ 空间}.$$
真正重要的是这种结构性降维：它把原本接近 \(10^{12}\) 个候选整数的搜索，压缩成了对 \(\sqrt L\) 附近素数的一次遍历，并且每个区间只用常数时间求解。
Для каждого целого \(n\) рассмотрим соседние простые числа \(p\) и \(q\), удовлетворяющие неравенству \(p \lt \sqrt n \lt q\). Число \(n\) называется semidivisible, если делится ровно на одно из этих двух простых. Требуется вычислить
$$S(L)=\sum_{\substack{n\le L\\ n\text{ semidivisible}}} n$$
при \(L=999966663333\).
Перебирать почти \(10^{12}\) значений по одному бессмысленно. Рабочая идея состоит в том, чтобы сгруппировать числа по той паре соседних простых, которая окружает \(\sqrt n\). После этого условие semidivisible превращается в точный расчёт по интервалу с помощью включения-исключения.
Все три реализации опираются на одну и ту же схему: разбить числа на полосы между квадратами соседних простых, для каждой полосы получить явную формулу вклада и затем просуммировать все полосы.
Если \(p\) и \(q\) — соседние простые, то условие
$$p \lt \sqrt n \lt q$$
эквивалентно условию
$$p^2 \lt n \lt q^2.$$
Значит, каждое подходящее число попадает ровно в одну полосу между квадратами двух соседних простых. Во всей этой полосе нижний окружающий простой остаётся равным \(p\), а верхний — \(q\). Поэтому для фиксированной пары \((p,q)\) удобно работать с границами
$$A=p^2+1,\qquad B=\min(L,q^2-1).$$
Только последняя активная полоса может быть обрезана глобальным пределом \(L\).
Внутри полосы \((p^2,q^2)\) число является semidivisible тогда и только тогда, когда выполняется исключающее условие
$$p\mid n \;\text{ xor }\; q\mid n.$$
Обозначим через \(M_d(A,B)\) сумму всех кратных \(d\) на отрезке \([A,B]\). Тогда вклад полосы равен
$$\mathcal{B}(p,q)=M_p(A,B)+M_q(A,B)-2M_{pq}(A,B).$$
Почему именно так? Кратные \(p\) учитываются в \(M_p\), кратные \(q\) — в \(M_q\). Числа, делящиеся на оба простых сразу, посчитаны дважды. Поскольку \(p\) и \(q\) различны и просты, делимость на оба эквивалентна делимости на \(pq\), и вычитание \(2M_{pq}(A,B)\) как раз убирает запрещённые случаи.
Для фиксированного делителя \(d\) все кратные \(d\) в \([A,B]\) имеют вид
$$d\,k_0,\ d(k_0+1),\ \dots,\ d\,k_1,$$
где
$$k_0=\left\lceil\frac{A}{d}\right\rceil,\qquad k_1=\left\lfloor\frac{B}{d}\right\rfloor.$$
Если \(k_0 \gt k_1\), кратных нет и сумма равна нулю. Иначе мы получаем арифметическую прогрессию, так что
$$M_d(A,B)=d\cdot\frac{(k_0+k_1)(k_1-k_0+1)}{2}.$$
Это и есть решающее упрощение: вместо перебора всех чисел в полосе достаточно вычислить три закрытые формулы для \(p\), \(q\) и \(pq\).
Первые две нужные пары соседних простых — это \((2,3)\) и \((3,5)\).
Для \((2,3)\) имеем полосу \(4 \lt n \lt 9\), то есть \(A=5\) и \(B=8\). Тогда
$$M_2(5,8)=6+8=14,\qquad M_3(5,8)=6,\qquad M_6(5,8)=6.$$
Следовательно,
$$\mathcal{B}(2,3)=14+6-2\cdot 6=8.$$
Это соответствует единственному semidivisible числу \(8\); число \(6\) исключается, потому что делится и на \(2\), и на \(3\).
Для \((3,5)\) глобальный предел укорачивает полосу до \(10\le n\le 15\). Здесь
$$M_3(10,15)=12+15=27,\qquad M_5(10,15)=10+15=25,\qquad M_{15}(10,15)=15.$$
Поэтому
$$\mathcal{B}(3,5)=27+25-2\cdot 15=22,$$
что даёт числа \(10\) и \(12\). В сумме получаем
$$S(15)=8+22=30.$$
После вывода формулы для одной полосы всё решение записывается так:
$$S(L)=\sum_{\substack{(p,q)\text{ соседние простые}\\ p^2\le L}} \mathcal{B}(p,q).$$
То есть алгоритм никогда не строит список всех semidivisible чисел. Он просто проходит по соседним простым и добавляет вклад соответствующей полосы.
Реализации на C++, Python и Java сначала строят список всех простых чисел немного выше \(\sqrt L\). Этого достаточно, потому что каждая активная полоса определяется простым \(p\), для которого \(p^2\le L\), и следующим за ним простым \(q\). Для последней полосы нужен ещё первый простой, превышающий \(\sqrt L\).
Далее программа перебирает соседние пары \((p,q)\). Для каждой пары вычисляются границы \(A=p^2+1\) и \(B=\min(L,q^2-1)\). Если \(A\gt B\), вклад нулевой. Иначе по первому кратному, последнему кратному и формуле арифметической прогрессии находятся \(M_p(A,B)\), \(M_q(A,B)\) и \(M_{pq}(A,B)\), после чего к ответу прибавляется
$$M_p(A,B)+M_q(A,B)-2M_{pq}(A,B).$$
Все вычисления остаются целочисленными. В версии на C++ используются более широкие промежуточные целые типы, Python полагается на длинную арифметику, а Java укладывается в 64-битный диапазон для этого ограничения. Перебор завершается, как только \(p^2\) становится больше \(L\).
Пусть \(N=\lfloor\sqrt L\rfloor+O(1)\). В этих реализациях генерация простых выполняется методом линейного решета, поэтому требует \(O(N)\) времени и \(O(N)\) памяти. Последующий проход по соседним простым парам делает лишь константное число операций на пару, то есть добавляет \(O(\pi(\sqrt L))\), что меньше стоимости построения решета.
Итак, полная сложность равна
$$O(\sqrt L)\text{ по времени и }O(\sqrt L)\text{ по памяти}.$$
Главное достижение алгоритма — не только в формальной асимптотике, но и в правильном представлении задачи: вместо перебора почти \(10^{12}\) кандидатов он работает только с простыми около \(\sqrt L\) и обрабатывает каждую полосу за постоянное время.
لكل عدد صحيح \(n\)، نأخذ العددين الأوليين المتتاليين \(p\) و\(q\) اللذين يحققان \(p \lt \sqrt n \lt q\). يسمى \(n\) عددًا semidivisible إذا كان يقبل القسمة على واحد فقط من هذين الأوليين. المطلوب هو حساب
$$S(L)=\sum_{\substack{n\le L\\ n\text{ semidivisible}}} n$$
عند الحد \(L=999966663333\).
فحص كل عدد حتى هذا الحد مباشرة غير عملي تمامًا. الفكرة الصحيحة هي تجميع الأعداد بحسب الزوج الأولي المتتالي الذي يحيط بـ \(\sqrt n\). بعد هذا التجميع يصبح الشرط semidivisible مسألة جمع لمضاعفات على مجال ثابت باستخدام الشمول والاستبعاد.
البرامج الثلاثة تبني الحل بالطريقة نفسها: تقسيم الأعداد إلى شرائح بين مربعات أولية متتالية، ثم حساب مساهمة كل شريحة بصيغة مغلقة، ثم جمع جميع الشرائح.
إذا كان \(p\) و\(q\) أوليين متتاليين، فإن الشرط
$$p \lt \sqrt n \lt q$$
يكافئ تمامًا الشرط
$$p^2 \lt n \lt q^2.$$
إذن كل عدد مطلوب يقع في شريحة واحدة فقط بين مربعين متتاليين لعددين أوليين. داخل هذه الشريحة كلها يبقى الأولي السفلي هو \(p\) والأولي العلوي هو \(q\). لذلك، من أجل زوج ثابت \((p,q)\)، يكون المجال العملي
$$A=p^2+1,\qquad B=\min(L,q^2-1).$$
وقد تُقطع الشريحة الأخيرة فقط بسبب الحد العالمي \(L\).
داخل الشريحة \((p^2,q^2)\)، يكون العدد semidivisible إذا كان من مضاعفات \(p\) أو من مضاعفات \(q\)، لكن ليس من مضاعفاتهما معًا:
$$p\mid n \;\text{ xor }\; q\mid n.$$
لنرمز بـ \(M_d(A,B)\) إلى مجموع جميع مضاعفات \(d\) في المجال \([A,B]\). عندئذ تكون مساهمة الشريحة
$$\mathcal{B}(p,q)=M_p(A,B)+M_q(A,B)-2M_{pq}(A,B).$$
التفسير مباشر: مضاعفات \(p\) تظهر مرة في \(M_p\)، ومضاعفات \(q\) تظهر مرة في \(M_q\). أما الأعداد التي تقبل القسمة على كليهما فقد عُدَّت مرتين. وبما أن \(p\) و\(q\) أوليان مختلفان، فإن القابلية للقسمة على كليهما تعني القابلية للقسمة على \(pq\)، ولذلك فإن طرح \(2M_{pq}(A,B)\) يزيل الحالات الممنوعة بالضبط.
لأي مقسوم عليه ثابت \(d\)، فإن مضاعفات \(d\) داخل \([A,B]\) تأخذ الشكل
$$d\,k_0,\ d(k_0+1),\ \dots,\ d\,k_1,$$
حيث
$$k_0=\left\lceil\frac{A}{d}\right\rceil,\qquad k_1=\left\lfloor\frac{B}{d}\right\rfloor.$$
إذا كان \(k_0 \gt k_1\)، فلا توجد أي مضاعفات ويكون المجموع صفرًا. وإلا فإن الحدود تشكل متتالية حسابية، ومن ثم
$$M_d(A,B)=d\cdot\frac{(k_0+k_1)(k_1-k_0+1)}{2}.$$
هذه هي نقطة الحسم في الحل: بدل المرور على كل عدد في الشريحة، نحسب ثلاث صيغ مغلقة فقط، واحدة لـ \(p\) وواحدة لـ \(q\) وواحدة لـ \(pq\).
أول زوجين أوليين متتاليين نحتاجهما هما \((2,3)\) و\((3,5)\).
بالنسبة إلى \((2,3)\)، تكون الشريحة \(4 \lt n \lt 9\)، أي \(A=5\) و\(B=8\). إذن
$$M_2(5,8)=6+8=14,\qquad M_3(5,8)=6,\qquad M_6(5,8)=6.$$
ومن ثم
$$\mathcal{B}(2,3)=14+6-2\cdot 6=8.$$
العدد semidivisible الوحيد هنا هو \(8\). أما \(6\) فيُستبعد لأنه يقبل القسمة على \(2\) و\(3\) معًا.
أما بالنسبة إلى \((3,5)\)، فإن الحد العالمي يقطع الشريحة لتصبح \(10\le n\le 15\). في هذه الحالة
$$M_3(10,15)=12+15=27,\qquad M_5(10,15)=10+15=25,\qquad M_{15}(10,15)=15.$$
ولذلك
$$\mathcal{B}(3,5)=27+25-2\cdot 15=22,$$
وهذا يساوي \(10+12\). وبجمع الشريحتين نحصل على
$$S(15)=8+22=30.$$
بعد اشتقاق مساهمة الشريحة الواحدة، تصبح الإجابة الكاملة
$$S(L)=\sum_{\substack{(p,q)\text{ consecutive primes}\\ p^2\le L}} \mathcal{B}(p,q).$$
أي أن الحل لا يولد الأعداد semidivisible واحدًا واحدًا، بل يجمع فقط مساهمات الشرائح المرتبطة بالأزواج الأولية المتتالية.
تبدأ تطبيقات C++ وPython وJava بتوليد جميع الأعداد الأولية حتى ما بعد \(\sqrt L\) بقليل. هذا يكفي لأن كل شريحة فعالة تحددها قيمة أولية \(p\) تحقق \(p^2\le L\) ومعها الأولي التالي \(q\). ومن أجل إغلاق الشريحة الأخيرة، تتأكد الشيفرة أيضًا من وجود أول عدد أولي أكبر من \(\sqrt L\).
بعد ذلك تمر الشيفرة على الأزواج المتتالية \((p,q)\). لكل زوج تُحسب نهايتا المجال \(A=p^2+1\) و\(B=\min(L,q^2-1)\). إذا كان \(A\gt B\)، فلا توجد مساهمة. وإلا تُحسب القيم \(M_p(A,B)\) و\(M_q(A,B)\) و\(M_{pq}(A,B)\) مباشرة من أول مضاعف وآخر مضاعف وصيغة المتتالية الحسابية، ثم يُضاف المقدار
$$M_p(A,B)+M_q(A,B)-2M_{pq}(A,B)$$
إلى المجموع الكلي.
كل الحسابات تبقى ضمن الحساب الصحيح على الأعداد الصحيحة. تستخدم نسخة C++ أنواعًا أوسع للقيم الوسيطة، ويستفيد Python من الأعداد الصحيحة كبيرة الحجم، بينما تبقى Java ضمن مجال 64 بت الموقّع لهذه المسألة. وتتوقف الحلقة عندما يصبح \(p^2\) أكبر من \(L\).
لنكتب \(N=\lfloor\sqrt L\rfloor+O(1)\). في هذه التطبيقات، توليد الأوليات يتم بطريقة من نمط الغربال الخطي، ولذلك تكلفته \(O(N)\) زمنًا و\(O(N)\) ذاكرة. أما المرور اللاحق على الأزواج الأولية المتتالية فينفذ عددًا ثابتًا من العمليات لكل زوج، أي يضيف \(O(\pi(\sqrt L))\)، وهو أصغر من تكلفة بناء قائمة الأوليات نفسها.
إذن التعقيد الكلي هو
$$O(\sqrt L)\text{ time and }O(\sqrt L)\text{ memory}.$$
لكن المكسب الأهم هو التحويل البنيوي للمسألة: بدل فحص ما يقارب \(10^{12}\) عددًا، يمر الحل على الأوليات القريبة من \(\sqrt L\) فقط، ويعالج كل شريحة في زمن ثابت.