For a given upper bound \(L\), compute
$$S(L)=\sum_{\substack{p\lt L\\ p\text{ prime}}} p.$$
The inequality is strict: if \(L\) itself is prime, it is still excluded. When \(L\le 2\), the sum is \(0\) because there are no primes below \(2\).
The task is not to test one number for primality, but to add all primes below a large bound without repeating the same divisibility work for each candidate. The implementation therefore classifies every integer from \(0\) to \(L-1\) in one coordinated pass and then sums the entries that survive.
The solution uses the Sieve of Eratosthenes. Instead of treating each integer independently, it keeps a table of numbers that are still possible primes and progressively deletes the composite ones.
A convenient way to write the target is
$$S(L)=\sum_{n=2}^{L-1} n\,\mathbf{1}_{n\text{ is prime}}.$$
So the real objective is to build the indicator \(\mathbf{1}_{n\text{ is prime}}\) for every \(n\lt L\). Once that information is known, the sum itself is just a linear scan through the surviving indices.
Begin with a Boolean table indexed by \(0,1,\dots,L-1\). Mark \(0\) and \(1\) as non-prime, and treat every integer from \(2\) onward as provisionally prime. Then inspect candidate bases in increasing order.
The key invariant is this: after all prime bases smaller than \(p\) have been processed, every number below \(L\) that has a prime factor smaller than \(p\) has already been marked composite. Therefore, if the entry for \(p\) is still unmarked when the scan reaches it, then \(p\) must itself be prime. If it were composite, it would have a least prime factor \(r\lt p\), and the pass for \(r\) would already have crossed out \(p\).
Once a prime \(p\) is confirmed, the sieve marks
$$p^2,\ p^2+p,\ p^2+2p,\ \dots$$
as composite. The first term is \(p^2\), not \(2p\), for a precise reason. Any smaller multiple \(kp\) with \(2\le k\lt p\) already has a factor smaller than \(p\), so it was removed earlier while processing that smaller factor or one of its prime divisors.
This is where the sieve gains most of its efficiency: the inner pass never restarts from the full list of multiples.
Let \(n\lt L\) be composite. Write \(n=ab\) with \(2\le a\le b\). Then \(a^2\le n\lt L\), so \(a\lt \sqrt{L}\). In particular, \(n\) has a prime factor \(r\le a\lt \sqrt{L}\). That prime factor will appear as a sieve base before the outer loop finishes, and its marking pass will cross out \(n\).
So once the scan reaches a value with \(p^2\ge L\), no composite below \(L\) can still be waiting for its first prime factor to be processed. Every remaining unmarked entry is prime, and the algorithm can move directly to summation.
Initially, the candidates are \(2,3,4,\dots,29\).
Processing \(p=2\) removes
$$4,6,8,10,12,14,16,18,20,22,24,26,28.$$
Processing \(p=3\) removes
$$9,12,15,18,21,24,27,$$
though some of those were already removed by \(2\).
The candidate \(4\) is skipped because it is already known to be composite. Next, \(p=5\) removes only \(25\), since the marking starts at \(5^2\). After that, \(6^2>30\), so the marking phase is over.
The numbers still marked prime are
$$2,3,5,7,11,13,17,19,23,29,$$
and therefore
$$S(30)=129.$$
The same mechanism explains the standard checkpoint \(S(10)=2+3+5+7=17\).
The C++, Python, and Java implementations all use the same three-phase structure.
If the bound is at most \(2\), the answer is returned immediately as \(0\). Otherwise, the implementation allocates a Boolean table of length \(L\), sets the entries for \(0\) and \(1\) to false, and leaves the rest provisionally true.
The outer scan starts at \(2\) and continues while \(p^2\lt L\). Whenever the current entry is still marked prime, the implementation crosses out the arithmetic progression
$$p^2,\ p^2+p,\ p^2+2p,\ \dots \lt L.$$
Candidates already known to be composite are skipped automatically, so only genuine prime bases launch a marking pass.
After the sieve phase, a second linear pass adds every index that remains marked prime. The typed implementations use a 64-bit accumulator because the total for the problem input is far beyond 32-bit range; the Python implementation relies on arbitrary-precision integers.
Initializing the Boolean table costs \(O(L)\) time. The marking work is bounded by
$$\sum_{\substack{p\le \sqrt{L}\\ p\text{ prime}}}\left(\left\lfloor\frac{L-1-p^2}{p}\right\rfloor+1\right)=O\!\left(L\sum_{p\le\sqrt{L}}\frac{1}{p}\right)=O(L\log\log L).$$
The final accumulation pass adds another \(O(L)\), so the total running time is \(O(L\log\log L)\). The Boolean table uses \(O(L)\) memory.
Für eine gegebene obere Schranke \(L\) soll
$$S(L)=\sum_{\substack{p\lt L\\ p\text{ prim}}} p$$
berechnet werden. Die Ungleichung ist strikt: Selbst wenn \(L\) prim ist, gehört \(L\) nicht mehr zur Summe. Für \(L\le 2\) ist das Ergebnis \(0\), weil es unterhalb von \(2\) keine Primzahlen gibt.
Die Schwierigkeit liegt also nicht im Primzahltest für eine einzelne Zahl, sondern darin, alle Primzahlen unter einer großen Grenze zu addieren, ohne dieselbe Teilbarkeitsarbeit für jeden Kandidaten neu zu wiederholen. Deshalb klassifiziert die Implementierung alle Zahlen von \(0\) bis \(L-1\) in einem gemeinsamen Durchlauf und summiert anschließend die übrig gebliebenen Einträge.
Die Lösung verwendet das Sieb des Eratosthenes. Anstatt jede Zahl getrennt zu behandeln, führt man eine Tabelle von Werten, die noch als mögliche Primzahlen gelten, und streicht schrittweise alle zusammengesetzten Zahlen heraus.
Bequem schreibt man
$$S(L)=\sum_{n=2}^{L-1} n\,\mathbf{1}_{n\text{ ist prim}}.$$
Damit reduziert sich die Aufgabe darauf, für jedes \(n\lt L\) den Primindikator \(\mathbf{1}_{n\text{ ist prim}}\) zu bestimmen. Ist diese Information bekannt, dann ist die Summe nur noch ein linearer Durchlauf über die verbleibenden Indizes.
Man beginnt mit einer Booleschen Tabelle für \(0,1,\dots,L-1\). Die Werte \(0\) und \(1\) werden sofort als nicht prim markiert; jede Zahl ab \(2\) gilt zunächst als vorläufig prim. Danach werden mögliche Siebbasen in aufsteigender Reihenfolge betrachtet.
Die zentrale Invariante lautet: Nachdem alle Primzahlen kleiner als \(p\) verarbeitet worden sind, ist jede Zahl unterhalb von \(L\), die einen Primfaktor kleiner als \(p\) besitzt, bereits als zusammengesetzt markiert. Wenn also der Eintrag zu \(p\) beim Erreichen von \(p\) noch unmarkiert ist, dann muss \(p\) selbst prim sein. Wäre \(p\) zusammengesetzt, dann hätte \(p\) einen kleinsten Primfaktor \(r\lt p\), und der Schritt für \(r\) hätte \(p\) schon gestrichen.
Sobald eine Primzahl \(p\) bestätigt ist, markiert das Sieb
$$p^2,\ p^2+p,\ p^2+2p,\ \dots$$
als zusammengesetzt. Der erste Term ist bewusst \(p^2\) und nicht \(2p\). Denn jedes kleinere Vielfache \(kp\) mit \(2\le k\lt p\) besitzt bereits einen Faktor kleiner als \(p\) und wurde daher früher beim Verarbeiten dieses kleineren Faktors oder eines seiner Primteiler entfernt.
Genau hier entsteht der Effizienzgewinn des Siebs: Die innere Schleife muss nicht immer wieder bei allen Vielfachen von vorne beginnen.
Sei \(n\lt L\) zusammengesetzt. Schreibe \(n=ab\) mit \(2\le a\le b\). Dann gilt \(a^2\le n\lt L\), also \(a\lt \sqrt{L}\). Insbesondere besitzt \(n\) einen Primfaktor \(r\le a\lt \sqrt{L}\). Dieser Primfaktor erscheint noch vor Ende der äußeren Schleife als Siebbasis und streicht \(n\) sicher heraus.
Sobald also ein Kandidat \(p\) mit \(p^2\ge L\) erreicht ist, kann es unterhalb von \(L\) keine zusammengesetzte Zahl mehr geben, die noch auf ihre erste unverarbeitete Primzahl wartet. Alle unmarkierten Einträge sind dann prim, und man kann direkt zur Summation übergehen.
Anfangs sind die Kandidaten \(2,3,4,\dots,29\).
Für \(p=2\) werden
$$4,6,8,10,12,14,16,18,20,22,24,26,28$$
gestrichen.
Für \(p=3\) werden
$$9,12,15,18,21,24,27$$
gestrichen, wobei einige davon bereits durch \(2\) entfernt waren.
Der Kandidat \(4\) wird übersprungen, weil er schon als zusammengesetzt bekannt ist. Danach streicht \(p=5\) wegen des Starts bei \(5^2\) nur noch die \(25\). Anschließend gilt \(6^2>30\), also ist die Markierungsphase beendet.
Übrig bleiben die Primzahlen
$$2,3,5,7,11,13,17,19,23,29,$$
und damit
$$S(30)=129.$$
Dasselbe Prinzip liefert auch den bekannten Prüfwert \(S(10)=2+3+5+7=17\).
Die Implementierungen in C++, Python und Java verwenden alle dieselbe dreistufige Struktur.
Ist die Schranke höchstens \(2\), wird sofort \(0\) zurückgegeben. Andernfalls erzeugt die Implementierung eine Boolesche Tabelle der Länge \(L\), setzt die Einträge für \(0\) und \(1\) auf falsch und lässt alle anderen zunächst auf wahr stehen.
Die äußere Schleife beginnt bei \(2\) und läuft, solange \(p^2\lt L\) gilt. Immer wenn der aktuelle Eintrag noch als prim markiert ist, streicht die Implementierung die arithmetische Folge
$$p^2,\ p^2+p,\ p^2+2p,\ \dots \lt L.$$
Kandidaten, die bereits als zusammengesetzt bekannt sind, werden automatisch übersprungen. Deshalb startet nur eine echte Primzahl einen Markierungsdurchlauf.
Nach dem Sieb folgt ein zweiter linearer Durchlauf, der alle noch als prim markierten Indizes addiert. In den typisierten Implementierungen wird dafür ein 64-Bit-Akkumulator verwendet, weil die Summe für die eigentliche Aufgabengrenze deutlich außerhalb des 32-Bit-Bereichs liegt; Python benutzt Ganzzahlen beliebiger Größe.
Die Initialisierung der Booleschen Tabelle kostet \(O(L)\) Zeit. Der Markierungsaufwand wird abgeschätzt durch
$$\sum_{\substack{p\le \sqrt{L}\\ p\text{ prim}}}\left(\left\lfloor\frac{L-1-p^2}{p}\right\rfloor+1\right)=O\!\left(L\sum_{p\le\sqrt{L}}\frac{1}{p}\right)=O(L\log\log L).$$
Der abschließende Summationsdurchlauf kostet noch einmal \(O(L)\). Insgesamt ergibt sich also \(O(L\log\log L)\) Laufzeit und \(O(L)\) Speicher für die Boolesche Tabelle.
Verilen bir üst sınır \(L\) için
$$S(L)=\sum_{\substack{p\lt L\\ p\text{ asal}}} p$$
hesaplanır. Eşitsizlik sıkıdır; \(L\) asal olsa bile toplama dahil edilmez. \(L\le 2\) olduğunda cevap \(0\)'dır, çünkü \(2\)'nin altında asal sayı yoktur.
Dolayısıyla mesele tek bir sayının asal olup olmadığını sınamak değildir. Asıl amaç, büyük bir sınırın altındaki bütün asalları aynı bölünebilirlik testlerini tekrar tekrar yapmadan toplamaktır. Bu yüzden uygulama, \(0\) ile \(L-1\) arasındaki tüm sayıları ortak bir eleme süreciyle sınıflandırır ve sonra hayatta kalanları toplar.
Çözüm Eratosthenes Eleği'ni kullanır. Her sayıyı bağımsız incelemek yerine, hâlâ asal olma ihtimali bulunan sayıları tutan bir tablo kurulup bileşik olanlar aşamalı biçimde elenir.
Hedef toplamı
$$S(L)=\sum_{n=2}^{L-1} n\,\mathbf{1}_{n\text{ asaldır}}$$
şeklinde yazmak kullanışlıdır. Böylece problem, her \(n\lt L\) için \(\mathbf{1}_{n\text{ asaldır}}\) göstergesini üretme problemine dönüşür. Bu gösterge tablosu kurulduktan sonra toplam, kalan indeksler üzerinde yapılan doğrusal bir taramadır.
\(0,1,\dots,L-1\) indeksli bir Boole tablosuyla başlanır. \(0\) ve \(1\) baştan asal olmayan olarak işaretlenir; \(2\)'den başlayan her sayı ise önce geçici olarak asal kabul edilir. Sonra aday tabanlar artan sırayla incelenir.
Temel invariant şudur: \(p\)'den küçük bütün asal tabanlar işlendiğinde, \(L\)'nin altındaki ve \(p\)'den küçük bir asal çarpanı olan her sayı zaten bileşik diye işaretlenmiştir. Bu nedenle tarama \(p\)'ye geldiğinde \(p\) hâlâ işaretlenmemişse, \(p\) mutlaka asaldır. Çünkü \(p\) bileşik olsaydı, \(p\)'nin \(r\lt p\) olacak en küçük asal böleni bulunurdu ve \(r\) için yapılan adım \(p\)'yi daha önce elemiş olurdu.
Bir asal \(p\) doğrulandıktan sonra elekte
$$p^2,\ p^2+p,\ p^2+2p,\ \dots$$
terimleri bileşik olarak işaretlenir. İlk terimin \(2p\) değil de \(p^2\) olmasının açık bir nedeni vardır. \(2\le k\lt p\) için her \(kp\) katı, \(p\)'den küçük bir çarpana zaten sahiptir; dolayısıyla o daha küçük çarpan ya da onun asal bölenlerinden biri işlenirken önceden elenmiştir.
Eleğin asıl verimi burada ortaya çıkar: iç döngü her defasında bütün katları baştan dolaşmaz.
\(n\lt L\) bileşik olsun ve \(n=ab\) biçiminde yazılsın; burada \(2\le a\le b\). O zaman \(a^2\le n\lt L\), yani \(a\lt \sqrt{L}\). Demek ki \(n\), \(r\le a\lt \sqrt{L}\) olacak bir asal çarpana sahiptir. Bu asal çarpan dış döngü bitmeden önce mutlaka taban olarak işlenecek ve \(n\)'yi eleyecektir.
Böylece \(p^2\ge L\) olduğunda, \(L\)'nin altında kalıp da ilk işlenmemiş asal çarpanını bekleyen hiçbir bileşik sayı kalmaz. İşaretlenmemiş her giriş asaldır ve algoritma doğrudan toplama aşamasına geçebilir.
Başlangıçta adaylar \(2,3,4,\dots,29\) sayılarıdır.
\(p=2\) işlendiğinde
$$4,6,8,10,12,14,16,18,20,22,24,26,28$$
elenir.
\(p=3\) işlendiğinde
$$9,12,15,18,21,24,27$$
elenir; bunların bir kısmı zaten \(2\) tarafından kaldırılmıştır.
\(4\) adayı bileşik olduğu önceden bilindiği için atlanır. Sonra \(p=5\), başlangıç noktası \(5^2\) olduğu için yalnızca \(25\)'i eler. Bundan sonra \(6^2>30\) olduğundan işaretleme biter.
Asal olarak kalan sayılar
$$2,3,5,7,11,13,17,19,23,29$$
olur ve dolayısıyla
$$S(30)=129.$$
Aynı mantık, standart doğrulama değeri olan \(S(10)=2+3+5+7=17\) sonucunu da açıklar.
C++, Python ve Java uygulamalarının tümü aynı üç aşamalı yapıyı izler.
Sınır \(2\) ya da daha küçükse sonuç hemen \(0\) olarak döndürülür. Aksi halde uzunluğu \(L\) olan bir Boole tablosu ayrılır, \(0\) ve \(1\) girişleri yanlış yapılır, diğer bütün girişler ise önce doğru bırakılır.
Dış tarama \(2\)'den başlar ve \(p^2\lt L\) koşulu sürdüğü sürece devam eder. Güncel giriş hâlâ asal olarak işaretliyse uygulama şu aritmetik diziyi siler:
$$p^2,\ p^2+p,\ p^2+2p,\ \dots \lt L.$$
Zaten bileşik olduğu bilinen adaylar otomatik olarak atlandığı için, iç işaretleme yalnızca gerçek asal tabanlarla başlatılır.
Elek tamamlandıktan sonra ikinci bir doğrusal tarama, asal olarak kalmış bütün indeksleri toplar. Tür güvenliği olan dillerde 64 bitlik bir biriktirici kullanılır; çünkü problem girdisindeki toplam 32 bit aralığını açık biçimde aşar. Python sürümü ise doğal olarak keyfi büyüklükte tamsayılar kullanır.
Boole tablosunun kurulması \(O(L)\) zaman alır. İşaretleme maliyeti şu toplamla sınırlandırılır:
$$\sum_{\substack{p\le \sqrt{L}\\ p\text{ asal}}}\left(\left\lfloor\frac{L-1-p^2}{p}\right\rfloor+1\right)=O\!\left(L\sum_{p\le\sqrt{L}}\frac{1}{p}\right)=O(L\log\log L).$$
Son toplama taraması da \(O(L)\) sürer. Böylece toplam çalışma süresi \(O(L\log\log L)\), bellek kullanımı ise Boole tablosu nedeniyle \(O(L)\) olur.
Dado un límite superior \(L\), hay que calcular
$$S(L)=\sum_{\substack{p\lt L\\ p\text{ primo}}} p.$$
La desigualdad es estricta: aunque \(L\) sea primo, no se incluye. Si \(L\le 2\), el resultado es \(0\), porque por debajo de \(2\) no hay números primos.
La dificultad no es comprobar si un solo número es primo, sino sumar todos los primos por debajo de un límite grande sin repetir una y otra vez el mismo trabajo de divisibilidad. Por eso la implementación clasifica de una sola vez todos los enteros entre \(0\) y \(L-1\) y luego suma los que sobreviven.
La solución utiliza la criba de Eratóstenes. En lugar de estudiar cada entero por separado, mantiene una tabla de valores que todavía podrían ser primos y va eliminando progresivamente los compuestos.
Es útil escribir el objetivo como
$$S(L)=\sum_{n=2}^{L-1} n\,\mathbf{1}_{n\text{ es primo}}.$$
Así, el problema real consiste en construir el indicador \(\mathbf{1}_{n\text{ es primo}}\) para cada \(n\lt L\). Una vez conocida esa tabla, la suma final no es más que un recorrido lineal por los índices que permanecen marcados.
Se empieza con una tabla booleana indexada por \(0,1,\dots,L-1\). Los valores \(0\) y \(1\) se marcan de inmediato como no primos, y cada entero a partir de \(2\) se considera provisionalmente primo. Después se recorren las posibles bases en orden creciente.
La invariante clave es la siguiente: después de procesar todas las bases primas menores que \(p\), ya ha quedado marcado como compuesto todo número menor que \(L\) que tenga un factor primo menor que \(p\). Por tanto, si al llegar a \(p\) su entrada sigue sin tacharse, \(p\) tiene que ser primo. Si fuera compuesto, tendría un factor primo mínimo \(r\lt p\), y el paso correspondiente a \(r\) ya habría tachado a \(p\).
Una vez confirmada una base prima \(p\), la criba marca
$$p^2,\ p^2+p,\ p^2+2p,\ \dots$$
como compuestos. El primer término es \(p^2\), no \(2p\), por una razón precisa. Cualquier múltiplo menor \(kp\) con \(2\le k\lt p\) ya posee un factor menor que \(p\), así que fue eliminado antes al procesar ese factor más pequeño o alguno de sus divisores primos.
Aquí aparece la verdadera ganancia de eficiencia del método: el bucle interno no vuelve a empezar desde todos los múltiplos posibles.
Sea \(n\lt L\) compuesto y escríbase \(n=ab\) con \(2\le a\le b\). Entonces \(a^2\le n\lt L\), luego \(a\lt \sqrt{L}\). En particular, \(n\) tiene un factor primo \(r\le a\lt \sqrt{L}\). Ese factor aparecerá como base de la criba antes de que termine el recorrido exterior, y su pasada de marcado eliminará a \(n\).
Así, cuando se alcanza un candidato con \(p^2\ge L\), ya no queda ningún compuesto menor que \(L\) esperando a que se procese su primer factor primo. Todo lo que sigue sin marcar es primo, y el algoritmo puede pasar directamente a la suma.
Al principio los candidatos son \(2,3,4,\dots,29\).
Al procesar \(p=2\) se eliminan
$$4,6,8,10,12,14,16,18,20,22,24,26,28.$$
Al procesar \(p=3\) se eliminan
$$9,12,15,18,21,24,27,$$
aunque algunos ya habían desaparecido en el paso de \(2\).
El candidato \(4\) se salta porque ya se sabe que es compuesto. Después, \(p=5\) solo elimina \(25\), porque el marcado empieza en \(5^2\). A continuación se cumple \(6^2>30\), así que la fase de cribado termina.
Los números que quedan como primos son
$$2,3,5,7,11,13,17,19,23,29,$$
y por tanto
$$S(30)=129.$$
La misma lógica explica el punto de control habitual \(S(10)=2+3+5+7=17\).
Las implementaciones en C++, Python y Java siguen la misma estructura de tres fases.
Si el límite es \(2\) o menor, la respuesta se devuelve inmediatamente como \(0\). En caso contrario, la implementación reserva una tabla booleana de longitud \(L\), fija a falso las posiciones \(0\) y \(1\), y deja el resto provisionalmente en verdadero.
El recorrido exterior empieza en \(2\) y continúa mientras \(p^2\lt L\). Siempre que la entrada actual siga marcada como prima, la implementación tacha la progresión aritmética
$$p^2,\ p^2+p,\ p^2+2p,\ \dots \lt L.$$
Los candidatos ya conocidos como compuestos se saltan automáticamente, así que solo las bases realmente primas activan un paso de marcado.
Tras completar la criba, un segundo recorrido lineal suma todos los índices que permanecen marcados como primos. Las implementaciones tipadas usan un acumulador de 64 bits, porque la suma para la entrada del problema supera con claridad el rango de 32 bits; Python se apoya en enteros de precisión arbitraria.
Inicializar la tabla booleana cuesta \(O(L)\) tiempo. El trabajo de marcado queda acotado por
$$\sum_{\substack{p\le \sqrt{L}\\ p\text{ primo}}}\left(\left\lfloor\frac{L-1-p^2}{p}\right\rfloor+1\right)=O\!\left(L\sum_{p\le\sqrt{L}}\frac{1}{p}\right)=O(L\log\log L).$$
El barrido final para sumar añade otro \(O(L)\), así que el tiempo total es \(O(L\log\log L)\). El espacio usado por la tabla booleana es \(O(L)\).
给定一个上界 \(L\)，要求计算
$$S(L)=\sum_{\substack{p\lt L\\ p\text{ 为素数}}} p.$$
这里是不等号严格小于：即使 \(L\) 本身是素数，也不能算进去。当 \(L\le 2\) 时，答案是 \(0\)，因为 \(2\) 以下没有素数。
这道题的难点并不是判断某一个数是否为素数，而是在一个很大的范围内把 所有 素数加起来，同时避免对每个候选数都重复做一遍除法检验。实现采用的思路，是把 \(0\) 到 \(L-1\) 的所有整数一次性放进同一个筛选过程，最后再把留下来的项求和。
解法建立在埃拉托斯特尼筛法之上。它不把每个整数当作彼此独立的问题来处理，而是维护一张“仍然可能是素数”的布尔表，并随着筛选推进逐步删掉所有合数。
目标和可以写成
$$S(L)=\sum_{n=2}^{L-1} n\,\mathbf{1}_{n\text{ 是素数}}.$$
这样一写，问题的本质就非常清楚了：我们真正需要的是对每个 \(n\lt L\) 构造出指标 \(\mathbf{1}_{n\text{ 是素数}}\)。一旦这张指标表已经正确建立，最后的求和不过是在所有仍被标为素数的下标上做一次线性扫描。
先建立一张以下标 \(0,1,\dots,L-1\) 表示整数的布尔表。把 \(0\) 和 \(1\) 立即标成非素数，而从 \(2\) 开始的所有整数先暂时视为“可能是素数”。然后按从小到大的顺序扫描候选底数。
筛法成立的关键不变量是：当所有小于 \(p\) 的素数底数都已经处理完以后，凡是小于 \(L\) 且拥有某个小于 \(p\) 的素因子的整数，都已经被标成合数。于是当扫描走到 \(p\) 时，如果它还没有被划掉，那么 \(p\) 本身就一定是素数。原因很直接：如果 \(p\) 是合数，那么它一定有一个最小素因子 \(r\lt p\)，而处理 \(r\) 的那一轮早就应该把 \(p\) 划掉了。
一旦确认 \(p\) 是素数，筛法就会把
$$p^2,\ p^2+p,\ p^2+2p,\ \dots$$
标为合数。之所以从 \(p^2\) 开始，而不是从 \(2p\) 开始，是因为所有更小的倍数 \(kp\)（其中 \(2\le k\lt p\)）都已经含有一个比 \(p\) 更小的因子，所以它们一定已经在更早的时候被删掉了，要么是在处理 \(k\) 本身时删掉的，要么是在处理 \(k\) 的某个素因子时删掉的。
这一步正是筛法效率高的根源之一：内层循环不必每次都从最前面的倍数重新开始，而只需要处理那些还没有被更小因子覆盖到的部分。
设 \(n\lt L\) 是一个合数，写成 \(n=ab\)，其中 \(2\le a\le b\)。那么有 \(a^2\le n\lt L\)，所以 \(a\lt \sqrt{L}\)。这说明 \(n\) 一定拥有一个满足 \(r\le a\lt \sqrt{L}\) 的素因子 \(r\)。只要筛法已经处理完所有满足 \(p^2\lt L\) 的素数底数，这个 \(r\) 就一定出现过，并且在它那一轮中把 \(n\) 划掉。
因此，当外层扫描到某个 \(p\) 使得 \(p^2\ge L\) 时，就不可能还存在“小于 \(L\) 且尚未被其最小素因子处理”的合数了。所有还保持未标记状态的整数，都已经是真正的素数，可以直接进入求和阶段。
一开始，候选数是 \(2,3,4,\dots,29\)。
处理 \(p=2\) 时，会划去
$$4,6,8,10,12,14,16,18,20,22,24,26,28.$$
处理 \(p=3\) 时，会划去
$$9,12,15,18,21,24,27,$$
其中有一些数其实已经在处理 \(2\) 时被划掉了。
扫描到 \(4\) 时，由于它已经被认定为合数，所以直接跳过。接着处理 \(p=5\) 时，因为起点是 \(5^2\)，所以只需要划去 \(25\)。再往后有 \(6^2>30\)，说明筛的主阶段已经结束。
最终仍然保留下来的素数是
$$2,3,5,7,11,13,17,19,23,29,$$
于是
$$S(30)=129.$$
同样的机制也解释了常见校验值 \(S(10)=2+3+5+7=17\)。
C++、Python 和 Java 三个实现都遵循同一套三阶段结构。
如果上界不超过 \(2\)，答案立即返回 \(0\)。否则，程序分配一个长度为 \(L\) 的布尔表，把 \(0\) 和 \(1\) 位置设为假，其余位置暂时设为真，表示“目前还可能是素数”。
外层扫描从 \(2\) 开始，并在 \(p^2\lt L\) 的条件下继续。只要当前条目仍然标记为素数，程序就会划去下面这个等差序列：
$$p^2,\ p^2+p,\ p^2+2p,\ \dots \lt L.$$
那些已经被判定为合数的候选底数会自动跳过，所以真正触发内层划除的只有素数底数。
筛法完成后，再做一次线性扫描，把所有仍标为素数的下标加起来。C++ 和 Java 版本使用 64 位累加器，因为题目输入对应的总和明显超出 32 位整数范围；Python 版本则直接依赖其任意精度整数。
初始化布尔表需要 \(O(L)\) 时间。划除合数的总工作量可以用下式估计：
$$\sum_{\substack{p\le \sqrt{L}\\ p\text{ 为素数}}}\left(\left\lfloor\frac{L-1-p^2}{p}\right\rfloor+1\right)=O\!\left(L\sum_{p\le\sqrt{L}}\frac{1}{p}\right)=O(L\log\log L).$$
最后的求和扫描再花 \(O(L)\) 时间，因此总时间复杂度是 \(O(L\log\log L)\)，空间复杂度则是布尔表带来的 \(O(L)\)。
Для заданной верхней границы \(L\) требуется вычислить
$$S(L)=\sum_{\substack{p\lt L\\ p\text{ простое}}} p.$$
Неравенство строгое: даже если \(L\) само простое, в сумму оно не входит. При \(L\le 2\) ответ равен \(0\), потому что ниже \(2\) простых чисел нет.
Сложность задачи состоит не в проверке одной отдельной величины на простоту, а в том, чтобы сложить все простые числа ниже большого предела, не повторяя одну и ту же работу по делимости для каждого кандидата. Поэтому реализация классифицирует сразу все числа от \(0\) до \(L-1\), а затем суммирует те значения, которые пережили отсеивание.
Решение основано на решете Эратосфена. Вместо того чтобы рассматривать каждое число отдельно, алгоритм поддерживает таблицу чисел, которые пока еще могут быть простыми, и постепенно удаляет из нее составные.
Удобно записать цель в виде
$$S(L)=\sum_{n=2}^{L-1} n\,\mathbf{1}_{n\text{ простое}}.$$
Тогда реальная задача сводится к построению индикатора \(\mathbf{1}_{n\text{ простое}}\) для каждого \(n\lt L\). Когда эта таблица построена, окончательная сумма получается простым линейным проходом по тем индексам, которые остались отмеченными как простые.
Сначала создается булева таблица для чисел \(0,1,\dots,L-1\). Числа \(0\) и \(1\) сразу помечаются как не простые, а все числа начиная с \(2\) временно считаются возможными простыми. После этого кандидаты на базовые делители просматриваются в порядке возрастания.
Ключевой инвариант таков: после обработки всех простых баз меньше \(p\) уже помечено как составное любое число меньше \(L\), у которого есть простой делитель меньше \(p\). Следовательно, если при достижении \(p\) соответствующая запись все еще не зачеркнута, то \(p\) обязано быть простым. Если бы \(p\) было составным, у него существовал бы наименьший простой делитель \(r\lt p\), и проход для \(r\) уже зачеркнул бы \(p\).
После подтверждения простоты числа \(p\) решето помечает как составные элементы
$$p^2,\ p^2+p,\ p^2+2p,\ \dots$$
Первым идет именно \(p^2\), а не \(2p\), и причина здесь точная. Любое меньшее кратное \(kp\) при \(2\le k\lt p\) уже имеет делитель, меньший \(p\), значит, оно было удалено раньше при обработке этого меньшего делителя или одного из его простых делителей.
Именно в этом месте решето выигрывает в эффективности: внутренний проход не начинает каждый раз с полного набора кратных заново.
Пусть \(n\lt L\) составное и \(n=ab\) при \(2\le a\le b\). Тогда \(a^2\le n\lt L\), следовательно, \(a\lt \sqrt{L}\). Значит, у числа \(n\) существует простой делитель \(r\le a\lt \sqrt{L}\). Этот делитель обязательно появится в роли базы решета до завершения внешнего цикла, и соответствующий шаг пометит \(n\) как составное.
Поэтому, как только достигается кандидат \(p\) с условием \(p^2\ge L\), больше не остается составных чисел ниже \(L\), которые ждали бы обработки своего первого простого делителя. Все невычеркнутые записи уже соответствуют простым числам, и можно переходить к суммированию.
Сначала кандидаты равны \(2,3,4,\dots,29\).
При обработке \(p=2\) вычеркиваются
$$4,6,8,10,12,14,16,18,20,22,24,26,28.$$
При обработке \(p=3\) вычеркиваются
$$9,12,15,18,21,24,27,$$
хотя некоторые из них уже были удалены шагом для \(2\).
Число \(4\) пропускается, потому что оно уже известно как составное. Затем шаг для \(p=5\) удаляет только \(25\), поскольку вычеркивание начинается с \(5^2\). После этого выполняется \(6^2>30\), и фаза маркировки заканчивается.
В итоге простыми остаются числа
$$2,3,5,7,11,13,17,19,23,29,$$
поэтому
$$S(30)=129.$$
Тот же механизм объясняет стандартную проверку \(S(10)=2+3+5+7=17\).
Реализации на C++, Python и Java используют одну и ту же трехшаговую схему.
Если граница не превосходит \(2\), ответ немедленно возвращается как \(0\). Иначе создается булева таблица длины \(L\), записи для \(0\) и \(1\) переводятся в ложь, а все остальные временно оставляются истинными.
Внешний проход начинается с \(2\) и продолжается, пока выполняется \(p^2\lt L\). Если текущая запись все еще помечена как простая, реализация вычеркивает арифметическую прогрессию
$$p^2,\ p^2+p,\ p^2+2p,\ \dots \lt L.$$
Кандидаты, уже известные как составные, пропускаются автоматически, так что запуск внутреннего шага происходит только для настоящих простых баз.
После завершения решета выполняется второй линейный проход, складывающий все индексы, которые остались отмеченными как простые. В типизированных реализациях используется 64-битный аккумулятор, потому что итог для основного входа задачи существенно выходит за пределы 32-битного диапазона; Python опирается на целые произвольной длины.
Инициализация булевой таблицы требует \(O(L)\) времени. Работа по вычеркиванию ограничивается оценкой
$$\sum_{\substack{p\le \sqrt{L}\\ p\text{ простое}}}\left(\left\lfloor\frac{L-1-p^2}{p}\right\rfloor+1\right)=O\!\left(L\sum_{p\le\sqrt{L}}\frac{1}{p}\right)=O(L\log\log L).$$
Последний проход суммирования занимает еще \(O(L)\), поэтому общее время работы равно \(O(L\log\log L)\), а память для булевой таблицы составляет \(O(L)\).
لحد علوي معطى \(L\)، نريد حساب
$$S(L)=\sum_{\substack{p\lt L\\ p\text{ أولي}}} p.$$
عدم المساواة هنا صارم: حتى لو كان \(L\) نفسه عددًا أوليًا فإنه لا يدخل في المجموع. وإذا كان \(L\le 2\) فالقيمة تساوي \(0\)، لأنه لا توجد أعداد أولية أصغر من \(2\).
الصعوبة ليست في اختبار عدد واحد لمعرفة أوليته، بل في جمع جميع الأعداد الأولية الأصغر من حد كبير من غير تكرار العمل نفسه الخاص بالقسمة على كل مرشح على حدة. لذلك تتعامل الشيفرة مع كل الأعداد من \(0\) إلى \(L-1\) دفعة واحدة داخل عملية غربلة موحدة، ثم تجمع القيم التي بقيت بعد الاستبعاد.
الحل يعتمد على غربال إراتوستينس. بدل أن ننظر إلى كل عدد على أنه مسألة مستقلة، نبني جدولًا منطقيًا للأعداد التي ما زالت قد تكون أولية، ثم نحذف الأعداد المركبة تدريجيًا.
يمكن كتابة الهدف على الصورة
$$S(L)=\sum_{n=2}^{L-1} n\,\mathbf{1}_{n\text{ أولي}}.$$
وبذلك تصبح المسألة الحقيقية هي بناء المؤشر \(\mathbf{1}_{n\text{ أولي}}\) لكل \(n\lt L\). متى صارت هذه المعلومات صحيحة، فإن خطوة الجمع النهائية ليست إلا مرورًا خطيًا على الفهارس التي بقيت معلمة على أنها أولية.
نبدأ بجدول منطقي مفهرس بالأعداد \(0,1,\dots,L-1\). يُعلَّم \(0\) و\(1\) فورًا على أنهما غير أوليين، بينما تُترك كل القيم من \(2\) فصاعدًا على أنها مرشحة أولية مؤقتًا. بعد ذلك نفحص قواعد الغربلة بترتيب تصاعدي.
الثابت الحاسم هو الآتي: بعد إنهاء جميع القواعد الأولية الأصغر من \(p\)، يكون كل عدد أصغر من \(L\) وله عامل أولي أصغر من \(p\) قد وُسِم بالفعل على أنه مركب. ومن ثم، إذا وصل المسح إلى \(p\) وكانت خانته ما تزال غير مشطوبة، فلا بد أن \(p\) نفسه أولي. ولو كان مركبًا لكان له أصغر عامل أولي \(r\lt p\)، وكانت خطوة \(r\) قد شطبت \(p\) سابقًا.
عندما نتأكد أن \(p\) أولي، فإن الغربال يعلّم
$$p^2,\ p^2+p,\ p^2+2p,\ \dots$$
على أنها أعداد مركبة. البداية من \(p^2\) وليست من \(2p\) لها سبب دقيق. فكل مضاعف أصغر من الشكل \(kp\) حيث \(2\le k\lt p\) يملك بالفعل عاملًا أصغر من \(p\)، ولذلك يكون قد أُزيل في وقت أبكر عند معالجة ذلك العامل الأصغر أو أحد عوامله الأولية.
وهنا يظهر جانب الكفاءة الرئيسي في الغربال: الحلقة الداخلية لا تعيد المرور على كل المضاعفات من بدايتها في كل مرة.
خذ عددًا مركبًا \(n\lt L\)، واكتبه على صورة \(n=ab\) مع \(2\le a\le b\). عندئذٍ \(a^2\le n\lt L\)، وبالتالي \(a\lt \sqrt{L}\). وهذا يعني أن \(n\) يملك عاملًا أوليًا \(r\le a\lt \sqrt{L}\). هذا العامل سيظهر كقاعدة للغربال قبل انتهاء الحلقة الخارجية، وعندها سيشطب \(n\) لا محالة.
إذن، عندما نصل إلى قيمة تحقق \(p^2\ge L\)، لا يبقى أي عدد مركب أصغر من \(L\) ينتظر أن يُعالج أصغر عوامله الأولية بعد. كل ما بقي غير مشطوب هو عدد أولي حقيقي، ويمكن الانتقال مباشرة إلى مرحلة الجمع.
في البداية تكون الأعداد المرشحة هي \(2,3,4,\dots,29\).
عند معالجة \(p=2\) نشطب
$$4,6,8,10,12,14,16,18,20,22,24,26,28.$$
وعند معالجة \(p=3\) نشطب
$$9,12,15,18,21,24,27,$$
مع أن بعض هذه القيم كان قد شُطب أصلًا في خطوة \(2\).
المرشح \(4\) يُتجاوز لأننا نعرف سلفًا أنه مركب. ثم تأتي خطوة \(p=5\)، وبما أن البداية من \(5^2\) فهي تشطب \(25\) فقط. بعد ذلك يصبح \(6^2>30\)، فتكون مرحلة التعليم قد انتهت.
الأعداد التي تبقى معلمة على أنها أولية هي
$$2,3,5,7,11,13,17,19,23,29,$$
ومن ثم
$$S(30)=129.$$
والآلية نفسها تفسر قيمة التحقق المعروفة \(S(10)=2+3+5+7=17\).
تسير تطبيقات C++ وPython وJava جميعًا وفق بنية واحدة من ثلاث مراحل.
إذا كان الحد لا يتجاوز \(2\)، تُعاد الإجابة فورًا على أنها \(0\). وإلا تُخصَّص مصفوفة منطقية طولها \(L\)، وتُجعل الخانتان الموافقـتان لـ \(0\) و\(1\) بقيمة false، وتُترك بقية الخانات مؤقتًا بقيمة true.
يبدأ المسح الخارجي من \(2\) ويستمر ما دام \(p^2\lt L\). وكلما كانت الخانة الحالية ما تزال معلمة على أنها أولية، تشطب الشيفرة المتتالية الحسابية
$$p^2,\ p^2+p,\ p^2+2p,\ \dots \lt L.$$
أما المرشحـات التي ثبت مسبقًا أنها مركبة فتُتجاوز تلقائيًا، ولهذا لا تبدأ مرحلة الشطب الداخلي إلا من قواعد أولية حقيقية.
بعد انتهاء الغربلة، يُجرى مرور خطي ثانٍ لجمع كل الفهارس التي بقيت معلمة على أنها أولية. في اللغات ذات الأنواع الثابتة يُستخدم مجمّع 64-بت، لأن مجموع المسألة الفعلي يتجاوز بوضوح مجال 32-بت، بينما تعتمد Python على أعداد صحيحة ذات دقة غير محدودة.
تهيئة الجدول المنطقي تكلف \(O(L)\) زمنًا. أما عمل الشطب فيُحدّ بالتقدير
$$\sum_{\substack{p\le \sqrt{L}\\ p\text{ أولي}}}\left(\left\lfloor\frac{L-1-p^2}{p}\right\rfloor+1\right)=O\!\left(L\sum_{p\le\sqrt{L}}\frac{1}{p}\right)=O(L\log\log L).$$
ثم يضيف المرور النهائي للجمع كلفة مقدارها \(O(L)\)، وبذلك يكون زمن التنفيذ الكلي \(O(L\log\log L)\)، أما الذاكرة فهي \(O(L)\) بسبب الجدول المنطقي.