We must sum all integers \(n \le 10^8\) such that for every divisor \(d \mid n\), the quantity
$$d+\frac{n}{d}$$
is prime. A naive search would test every \(n\) and every divisor pair, which is far too slow at this bound. The local C++, Python, and Java solutions instead combine number-theoretic filters with a prime sieve so that only a much smaller family of candidates is checked in full.
If \(n\) satisfies the condition for every divisor, then in particular the choice \(d=1\) forces
$$1+\frac{n}{1}=n+1$$
to be prime. Therefore every valid value must be of the form
$$n=p-1 \qquad (p \text{ prime}).$$
This already removes almost all integers from consideration. It also explains why the implementations iterate over primes and test \(n=p-1\) rather than scanning every \(n\) directly.
The prime \(n+1\) is larger than \(2\) unless \(n=1\). Hence \(n+1\) is odd, so every valid \(n>1\) must be even. Now suppose \(4 \mid n\). Taking \(d=2\) gives
$$2+\frac{n}{2}.$$
Because \(n/2\) is then even, this value is an even integer greater than \(2\), so it cannot be prime. Thus every valid \(n>1\) satisfies
$$n \equiv 2 \pmod 4.$$
This is exactly the fast rejection implemented by the line that discards numbers with \((n \mathbin{\&} 3) = 0\).
Assume an odd prime \(q\) satisfies \(q^2 \mid n\). Choosing \(d=q\) gives
$$q+\frac{n}{q}=q\left(1+\frac{n}{q^2}\right).$$
The second factor is an integer at least \(2\), so the whole expression is a multiple of \(q\) larger than \(q\), hence composite. Therefore no odd prime square can divide a valid \(n\).
Combined with the previous step, this shows that every valid \(n>1\) is squarefree and contains the prime \(2\) exactly once. The code mirrors this proof: after factoring \(n/2\), it immediately rejects the candidate if the same odd prime appears twice.
Once a candidate survives the cheap filters, the remaining condition is still
$$d+\frac{n}{d}\text{ is prime for all }d \mid n.$$
Divisors come in pairs \((d,n/d)\), and both members of the pair produce the same sum. So it is enough to test only the divisors with
$$d \le \frac{n}{d} \qquad \Longleftrightarrow \qquad d \le \sqrt{n}.$$
For example, \(n=30\) has divisor pairs \((1,30)\), \((2,15)\), \((3,10)\), and \((5,6)\). The corresponding values are \(31,17,13,11\), all prime, so \(30\) contributes to the final sum.
For fixed \(n\), define \(f(d)=d+n/d\). On the interval \(1 \le d \le \sqrt{n}\), this function decreases, so the largest relevant value occurs at \(d=1\):
$$d+\frac{n}{d} \le n+1.$$
Since the search limit is \(n \le 10^8\), every primality query lies in the range \([2,10^8+1]\). That is why all three implementations build a prime sieve only once, up to LIMIT + 1, and then answer every primality test by constant-time table lookup.
The three local solution files implement the same pipeline.
First, they generate a sieve of primes up to LIMIT + 1.
Second, they consider only candidates of the form n = p - 1 with \(p\) prime.
Third, the helper check_n or checkN performs the exact mathematical tests above:
$$n=1 \Rightarrow \text{accept}, \qquad n \text{ odd } \Rightarrow \text{reject}, \qquad 4 \mid n \Rightarrow \text{reject}.$$
Then it writes \(n=2m\) and factors the odd number \(m\) using an SPF table stored only for odd indices. If an odd prime factor repeats, the candidate is rejected because the odd part is not squarefree. Otherwise the code builds all divisors from the distinct prime factors and checks whether
$$d+\frac{n}{d}$$
is prime for every divisor pair.
The C++ and Java versions explicitly materialize the prime list and split it into chunks for parallel processing. Each worker accumulates a partial sum over its assigned primes and the totals are added at the end. The Python version keeps the same mathematics but loops through the sieve array serially.
The SPF structure is also implementation-specific but mathematically identical. After dividing by \(2\), the remaining factor \(m\) is odd, so the code stores the smallest prime factor of an odd integer \(x\) at position \(x/2\). If the stored value is \(0\), the remainder itself is prime. This gives a compact and fast way to factor each candidate without trial division.
The dominant preprocessing cost is building the prime sieve up to \(10^8+1\) and the odd-only SPF table up to \(10^8/2\). Both are sieve-style preprocesses with near-linear behavior, typically summarized as \(O(N \log \log N)\) time and \(O(N)\) memory for the global bound \(N=10^8\).
After preprocessing, the algorithm examines only \(\pi(N+1)\) candidates because every valid \(n\) must equal \(p-1\). Factoring a surviving candidate touches only its distinct prime factors, and divisor generation costs \(O(2^{\omega(n)})\), where \(\omega(n)\) is the number of distinct prime divisors. The squarefree restriction keeps \(\omega(n)\) small in practice, so the expensive full divisor test is applied to a very manageable set of numbers.
Gesucht ist die Summe aller ganzen Zahlen \(n \le 10^8\), für die für jeden Teiler \(d \mid n\) der Ausdruck
$$d+\frac{n}{d}$$
eine Primzahl ist. Eine direkte Vollsuche über alle \(n\) und alle Teilerpaare wäre viel zu langsam. Die lokalen C++-, Python- und Java-Lösungen reduzieren den Suchraum deshalb zuerst mit zwingenden zahlentheoretischen Bedingungen und führen den vollständigen Teilertest nur noch für wenige Kandidaten aus.
Wenn \(n\) die Bedingung für alle Teiler erfüllt, dann insbesondere für \(d=1\). Also muss
$$1+\frac{n}{1}=n+1$$
prim sein. Jede zulässige Zahl hat daher die Form
$$n=p-1 \qquad (p \text{ prim}).$$
Genau deshalb iteriert der Code nicht über alle ganzen Zahlen, sondern über Primzahlen \(p\) und untersucht nur \(n=p-1\).
Außer im Sonderfall \(n=1\) ist die Primzahl \(n+1\) größer als \(2\) und damit ungerade. Also muss jedes gültige \(n>1\) gerade sein. Angenommen nun \(4 \mid n\). Dann erhält man für \(d=2\)
$$2+\frac{n}{2}.$$
Da \(n/2\) dann gerade ist, ist dieser Wert eine gerade Zahl größer als \(2\) und somit nicht prim. Folglich gilt für alle gültigen \(n>1\)
$$n \equiv 2 \pmod 4.$$
Im Programm entspricht das dem sehr billigen Filter \((n \mathbin{\&} 3) == 0\).
Sei \(q\) eine ungerade Primzahl mit \(q^2 \mid n\). Wählt man \(d=q\), so folgt
$$q+\frac{n}{q}=q\left(1+\frac{n}{q^2}\right).$$
Der zweite Faktor ist eine ganze Zahl von mindestens \(2\). Also ist der gesamte Ausdruck ein echtes Vielfaches von \(q\) und damit zusammengesetzt. Deshalb darf keine ungerade Primzahl mit Exponent mindestens \(2\) in \(n\) auftreten.
Zusammen mit dem Ausschluss von \(4 \mid n\) ergibt sich: Jedes gültige \(n>1\) ist gerade und quadratfrei, wobei die Primzahl \(2\) genau einmal vorkommt. Genau diese Eigenschaft prüft der Code, indem er beim Faktorisieren von \(n/2\) sofort abbricht, sobald derselbe ungerade Primfaktor zweimal erscheint.
Nach den schnellen Filtern bleibt weiterhin die Forderung
$$d+\frac{n}{d}\text{ ist prim für alle }d \mid n.$$
Da die Teiler in Paaren \((d,n/d)\) auftreten und beide denselben Summenwert liefern, genügt es, nur die eine Hälfte zu testen:
$$d \le \frac{n}{d} \qquad \Longleftrightarrow \qquad d \le \sqrt{n}.$$
Für \(n=30\) sind die relevanten Paare \((1,30)\), \((2,15)\), \((3,10)\) und \((5,6)\). Daraus entstehen \(31,17,13,11\), also ausschließlich Primzahlen. Deshalb trägt \(30\) zur Summe bei.
Für festes \(n\) setze \(f(d)=d+n/d\). Auf dem Bereich \(1 \le d \le \sqrt{n}\) ist diese Funktion fallend, also liegt der größte relevante Wert bei \(d=1\):
$$d+\frac{n}{d} \le n+1.$$
Da im Problem \(n \le 10^8\) gilt, reichen Primtests bis \(10^8+1\) vollkommen aus. Genau deswegen bauen alle drei Implementierungen nur einmal ein Sieb bis LIMIT + 1 auf und beantworten anschließend jede Primanfrage per Tabellenzugriff.
Die drei lokalen Lösungen setzen dieselbe Argumentation fast Zeile für Zeile um.
Zuerst wird ein Primzahlsieb bis LIMIT + 1 erzeugt.
Danach werden ausschließlich Kandidaten der Form n = p - 1 betrachtet.
Die Funktion check_n beziehungsweise checkN führt dann genau diese Tests aus:
$$n=1 \Rightarrow \text{akzeptieren}, \qquad n \text{ ungerade } \Rightarrow \text{verwerfen}, \qquad 4 \mid n \Rightarrow \text{verwerfen}.$$
Anschließend wird \(n=2m\) geschrieben und das ungerade \(m\) mit einer SPF-Tabelle für ungerade Zahlen faktorisiert. Sobald ein ungerader Primfaktor doppelt auftritt, wird der Kandidat wegen fehlender Quadratfreiheit abgelehnt. Sonst erzeugt der Code aus den verschiedenen Primfaktoren alle Teiler und prüft für jedes relevante Teilerpaar die Primzahlbedingung.
Die C++- und Java-Versionen materialisieren zunächst die Primzahlliste und teilen sie dann für parallele Verarbeitung in Blöcke auf. Jeder Thread beziehungsweise jede Task bildet eine lokale Teilsumme; am Ende werden diese Beiträge addiert. Die Python-Version ist mathematisch identisch, arbeitet aber seriell über das Siebarray.
Auch die SPF-Struktur ist bewusst kompakt. Nach dem Herausziehen des Faktors \(2\) bleibt wegen \(4 \nmid n\) nur noch eine ungerade Zahl \(m\) übrig. Daher speichert das Programm den kleinsten Primfaktor einer ungeraden Zahl \(x\) an der Position \(x/2\). Ein Eintrag \(0\) bedeutet, dass der Rest selbst prim ist. So wird jede Kandidatenzahl ohne teure Probedivision zerlegt.
Der Hauptaufwand liegt in der Vorverarbeitung: Primzahlsieb bis \(10^8+1\) und SPF-Sieb für ungerade Zahlen bis \(10^8/2\). Beide Schritte verhalten sich wie klassische Siebe und benötigen näherungsweise \(O(N \log \log N)\) Zeit sowie \(O(N)\) Speicher für die globale Schranke \(N=10^8\).
Danach werden nur noch \(\pi(N+1)\) Kandidaten geprüft, weil jedes gültige \(n\) die Form \(p-1\) haben muss. Das Faktorisieren eines Kandidaten kostet nur die Verarbeitung seiner verschiedenen Primteiler, und das Erzeugen aller Teiler benötigt \(O(2^{\omega(n)})\). Wegen der Quadratfreiheit bleibt \(\omega(n)\) in der Praxis klein, sodass der vollständige Teilertest auf eine handhabbare Menge von Fällen beschränkt ist.
Aranan şey, \(n \le 10^8\) koşulunu sağlayan tüm tamsayılar arasında, her bölen \(d \mid n\) için
$$d+\frac{n}{d}$$
ifadesi asal olanların toplamıdır. Tüm sayıları ve tüm bölen çiftlerini kaba kuvvetle denemek bu sınırda pratik değildir. Depodaki C++, Python ve Java çözümleri bunun yerine önce güçlü zorunlu koşullarla adayları azaltır, sonra yalnızca kalan az sayıdaki aday için tam bölen kontrolü yapar.
Eğer bir \(n\) her bölen için koşulu sağlıyorsa, özellikle \(d=1\) için de sağlamalıdır. Bu da
$$1+\frac{n}{1}=n+1$$
sayısının asal olmasını zorunlu kılar. Dolayısıyla her geçerli aday
$$n=p-1 \qquad (p \text{ asal})$$
biçimindedir. Kodun doğrudan tüm \(n\) değerlerini gezmek yerine asal sayılar üzerinden ilerlemesinin nedeni tam olarak budur.
\(n=1\) dışında, \(n+1\) asal sayısı \(2\)'den büyüktür ve bu yüzden tektir. O halde her geçerli \(n>1\) çift olmalıdır. Şimdi \(4 \mid n\) olduğunu varsayalım. \(d=2\) seçersek
$$2+\frac{n}{2}$$
elde edilir. Bu değer çift ve \(2\)'den büyüktür; dolayısıyla asal olamaz. Sonuç olarak geçerli tüm \(n>1\) için
$$n \equiv 2 \pmod 4$$
zorunludur. Çözüm dosyalarındaki hızlı bit işlemi testi tam olarak bu eleği uygular.
Bir tek asal \(q\) için \(q^2 \mid n\) olsun. \(d=q\) seçildiğinde
$$q+\frac{n}{q}=q\left(1+\frac{n}{q^2}\right)$$
olur. İkinci çarpan en az \(2\) olan bir tamsayıdır; bu yüzden tüm ifade \(q\)'nun kendisinden büyük bir katıdır ve bileşiktir. Demek ki geçerli bir \(n\)'de hiçbir tek asalın karesi bulunamaz.
\(4 \nmid n\) sonucu ile birleştirince şu sonuca ulaşırız: \(n>1\) için geçerli her sayı çift ve kare-serbesttir; \(2\) çarpanı yalnızca bir kez gelir. Kod, \(n/2\)'yi çarpanlara ayırırken aynı tek asal ikinci kez görünür görünmez adayı reddederek bu matematiksel sonucu doğrudan kullanır.
Ucuz elemeden sonra hâlâ şu koşulun tamamını doğrulamak gerekir:
$$d+\frac{n}{d}\text{ her }d \mid n\text{ için asal olmalıdır.}$$
Bölenler \((d,n/d)\) çiftleri halinde gelir ve her iki bölen de aynı toplamı üretir. Bu nedenle yalnızca
$$d \le \frac{n}{d} \qquad \Longleftrightarrow \qquad d \le \sqrt{n}$$
koşulunu sağlayan bölenleri kontrol etmek yeterlidir. Örneğin \(n=30\) için ilgili çiftler \((1,30)\), \((2,15)\), \((3,10)\) ve \((5,6)\)'dır. Karşılık gelen toplamlar \(31,17,13,11\) olup hepsi asaldır; bu yüzden \(30\) toplama dahil edilir.
Sabit bir \(n\) için \(f(d)=d+n/d\) tanımlayalım. \(1 \le d \le \sqrt{n}\) aralığında bu fonksiyon azalır; bu yüzden en büyük gerekli değer \(d=1\) noktasında oluşur:
$$d+\frac{n}{d} \le n+1.$$
Problemde \(n \le 10^8\) olduğundan tüm asal sorguları en fazla \(10^8+1\)'e kadar gider. Çözümlerin yalnızca bir kez LIMIT + 1 boyutunda asal süzgeci kurmasının nedeni budur.
Üç yerel çözüm dosyası aynı işlem hattını uygular.
Önce LIMIT + 1'e kadar asal tablosu oluşturulur.
Sonra sadece n = p - 1 biçimindeki adaylar denenir.
Ardından check_n veya checkN yardımcı fonksiyonu şu mantığı izler:
$$n=1 \Rightarrow \text{kabul}, \qquad n \text{ tek } \Rightarrow \text{ret}, \qquad 4 \mid n \Rightarrow \text{ret}.$$
Daha sonra \(n=2m\) yazılır ve tek sayı olan \(m\), yalnızca tek indisler için tutulan SPF tablosu ile çarpanlara ayrılır. Aynı tek asal iki kez görülürse aday kare-serbest olmadığı için elenir. Aksi halde farklı asal çarpanlardan tüm bölenler üretilir ve her bölen çifti için asal testi yapılır.
C++ ve Java sürümleri asal listesini açıkça oluşturup bunu parçalara ayırarak paralel toplama yapar. Her iş parçacığı kendi yerel toplamını hesaplar; sonunda bu toplamlar birleştirilir. Python sürümü ise aynı matematiği korur fakat asal tablosu üzerinde seri dolaşır.
SPF yapısı da önemli bir ayrıntıdır. \(2\) çarpanı çıkarıldıktan sonra geriye yalnızca tek sayı \(m\) kaldığı için program, tek bir \(x\) sayısının en küçük asal çarpanını \(x/2\) konumunda saklar. Eğer bu değer \(0\) ise, elde kalan sayı zaten asaldır. Böylece deneme bölmesi yapmadan hızlı çarpanlara ayırma mümkün olur.
Ana maliyet, \(10^8+1\)'e kadar asal süzgeci ile \(10^8/2\)'ye kadar tek-sayı SPF tablosunu kurmaktır. Bunlar klasik süzgeç benzeri işlemler olduğundan toplam ön işleme maliyeti pratikte \(O(N \log \log N)\) zaman ve \(O(N)\) bellek olarak özetlenir.
Bu aşamadan sonra algoritma yalnızca \(\pi(N+1)\) kadar aday inceler; çünkü geçerli her \(n\), \(p-1\) biçiminde olmalıdır. Bir adayın çarpanlara ayrılması farklı asal sayısı kadar iş gerektirir ve tüm bölenlerin üretilmesi \(O(2^{\omega(n)})\) maliyetlidir. Kare-serbestlik filtresi \(\omega(n)\)'yi küçük tuttuğu için tam doğrulama adımı uygulamada yeterince hızlıdır.
Debemos sumar todos los enteros \(n \le 10^8\) tales que, para cada divisor \(d \mid n\), la cantidad
$$d+\frac{n}{d}$$
sea prima. Una búsqueda ingenua probaría cada \(n\) y todos sus divisores, lo cual es demasiado costoso. Los archivos locales en C++, Python y Java reducen primero el espacio de búsqueda con condiciones necesarias muy fuertes y solo después realizan la comprobación completa de divisores.
Si un número \(n\) cumple la condición para todos sus divisores, entonces en particular debe cumplirla para \(d=1\). Por tanto
$$1+\frac{n}{1}=n+1$$
debe ser primo. Luego todo candidato válido tiene la forma
$$n=p-1 \qquad (p \text{ primo}).$$
Esta observación explica por qué el programa recorre primos \(p\) y examina \(n=p-1\) en vez de probar todos los enteros uno por uno.
Salvo el caso especial \(n=1\), el primo \(n+1\) es mayor que \(2\), así que es impar. En consecuencia, todo \(n>1\) válido debe ser par. Supongamos ahora que \(4 \mid n\). Tomando \(d=2\) obtenemos
$$2+\frac{n}{2}.$$
Como \(n/2\) sería par, ese valor también es par y mayor que \(2\), luego no puede ser primo. Por eso, para todo \(n>1\) válido se cumple
$$n \equiv 2 \pmod 4.$$
Este criterio aparece literalmente en la implementación mediante un rechazo inmediato de los múltiplos de \(4\).
Supongamos que un primo impar \(q\) satisface \(q^2 \mid n\). Si elegimos \(d=q\), entonces
$$q+\frac{n}{q}=q\left(1+\frac{n}{q^2}\right).$$
El segundo factor es un entero de al menos \(2\), por lo que toda la expresión es un múltiplo de \(q\) mayor que \(q\), es decir, compuesto. En consecuencia, ningún primo impar puede aparecer con exponente al menos \(2\) en un \(n\) válido.
Junto con la prohibición de \(4 \mid n\), esto implica que todo \(n>1\) válido es par y libre de cuadrados, con el factor \(2\) apareciendo exactamente una vez. La rutina de factorización usa justo esta idea: si detecta un primo impar repetido en \(n/2\), rechaza el candidato de inmediato.
Tras los filtros rápidos todavía hay que verificar la condición completa
$$d+\frac{n}{d}\text{ es primo para todo }d \mid n.$$
Los divisores aparecen en pares \((d,n/d)\), y ambos producen la misma suma. Por ello basta revisar solo la mitad:
$$d \le \frac{n}{d} \qquad \Longleftrightarrow \qquad d \le \sqrt{n}.$$
Por ejemplo, para \(n=30\) los pares relevantes son \((1,30)\), \((2,15)\), \((3,10)\) y \((5,6)\). Las sumas correspondientes son \(31,17,13,11\), todas primas, de modo que \(30\) sí contribuye a la suma total.
Fijado \(n\), definamos \(f(d)=d+n/d\). En el intervalo \(1 \le d \le \sqrt{n}\), esta función decrece, de modo que el mayor valor relevante aparece en \(d=1\):
$$d+\frac{n}{d} \le n+1.$$
Como el límite global es \(n \le 10^8\), toda consulta de primalidad queda dentro de \([2,10^8+1]\). Por eso las tres soluciones construyen una única tabla de primalidad hasta LIMIT + 1 y luego responden cada consulta en tiempo constante.
Los tres programas locales siguen el mismo esquema.
Primero construyen una criba de primos hasta LIMIT + 1.
Después consideran solo candidatos de la forma n = p - 1.
La función auxiliar check_n o checkN aplica exactamente los filtros matemáticos anteriores:
$$n=1 \Rightarrow \text{aceptar}, \qquad n \text{ impar } \Rightarrow \text{rechazar}, \qquad 4 \mid n \Rightarrow \text{rechazar}.$$
Luego escribe \(n=2m\) y factoriza el número impar \(m\) usando una tabla SPF almacenada solo para índices impares. Si un primo impar se repite, el candidato se descarta por no ser libre de cuadrados. En caso contrario, el código genera todos los divisores a partir de los factores distintos y comprueba la primalidad de cada suma \(d+n/d\).
Las versiones de C++ y Java construyen explícitamente la lista de primos y la dividen en bloques para sumar en paralelo. Cada hilo o tarea acumula una suma parcial y al final se combinan todos los resultados. La versión de Python mantiene el mismo razonamiento matemático, pero recorre la criba de forma secuencial.
La estructura SPF también está optimizada. Una vez extraído el factor \(2\), el resto \(m\) es impar, así que el menor factor primo de un impar \(x\) se guarda en la posición \(x/2\). Si esa entrada vale \(0\), el resto actual ya es primo. Esto permite factorizar cada candidato con mucha rapidez y sin divisiones de prueba costosas.
El coste dominante es el preprocesamiento: construir la criba de primos hasta \(10^8+1\) y la tabla SPF para impares hasta \(10^8/2\). Ambos pasos se comportan como cribas clásicas, por lo que el coste global se resume como \(O(N \log \log N)\) en tiempo y \(O(N)\) en memoria para el límite \(N=10^8\).
Después del preprocesamiento solo se examinan \(\pi(N+1)\) candidatos, porque todo \(n\) válido debe escribirse como \(p-1\). Factorizar un candidato requiere procesar solo sus primos distintos, y generar todos sus divisores cuesta \(O(2^{\omega(n)})\). La restricción de ser libre de cuadrados mantiene pequeño a \(\omega(n)\), de modo que la verificación completa resulta práctica.
目标是求出所有满足 \(n \le 10^8\) 的整数之和，并且这些整数必须对每个约数 \(d \mid n\) 都满足
$$d+\frac{n}{d}$$
为素数。直接枚举每个 \(n\) 再枚举其全部约数对，在这个范围内代价过高。仓库中的 C++、Python 和 Java 解法都先利用若干必要条件大幅缩小候选集合，再对少量剩余候选做完整验证。
如果某个 \(n\) 对所有约数都满足条件，那么对 \(d=1\) 当然也必须成立，于是
$$1+\frac{n}{1}=n+1$$
必须是素数。因此每个可行的 \(n\) 都必定形如
$$n=p-1 \qquad (p \text{ 为素数}).$$
这一步已经把候选从“全部整数”压缩成“素数减一”。这也解释了为什么代码是先筛素数，再测试 \(n=p-1\)，而不是顺序扫描每个 \(n\)。
除了特殊值 \(n=1\) 以外，\(n+1\) 是大于 \(2\) 的素数，所以它必为奇数，从而 \(n\) 必为偶数。再进一步，若 \(4 \mid n\)，取 \(d=2\) 就得到
$$2+\frac{n}{2}.$$
此时 \(n/2\) 为偶数，因此这个值也是大于 \(2\) 的偶数，不可能是素数。故所有有效的 \(n>1\) 都满足
$$n \equiv 2 \pmod 4.$$
源码中的位运算快速判断，正是在实现这个必要条件。
设某个奇素数 \(q\) 满足 \(q^2 \mid n\)。选择 \(d=q\)，则
$$q+\frac{n}{q}=q\left(1+\frac{n}{q^2}\right).$$
右侧第二个因子是至少为 \(2\) 的整数，所以整个表达式是一个大于 \(q\) 的 \(q\) 的倍数，因此一定是合数。这说明有效的 \(n\) 不能含有任何奇素数平方因子。
再结合 \(4 \nmid n\)，可知每个有效的 \(n>1\) 都是偶数且平方自由，素因子 \(2\) 只出现一次。代码中对 \(n/2\) 做分解时，一旦发现同一个奇素因子出现两次，就立即拒绝该候选，这与上面的证明完全一致。
通过快速筛选以后，仍需验证完整条件
$$d+\frac{n}{d}\text{ 对所有 }d \mid n\text{ 都是素数。}$$
由于约数总是成对出现为 \((d,n/d)\)，而这两个约数给出的和完全相同，所以只检查一侧即可：
$$d \le \frac{n}{d} \qquad \Longleftrightarrow \qquad d \le \sqrt{n}.$$
例如 \(n=30\) 时，只需看 \((1,30)\)、\((2,15)\)、\((3,10)\)、\((5,6)\) 这四组。对应的值分别是 \(31,17,13,11\)，全部都是素数，因此 \(30\) 会被计入最终答案。
固定 \(n\) 后，令 \(f(d)=d+n/d\)。在区间 \(1 \le d \le \sqrt{n}\) 上，这个函数单调下降，所以最大相关值出现在 \(d=1\)：
$$d+\frac{n}{d} \le n+1.$$
因为题目给出 \(n \le 10^8\)，所有素性查询都不会超过 \(10^8+1\)。因此三个实现都只构造一次到 LIMIT + 1 的素数筛表，之后所有判断都可以直接查表完成。
三个本地解法使用完全相同的数学流程。
首先建立到 LIMIT + 1 为止的素数筛。
其次只考虑形如 n = p - 1 的候选。
然后辅助函数 check_n 或 checkN 按照下面的顺序执行判断：
$$n=1 \Rightarrow \text{接受}, \qquad n \text{ 为奇数 } \Rightarrow \text{拒绝}, \qquad 4 \mid n \Rightarrow \text{拒绝}.$$
接着写成 \(n=2m\)，并利用只为奇数建立的 SPF 表分解奇数 \(m\)。如果某个奇素因子重复出现，则因为不是平方自由数而直接失败。否则，程序根据不同素因子生成全部约数，并对每个约数对检查 \(d+n/d\) 是否为素数。
C++ 和 Java 版本会先显式生成素数列表，再把列表切成若干块并行处理。每个线程或任务计算自己的局部和，最后汇总得到总答案。Python 版本保留同样的数学逻辑，但采用串行遍历筛表的方式。
SPF 结构同样体现了实现细节。由于先提取了因子 \(2\)，剩余的 \(m\) 一定是奇数，因此代码把奇数 \(x\) 的最小素因子存放在位置 \(x/2\)。如果该位置的值为 \(0\)，说明当前剩余部分本身就是素数。这样就能避免昂贵的试除过程，实现快速分解。
主要开销来自预处理，即构建到 \(10^8+1\) 的素数筛以及到 \(10^8/2\) 的奇数 SPF 表。这两个步骤都属于筛法预处理，通常可概括为时间复杂度 \(O(N \log \log N)\)，空间复杂度 \(O(N)\)，其中 \(N=10^8\)。
预处理之后，算法只需检查 \(\pi(N+1)\) 个候选，因为每个有效 \(n\) 必须写成 \(p-1\)。单个候选的分解只涉及不同素因子，而生成全部约数的代价为 \(O(2^{\omega(n)})\)。由于平方自由条件使 \(\omega(n)\) 在实际中很小，因此完整验证步骤在这个范围内是可行的。
Нужно найти сумму всех чисел \(n \le 10^8\), для которых для каждого делителя \(d \mid n\) выражение
$$d+\frac{n}{d}$$
является простым. Полный перебор всех \(n\) и всех пар делителей слишком дорог. Поэтому локальные решения на C++, Python и Java сначала накладывают сильные необходимые условия, резко сокращая число кандидатов, и только потом выполняют полный тест по делителям.
Если число \(n\) подходит для всех делителей, то оно должно подходить и для \(d=1\). Следовательно, число
$$1+\frac{n}{1}=n+1$$
обязано быть простым. Значит, любой допустимый кандидат имеет вид
$$n=p-1 \qquad (p \text{ простое}).$$
Именно поэтому код не перебирает все подряд значения \(n\), а идет по простым \(p\) и проверяет только \(n=p-1\).
За исключением случая \(n=1\), простое число \(n+1\) больше \(2\), а значит нечетно. Следовательно, всякое допустимое \(n>1\) должно быть четным. Теперь предположим, что \(4 \mid n\). Тогда при \(d=2\) получаем
$$2+\frac{n}{2}.$$
Так как \(n/2\) в этом случае четно, значение тоже четно и больше \(2\), то есть не может быть простым. Значит, для любого допустимого \(n>1\) верно
$$n \equiv 2 \pmod 4.$$
Этому соответствует быстрый программный фильтр, отбрасывающий числа, кратные \(4\).
Пусть для некоторого нечетного простого \(q\) выполнено \(q^2 \mid n\). Возьмем делитель \(d=q\). Тогда
$$q+\frac{n}{q}=q\left(1+\frac{n}{q^2}\right).$$
Второй множитель является целым числом не меньше \(2\), поэтому все выражение делится на \(q\) и больше самого \(q\), то есть обязательно составно. Значит, в допустимом \(n\) не может быть квадратов нечетных простых.
Совместив это с запретом \(4 \mid n\), получаем: каждое допустимое \(n>1\) четно и квадратно-свободно, причем множитель \(2\) встречается ровно один раз. Код использует именно этот факт: при факторизации \(n/2\) повторное появление одного и того же нечетного простого сразу приводит к отказу.
После быстрых проверок остается подтвердить исходное условие
$$d+\frac{n}{d}\text{ должно быть простым для всех }d \mid n.$$
Делители появляются попарно как \((d,n/d)\), и оба элемента пары дают одну и ту же сумму. Поэтому достаточно проверять только половину делителей:
$$d \le \frac{n}{d} \qquad \Longleftrightarrow \qquad d \le \sqrt{n}.$$
Например, для \(n=30\) нужно рассмотреть пары \((1,30)\), \((2,15)\), \((3,10)\) и \((5,6)\). Получаем \(31,17,13,11\), то есть только простые числа, поэтому \(30\) входит в итоговую сумму.
Для фиксированного \(n\) обозначим \(f(d)=d+n/d\). На отрезке \(1 \le d \le \sqrt{n}\) эта функция убывает, поэтому максимальное релевантное значение достигается при \(d=1\):
$$d+\frac{n}{d} \le n+1.$$
Так как по условию \(n \le 10^8\), все проверки простоты лежат в диапазоне до \(10^8+1\). Поэтому все три реализации один раз строят решето до LIMIT + 1, а затем отвечают на все запросы проверки простоты за \(O(1)\) по таблице.
Все три локальные программы реализуют одну и ту же схему.
Сначала строится решето простых чисел до LIMIT + 1.
Затем рассматриваются только кандидаты вида n = p - 1.
После этого функция check_n или checkN выполняет ровно такие проверки:
$$n=1 \Rightarrow \text{принять}, \qquad n \text{ нечетно } \Rightarrow \text{отклонить}, \qquad 4 \mid n \Rightarrow \text{отклонить}.$$
Далее число записывается как \(n=2m\), и нечетное \(m\) раскладывается с помощью таблицы SPF, хранящейся только для нечетных индексов. Если какой-то нечетный простой множитель повторяется, кандидат сразу отбрасывается как не свободный от квадратов. Иначе код строит все делители из различных простых множителей и проверяет простоту каждого значения \(d+n/d\).
Версии на C++ и Java сначала формируют явный список простых чисел и делят его на блоки для параллельной обработки. Каждый поток или задача считает локальную сумму, после чего все частичные результаты складываются. Версия на Python использует ту же математику, но проходит по решету последовательно.
Таблица SPF тоже устроена экономно. После выделения множителя \(2\) остаток \(m\) всегда нечетен, поэтому минимальный простой делитель нечетного числа \(x\) хранится в позиции \(x/2\). Если там стоит \(0\), текущий остаток уже прост. Это позволяет быстро факторизовать кандидаты без медленного пробного деления.
Основная стоимость приходится на предварительную обработку: построение решета простых до \(10^8+1\) и таблицы SPF для нечетных чисел до \(10^8/2\). Оба этапа имеют характер классических решет, поэтому обычно оцениваются как \(O(N \log \log N)\) по времени и \(O(N)\) по памяти для глобальной границы \(N=10^8\).
После этого алгоритм проверяет только \(\pi(N+1)\) кандидатов, потому что всякое допустимое \(n\) обязано иметь вид \(p-1\). Факторизация одного кандидата требует работы лишь с его различными простыми делителями, а построение всех делителей стоит \(O(2^{\omega(n)})\). Условие квадратно-свободности держит \(\omega(n)\) небольшим на практике, поэтому полный тест оказывается выполнимым.
المطلوب هو حساب مجموع جميع الأعداد \(n \le 10^8\) التي تحقق الشرط التالي: لكل قاسم \(d \mid n\) يكون المقدار
$$d+\frac{n}{d}$$
عددًا أوليًا. الفحص المباشر لكل \(n\) ولكل أزواج القواسم الخاصة به سيكون بطيئًا جدًا عند هذا الحد. لذلك تعتمد الحلول المحلية في C++ وPython وJava على عدة شروط عددية ضرورية لتقليص عدد المرشحين أولًا، ثم تطبق الفحص الكامل فقط على ما يبقى.
إذا كان عدد ما \(n\) صالحًا لكل قواسمه، فلا بد أن يكون صالحًا عندما نأخذ \(d=1\). عندئذ يجب أن يكون
$$1+\frac{n}{1}=n+1$$
عددًا أوليًا. إذن كل قيمة صالحة لا بد أن تكون من الشكل
$$n=p-1.$$
هنا \(p\) عدد أولي. لهذا السبب لا تمر الشيفرة على جميع الأعداد الصحيحة، بل تمر على الأعداد الأولية \(p\) وتختبر فقط القيم \(n=p-1\).
باستثناء الحالة الخاصة \(n=1\)، يكون العدد الأولي \(n+1\) أكبر من \(2\)، وبالتالي يكون فرديًا. إذن كل \(n>1\) صالح يجب أن يكون زوجيًا. لنفترض الآن أن \(4 \mid n\). إذا أخذنا \(d=2\) نحصل على
$$2+\frac{n}{2}.$$
وبما أن \(n/2\) يكون زوجيًا في هذه الحالة، فإن الناتج يكون عددًا زوجيًا أكبر من \(2\)، ومن ثم لا يمكن أن يكون أوليًا. لذلك يجب أن يحقق كل \(n>1\) صالح
$$n \equiv 2 \pmod 4.$$
هذا هو بالضبط الاختبار السريع الموجود في الشيفرة لاستبعاد مضاعفات \(4\).
افترض أن هناك عددًا أوليًا فرديًا \(q\) بحيث \(q^2 \mid n\). عند اختيار \(d=q\) نحصل على
$$q+\frac{n}{q}=q\left(1+\frac{n}{q^2}\right).$$
العامل الثاني عدد صحيح لا يقل عن \(2\)، ولذلك يكون التعبير كله مضاعفًا لـ \(q\) وأكبر من \(q\)، أي إنه عدد مركب. إذن لا يجوز أن يحتوي أي \(n\) صالح على مربع أولي فردي.
ومع شرط \(4 \nmid n\)، نستنتج أن كل \(n>1\) صالح هو عدد زوجي وخالٍ من المربعات، ويظهر العامل \(2\) مرة واحدة فقط. تقوم الدالة المساعدة في الحلول البرمجية بتطبيق هذه النتيجة مباشرة: فإذا تكرر عامل أولي فردي أثناء تحليل \(n/2\)، يُرفض المرشح فورًا.
بعد المرور عبر المرشحات السريعة، يبقى التحقق من الشرط الأصلي كاملًا: لكل \(d \mid n\) يجب أن تكون القيمة
$$d+\frac{n}{d}$$
عددًا أوليًا.
القواسم تأتي في أزواج من الشكل \((d,n/d)\)، وكلا عنصري الزوج يعطيان القيمة نفسها. لذلك يكفي فحص نصف القواسم فقط:
$$d \le \frac{n}{d} \qquad \Longleftrightarrow \qquad d \le \sqrt{n}.$$
مثلًا عند \(n=30\) نحتاج إلى الأزواج \((1,30)\)، \((2,15)\)، \((3,10)\)، \((5,6)\). القيم الناتجة هي \(31,17,13,11\)، وكلها أولية، لذلك يساهم \(30\) في المجموع النهائي.
لعدد ثابت \(n\)، عرّف الدالة \(f(d)=d+n/d\). على المجال \(1 \le d \le \sqrt{n}\) تكون هذه الدالة متناقصة، لذلك أكبر قيمة مطلوبة تظهر عند \(d=1\):
$$d+\frac{n}{d} \le n+1.$$
وبما أن حد المسألة هو \(n \le 10^8\)، فإن جميع اختبارات الأولية تقع داخل المجال حتى \(10^8+1\). لهذا تبني الحلول الثلاثة غربال أوليات واحدًا حتى LIMIT + 1 ثم تعتمد على وصول مباشر للجدول في كل اختبار لاحق.
الملفات المحلية الثلاثة تطبق السلسلة الرياضية نفسها.
أولًا يُبنى غربال للأعداد الأولية حتى LIMIT + 1.
ثم تُفحص فقط القيم من الشكل n = p - 1.
بعد ذلك تنفذ الدالة check_n أو checkN المرشحات التالية بالترتيب: إذا كان \(n=1\) فيُقبل، وإذا كان \(n\) فرديًا فيُرفض، وإذا تحقق \(4 \mid n\) فيُرفض كذلك.
ثم يُكتب العدد على صورة \(n=2m\)، ويُحلل العدد الفردي \(m\) باستخدام جدول SPF مخزن فقط للفهرسة الفردية. إذا ظهر عامل أولي فردي مرتين، يُرفض المرشح لأنه ليس خاليًا من المربعات. وإلا تُولَّد جميع القواسم من العوامل الأولية المختلفة، ثم تُفحص أولية كل قيمة من الشكل \(d+n/d\).
نسختا C++ وJava تنشئان قائمة صريحة بالأعداد الأولية ثم تقسّمانها إلى مقاطع من أجل التنفيذ المتوازي. كل خيط أو مهمة يحسب مجموعًا جزئيًا مستقلًا، ثم تُجمع النتائج في النهاية. أما نسخة Python فتحتفظ بالمنهج الرياضي نفسه، لكنها تنفذ المرور على الغربال بصورة تسلسلية.
أما بنية SPF فهي مضغوطة عمدًا. بعد فصل العامل \(2\)، يبقى لدينا عدد فردي \(m\)، ولذلك تُخزَّن أصغر قسمة أولية للعدد الفردي \(x\) في الموضع \(x/2\). وإذا كانت القيمة المخزنة \(0\)، فهذا يعني أن الباقي الحالي أولي أصلًا. بهذه الطريقة يمكن تحليل كل مرشح بسرعة ومن دون استخدام قسمة تجريبية بطيئة.
الكلفة الأساسية تأتي من مرحلة التهيئة: بناء غربال الأوليات حتى \(10^8+1\) وبناء جدول SPF للأعداد الفردية حتى \(10^8/2\). كلاهما من نوع الخوارزميات الغربالية، ولذلك يُلخَّص زمنهما عادة بالصيغة \(O(N \log \log N)\) مع ذاكرة \(O(N)\) عندما يكون \(N=10^8\).
بعد هذه التهيئة لا تفحص الخوارزمية إلا \(\pi(N+1)\) مرشحًا، لأن كل \(n\) صالح يجب أن يكون من الشكل \(p-1\). تحليل المرشح الواحد يحتاج فقط إلى عدد عوامله الأولية المختلفة، وتوليد جميع قواسمه يكلف \(O(2^{\omega(n)})\). وبسبب شرط الخلو من المربعات تبقى \(\omega(n)\) صغيرة عمليًا، ولذلك يكون الفحص الكامل ممكنًا عند هذا الحد.