Knowledge (XXG)

Sieve theory

Source đź“ť

25: 116:. The direct attack on prime numbers using these methods soon reaches apparently insuperable obstacles, in the way of the accumulation of error terms. In one of the major strands of number theory in the twentieth century, ways were found of avoiding some of the difficulties of a frontal attack with a naive idea of what sieving should be. 3375: 2281: 131:
on these sets (options for giving some elements of these sets more "weight" than others). Furthermore, in some modern applications, sieves are used not to estimate the size of a sifted set, but to produce a function that is large on the set and mostly small outside it, while being easier to analyze
2783: 860: 4043:. Nevertheless, the more advanced sieves can still get very intricate and delicate (especially when combined with other deep techniques in number theory), and entire textbooks have been devoted to this single subfield of number theory; a classic reference is ( 1687: 4028:, which roughly speaking asserts that sieve theory methods have extreme difficulty distinguishing between numbers with an odd number of prime factors and numbers with an even number of prime factors. This parity problem is still not very well understood. 565: 1809: 3235: 2048: 1974: 2522: 2886: 437: 3806:. While the original broad aims of sieve theory still are largely unachieved, there have been some partial successes, especially in combination with other number theoretic tools. Highlights include: 2625: 1055: 654: 350: 2053: 731: 949: 3473: 2040: 1472: 1085: 2404: 3516: 3204: 219: 893: 3098: 3060: 3889: 315: 3405: 3022: 1876: 723: 617: 451: 271: 3909: 3692: 3993: 3598: 54: 3670: 3634: 3552: 2617: 2581: 2325: 1852: 1418: 1381: 1344: 3944: 2989: 1307: 1270: 1193: 1156: 986: 3724: 3152: 3125: 2436: 691: 3911:
is sufficiently small (fractions such as 1/10 are quite typical here). This lemma is usually too weak to sieve out primes (which generally require something like
2008: 1706: 1444: 1119: 3370:{\displaystyle \sum \limits _{d\mid n}\mu (d)g(d)=\prod \limits _{\begin{array}{c}p|n;\;p\in \mathbb {P} \end{array}}(1-g(p)),\quad \forall \;n\in \mathbb {N} .} 3768: 3748: 3425: 3227: 2953: 2933: 2913: 2545: 1464: 1233: 1213: 370: 2276:{\displaystyle {\begin{aligned}S({\mathcal {A}},\mathbb {P} ,7)&=A_{1}(x)-A_{2}(x)-A_{3}(x)-A_{5}(x)+A_{6}(x)+A_{10}(x)+A_{15}(x)-A_{30}(x).\end{aligned}}} 123:
numbers), which is typically somewhat larger than the original set, and easier to analyze. More sophisticated sieves also do not work directly with sets
119:
One successful approach is to approximate a specific sifted set of numbers (e.g. the set of prime numbers) by another, simpler set (e.g. the set of
1883: 3843:
even number is the sum of a prime and another number which is either a prime or a semiprime. These can be considered to be near-misses to the
3799: 4519: 4281: 4197: 2452: 317:
we want to sieve. However this abstraction allows for more general situations. Next we introduce a general set of prime numbers called the
2794: 3815:, which shows that the sum of the reciprocals of the twin primes converges (whereas the sum of the reciprocals of all primes diverges); 375: 1088: 4388: 4314: 4243: 4168: 4130: 4100: 3856: 76: 2778:{\displaystyle S({\mathcal {A}},{\mathcal {P}},z)=X\sum \limits _{d\mid P(z)}\mu (d)g(d)+\sum \limits _{d\mid P(z)}\mu (d)r_{d}(x)} 3951: 4379:, Cambridge studies in advanced mathematics, vol. 46, Translated from the second French edition (1995) by C. B. Thomas, 991: 4463: 4331: 4273: 4024: 626: 323: 855:{\displaystyle A_{\operatorname {sift} }:=\{a\in A|(a,p_{1}\cdots p_{k})=1\},\quad p_{1},\dots ,p_{k}\in {\mathcal {P}}} 37: 4458: 47: 41: 33: 898: 4380: 4306: 4092: 4063: 3430: 1682:{\displaystyle |A_{\operatorname {sift} }|=|A|-|E_{2}|-|E_{3}|+|E_{6}|-|E_{5}|+|E_{10}|+|E_{15}|-|E_{30}|+\cdots } 2013: 58: 2958:
The partial sum of the sifting function alternately over- and undercounts, so the remainder term will be huge.
1063: 4022:
The techniques of sieve theory can be quite powerful, but they seem to be limited by an obstacle known as the
2333: 4036: 3802:. One of the original purposes of sieve theory was to try to prove conjectures in number theory such as the 3727: 3478: 3160: 2443: 181: 4070:
to determine efficiently which members of a list of numbers can be completely factored into small primes.
4040: 2892: 868: 4553: 4414: 4336: 4080: 4067: 4055: 3844: 3803: 3065: 3027: 109: 560:{\displaystyle S({\mathcal {A}},{\mathcal {P}},z)=\sum \limits _{n\leq x,{\text{gcd}}(n,P(z))=1}a_{n}.} 3867: 3383:
a word of caution regarding the notation, in the literature one often identifies the set of sequences
276: 4121:, Tata Institute of Fundamental Research Lectures on Mathematics and Physics, vol. 72, Berlin: 3386: 2994: 1857: 704: 573: 227: 4192:. London Mathematical Society Monographs. Vol. 33. Princeton, NJ: Princeton University Press. 3848: 4453: 3894: 3675: 4345: 4298: 3958: 3840: 222: 156: 133: 3557: 1815: 4515: 4384: 4310: 4277: 4239: 4227: 4193: 4164: 4126: 4096: 3819: 3811: 3639: 3603: 3521: 2586: 2550: 2294: 1821: 1386: 1349: 1312: 3914: 2965: 1275: 1238: 1161: 1124: 954: 4507: 4423: 4355: 4265: 4223: 4211: 4156: 1804:{\displaystyle S({\mathcal {A}},{\mathcal {P}},z)=\sum \limits _{d\mid P(z)}\mu (d)A_{d}(x)} 4437: 4398: 4367: 4324: 4291: 4253: 4207: 4178: 4140: 4110: 3697: 3130: 3103: 4433: 4394: 4363: 4320: 4287: 4249: 4215: 4203: 4174: 4152: 4136: 4122: 4106: 4059: 2412: 667: 128: 3864:
numbers, then one can accurately estimate the number of elements left in the sieve after
1987: 1423: 1094: 4272:, American Mathematical Society Colloquium Publications, vol. 57, Providence, RI: 4261: 4235: 4035:, in the sense that it does not necessarily require sophisticated concepts from either 3787: 3753: 3733: 3410: 3212: 2938: 2918: 2898: 2530: 1449: 1218: 1198: 355: 113: 4547: 4483:
Brun, Viggo (1915). "Ăśber das Goldbachsche Gesetz und die Anzahl der Primzahlpaare".
3783: 93: 4405: 4084: 3998: 3836: 3795: 661: 120: 101: 4428: 4409: 4359: 4185: 3791: 620: 160: 4305:, Cambridge Tracts in Mathematics, vol. 70, Cambridge-New York-Melbourne: 4160: 4151:, Ergebnisse der Mathematik und ihrer Grenzgebiete (3), vol. 43, Berlin: 3779: 3024:
consisting of restricted Möbius functions. Choosing two appropriate sequences
2959: 148: 4511: 4031:
Compared with other methods in number theory, sieve theory is comparatively
4006: 3832: 1091:. This algorithm works like this: first one removes from the cardinality of 175: 4054:
The sieve methods discussed in this article are not closely related to the
2891:
One tries then to estimate the sifting function by finding upper and lower
1969:{\displaystyle A_{d}(x)=\sum \limits _{n\leq x,n\equiv 0{\pmod {d}}}a_{n}.} 3946:
iterations), but can be enough to obtain results regarding almost primes.
4234:. London Mathematical Society Monographs. Vol. 4. London-New York: 3154:, one can get lower and upper bounds for the original sifting functions 657: 4013:) generalizes Zhang's theorem to arbitrarily long sequences of primes. 2517:{\displaystyle g(1)=1,\qquad 0\leq g(p)<1\qquad p\in \mathbb {P} } 152: 144: 100:
of integers. The prototypical example of a sifted set is the set of
96:, designed to count, or more realistically to estimate the size of, 4350: 3955:, which asserts that there are infinitely many primes of the form 2881:{\displaystyle S({\mathcal {A}},{\mathcal {P}},z)=XG(x,z)+R(x,z).} 432:{\displaystyle P(z)=\prod \limits _{p\in {\mathcal {P}},p<z}p} 108:. Correspondingly, the prototypical example of a sieve is the 151:
in 1915. However Brun's work was inspired by the works of the
18: 2042:. The Möbius function is negative for every prime, so we get 1195:. Now since one has removed the numbers that are divisble by 3484: 3436: 3392: 2816: 2806: 2647: 2637: 2064: 2019: 1863: 1728: 1718: 997: 880: 847: 710: 473: 463: 407: 329: 187: 4091:, London Mathematical Society Student Texts, vol. 66, 3835:(the product of two primes); a closely related theorem of 4377:
Introduction to Analytic and Probabilistic Number Theory
4504:
An Introduction to Sieve Methods and Their Applications
4089:
An introduction to sieve methods and their applications
3229:
is multiplicative, one can also work with the identity
1050:{\displaystyle {\mathcal {P}}:=\{2,3,5,7,11,13\dots \}} 127:, but instead count them according to carefully chosen 4303:
Applications of sieve methods to the theory of numbers
3287: 3961: 3917: 3897: 3870: 3756: 3736: 3700: 3678: 3642: 3606: 3560: 3524: 3481: 3433: 3413: 3389: 3238: 3215: 3163: 3133: 3106: 3068: 3030: 2997: 2968: 2941: 2921: 2901: 2797: 2628: 2619:
is some remainder term. The sifting function becomes
2589: 2553: 2533: 2455: 2415: 2336: 2297: 2051: 2016: 1990: 1886: 1860: 1824: 1709: 1475: 1452: 1426: 1389: 1352: 1315: 1278: 1241: 1221: 1201: 1164: 1127: 1097: 1066: 994: 957: 901: 871: 734: 707: 670: 629: 576: 454: 378: 358: 326: 279: 230: 184: 3823:, which shows that there are infinitely many primes 3672:to be already the cardinality of this set. We used 649:{\displaystyle A_{\operatorname {sift} }\subseteq A} 345:{\displaystyle {\mathcal {P}}\subseteq \mathbb {P} } 16:
Ways to estimate the size of sifted sets of integers
1420:, i.e. the cardinality of all numbers divisible by 221:. In the most basic case this sequence is just the 4535: 4066:. Those factorization methods use the idea of the 4048: 3987: 3938: 3903: 3883: 3762: 3742: 3718: 3686: 3664: 3628: 3592: 3546: 3510: 3467: 3419: 3399: 3369: 3221: 3198: 3146: 3119: 3092: 3054: 3016: 2983: 2947: 2927: 2907: 2880: 2777: 2611: 2575: 2539: 2516: 2430: 2398: 2319: 2275: 2034: 2002: 1968: 1870: 1846: 1803: 1681: 1466:. This leads to the inclusion–exclusion principle 1458: 1438: 1412: 1375: 1338: 1301: 1264: 1227: 1207: 1187: 1150: 1113: 1079: 1049: 980: 943: 887: 854: 717: 685: 648: 611: 559: 431: 364: 344: 309: 265: 213: 4119:Lectures on Sieve Methods and Prime Number Theory 4044: 3860:, which asserts that if one is sifting a set of 46:but its sources remain unclear because it lacks 2991:in the sifting function with a weight sequence 4502:Cojocaru, Alina Carmen; Murty, M. Ram (2005). 4005:), which shows that there are infinitely many 944:{\displaystyle E_{p}=\{pn:n\in \mathbb {N} \}} 1060:If one wants to calculate the cardinality of 8: 3468:{\displaystyle {\mathcal {A}}=\{s:s\leq x\}} 3462: 3444: 1044: 1005: 938: 915: 806: 748: 442:The goal of sieve theory is to estimate the 304: 286: 171:For information on notation see at the end. 2035:{\displaystyle {\mathcal {P}}=\mathbb {P} } 163:and only two of his manuscripts survived. 3352: 3304: 1383:again. Additionally one has now to remove 4427: 4349: 4007:pairs of primes within a bounded distance 3979: 3966: 3960: 3926: 3922: 3916: 3896: 3875: 3869: 3755: 3735: 3699: 3680: 3679: 3677: 3647: 3641: 3611: 3605: 3585: 3570: 3561: 3559: 3529: 3523: 3499: 3483: 3482: 3480: 3435: 3434: 3432: 3412: 3391: 3390: 3388: 3360: 3359: 3312: 3311: 3293: 3286: 3243: 3237: 3214: 3187: 3168: 3162: 3138: 3132: 3111: 3105: 3081: 3076: 3067: 3043: 3038: 3029: 3005: 2996: 2967: 2940: 2920: 2900: 2815: 2814: 2805: 2804: 2796: 2760: 2723: 2671: 2646: 2645: 2636: 2635: 2627: 2594: 2588: 2558: 2552: 2532: 2510: 2509: 2454: 2414: 2381: 2341: 2335: 2302: 2296: 2251: 2229: 2207: 2185: 2163: 2141: 2119: 2097: 2073: 2072: 2063: 2062: 2052: 2050: 2028: 2027: 2018: 2017: 2015: 1989: 1957: 1935: 1913: 1891: 1885: 1862: 1861: 1859: 1829: 1823: 1786: 1749: 1727: 1726: 1717: 1716: 1708: 1697:We can rewrite the sifting function with 1668: 1662: 1653: 1645: 1639: 1630: 1622: 1616: 1607: 1599: 1593: 1584: 1576: 1570: 1561: 1553: 1547: 1538: 1530: 1524: 1515: 1507: 1499: 1491: 1485: 1476: 1474: 1451: 1425: 1405: 1399: 1390: 1388: 1368: 1362: 1353: 1351: 1331: 1325: 1316: 1314: 1294: 1288: 1279: 1277: 1257: 1251: 1242: 1240: 1220: 1200: 1180: 1174: 1165: 1163: 1143: 1137: 1128: 1126: 1106: 1098: 1096: 1080:{\displaystyle A_{\operatorname {sift} }} 1071: 1065: 996: 995: 993: 973: 967: 958: 956: 934: 933: 906: 900: 879: 878: 870: 846: 845: 836: 817: 791: 778: 760: 739: 733: 709: 708: 706: 669: 634: 628: 594: 581: 575: 548: 507: 494: 472: 471: 462: 461: 453: 406: 405: 398: 377: 357: 338: 337: 328: 327: 325: 278: 248: 235: 229: 202: 186: 185: 183: 77:Learn how and when to remove this message 3554:is sometimes notated as the cardinality 3100:and denoting the sifting functions with 4475: 4010: 2962:'s idea to improve this was to replace 2399:{\displaystyle A_{d}(x)=g(d)X+r_{d}(x)} 3511:{\displaystyle {\mathcal {A}}=(a_{n})} 3199:{\displaystyle S^{-}\leq S\leq S^{+}.} 1235:twice, one has to add the cardinality 214:{\displaystyle {\mathcal {A}}=(a_{n})} 4334:(2015). "Small gaps between primes". 4002: 7: 3283: 3240: 2720: 2668: 2287:Approximation of the congruence sum 1943: 1936: 1910: 1746: 888:{\displaystyle p\in {\mathcal {P}}} 491: 395: 3349: 3093:{\displaystyle (\lambda _{d}^{+})} 3055:{\displaystyle (\lambda _{d}^{-})} 92:is a set of general techniques in 14: 3857:fundamental lemma of sieve theory 3518:. Also in the literature the sum 697:The inclusion–exclusion principle 178:sequence of non-negative numbers 3884:{\displaystyle N^{\varepsilon }} 3694:to denote the set of primes and 23: 4485:Archiv for Math. Naturvidenskab 3348: 2502: 2477: 1272:. In the next step one removes 812: 310:{\displaystyle A=\{s:s\leq x\}} 4536:Iwaniec & Friedlander 2010 4506:. Cambridge University Press. 4049:Iwaniec & Friedlander 2010 3713: 3701: 3659: 3653: 3623: 3617: 3586: 3582: 3576: 3562: 3541: 3535: 3505: 3492: 3427:itself. This means one writes 3400:{\displaystyle {\mathcal {A}}} 3342: 3339: 3333: 3321: 3294: 3276: 3270: 3264: 3258: 3087: 3069: 3049: 3031: 3017:{\displaystyle (\lambda _{d})} 3011: 2998: 2978: 2972: 2872: 2860: 2851: 2839: 2827: 2801: 2772: 2766: 2753: 2747: 2739: 2733: 2713: 2707: 2701: 2695: 2687: 2681: 2658: 2632: 2606: 2600: 2570: 2564: 2493: 2487: 2465: 2459: 2425: 2419: 2393: 2387: 2368: 2362: 2353: 2347: 2314: 2308: 2263: 2257: 2241: 2235: 2219: 2213: 2197: 2191: 2175: 2169: 2153: 2147: 2131: 2125: 2109: 2103: 2083: 2059: 1947: 1937: 1903: 1897: 1871:{\displaystyle {\mathcal {P}}} 1841: 1835: 1798: 1792: 1779: 1773: 1765: 1759: 1739: 1713: 1669: 1654: 1646: 1631: 1623: 1608: 1600: 1585: 1577: 1562: 1554: 1539: 1531: 1516: 1508: 1500: 1492: 1477: 1406: 1391: 1369: 1354: 1332: 1317: 1295: 1280: 1258: 1243: 1181: 1166: 1144: 1129: 1107: 1099: 974: 959: 797: 765: 761: 718:{\displaystyle {\mathcal {P}}} 680: 674: 612:{\displaystyle a_{n}=1_{A}(n)} 606: 600: 533: 530: 524: 512: 484: 458: 388: 382: 266:{\displaystyle a_{n}=1_{A}(n)} 260: 254: 208: 195: 1: 4410:"Bounded gaps between primes" 4274:American Mathematical Society 4047:) and a more modern text is ( 4045:Halberstam & Richert 1974 3800:Goldston-Pintz-Yıldırım sieve 1089:inclusion–exclusion principle 3904:{\displaystyle \varepsilon } 3687:{\displaystyle \mathbb {P} } 988:be the cardinality. Let now 104:up to some prescribed limit 4459:Encyclopedia of Mathematics 4429:10.4007/annals.2014.179.3.7 4360:10.4007/annals.2015.181.1.7 4009:. The Maynard–Tao theorem ( 3988:{\displaystyle a^{2}+b^{4}} 3952:Friedlander–Iwaniec theorem 3831:+ 2 is either a prime or a 1854:induced by the elements of 4570: 4381:Cambridge University Press 4375:Tenenbaum, GĂ©rald (1995), 4307:Cambridge University Press 4117:Motohashi, Yoichi (1983), 4093:Cambridge University Press 4064:general number field sieve 4058:sieve methods such as the 4018:Techniques of sieve theory 3778:Modern sieves include the 3593:{\displaystyle |A_{d}(x)|} 4452:Bredikhin, B.M. (2001) , 4161:10.1007/978-3-662-04658-6 3891:iterations provided that 4512:10.1017/CBO9780511615993 4147:Greaves, George (2001), 3665:{\displaystyle A_{d}(x)} 3636:, while we have defined 3629:{\displaystyle A_{d}(x)} 3547:{\displaystyle A_{d}(x)} 2612:{\displaystyle r_{d}(x)} 2576:{\displaystyle A_{1}(x)} 2320:{\displaystyle A_{d}(x)} 1847:{\displaystyle A_{d}(x)} 1692: 1413:{\displaystyle |E_{30}|} 1376:{\displaystyle |E_{15}|} 1339:{\displaystyle |E_{10}|} 352:and their product up to 32:This article includes a 4149:Sieves in number theory 4037:algebraic number theory 3939:{\displaystyle N^{1/2}} 3728:greatest common divisor 2984:{\displaystyle \mu (d)} 2547:is an approximation of 2444:multiplicative function 1302:{\displaystyle |E_{5}|} 1265:{\displaystyle |E_{6}|} 1188:{\displaystyle |E_{3}|} 1151:{\displaystyle |E_{2}|} 1057:be some set of primes. 981:{\displaystyle |E_{p}|} 134:characteristic function 61:more precise citations. 4190:Prime-detecting sieves 4081:Cojocaru, Alina Carmen 4041:analytic number theory 3989: 3940: 3905: 3885: 3764: 3744: 3720: 3688: 3666: 3630: 3594: 3548: 3512: 3469: 3421: 3401: 3371: 3223: 3200: 3148: 3121: 3094: 3056: 3018: 2985: 2949: 2929: 2909: 2882: 2779: 2613: 2577: 2541: 2518: 2432: 2400: 2321: 2291:One assumes then that 2277: 2036: 2004: 1970: 1872: 1848: 1805: 1683: 1460: 1440: 1414: 1377: 1340: 1303: 1266: 1229: 1209: 1189: 1152: 1115: 1081: 1051: 982: 945: 889: 856: 719: 687: 650: 613: 561: 433: 366: 346: 311: 267: 215: 143:was first used by the 112:, or the more general 4415:Annals of Mathematics 4337:Annals of Mathematics 4068:sieve of Eratosthenes 4056:integer factorization 3990: 3941: 3906: 3886: 3845:twin prime conjecture 3804:twin prime conjecture 3765: 3745: 3721: 3719:{\displaystyle (a,b)} 3689: 3667: 3631: 3595: 3549: 3513: 3475:to define a sequence 3470: 3422: 3402: 3372: 3224: 3201: 3149: 3147:{\displaystyle S^{+}} 3122: 3120:{\displaystyle S^{-}} 3095: 3057: 3019: 2986: 2950: 2930: 2910: 2883: 2780: 2614: 2578: 2542: 2519: 2433: 2401: 2322: 2278: 2037: 2005: 1971: 1873: 1849: 1806: 1684: 1461: 1441: 1415: 1378: 1341: 1304: 1267: 1230: 1210: 1190: 1153: 1116: 1082: 1052: 983: 946: 890: 857: 720: 688: 656:of numbers, that are 651: 619:this just counts the 614: 562: 434: 367: 347: 312: 268: 216: 110:sieve of Eratosthenes 3959: 3915: 3895: 3868: 3754: 3734: 3698: 3676: 3640: 3604: 3558: 3522: 3479: 3431: 3411: 3387: 3236: 3213: 3161: 3131: 3104: 3066: 3028: 2995: 2966: 2939: 2919: 2899: 2795: 2626: 2587: 2551: 2531: 2453: 2431:{\displaystyle g(d)} 2413: 2334: 2295: 2049: 2014: 1988: 1884: 1858: 1822: 1707: 1473: 1450: 1424: 1387: 1350: 1313: 1276: 1239: 1219: 1199: 1162: 1125: 1095: 1087:, one can apply the 1064: 992: 955: 899: 869: 732: 705: 686:{\displaystyle P(z)} 668: 627: 574: 452: 376: 356: 324: 277: 228: 182: 4299:Hooley, Christopher 3849:Goldbach conjecture 3839:asserts that every 3086: 3048: 2003:{\displaystyle z=7} 1818:and some functions 1699:Legendre's identity 1693:Legendre's identity 1439:{\displaystyle 2,3} 1114:{\displaystyle |A|} 865:and for each prime 174:We start with some 4383:, pp. 56–79, 4228:Richert, Hans-Egon 3985: 3936: 3901: 3881: 3841:sufficiently large 3760: 3740: 3716: 3684: 3662: 3626: 3590: 3544: 3508: 3465: 3417: 3397: 3367: 3320: 3318: 3254: 3219: 3196: 3144: 3117: 3090: 3072: 3052: 3034: 3014: 2981: 2945: 2925: 2905: 2878: 2775: 2743: 2691: 2609: 2573: 2537: 2514: 2428: 2396: 2327:can be written as 2317: 2273: 2271: 2032: 2000: 1966: 1952: 1868: 1844: 1801: 1769: 1679: 1456: 1436: 1410: 1373: 1336: 1299: 1262: 1225: 1205: 1185: 1148: 1111: 1077: 1047: 978: 941: 885: 852: 715: 683: 646: 609: 557: 543: 429: 425: 362: 342: 307: 263: 223:indicator function 211: 167:Basic sieve theory 34:list of references 4521:978-0-521-84816-9 4283:978-0-8218-4970-5 4266:Friedlander, John 4224:Halberstam, Heini 4199:978-0-691-12437-7 3763:{\displaystyle b} 3743:{\displaystyle a} 3420:{\displaystyle A} 3282: 3239: 3222:{\displaystyle g} 2948:{\displaystyle R} 2928:{\displaystyle G} 2908:{\displaystyle S} 2719: 2667: 2540:{\displaystyle X} 1909: 1745: 1459:{\displaystyle 5} 1228:{\displaystyle 3} 1208:{\displaystyle 2} 510: 490: 394: 365:{\displaystyle z} 87: 86: 79: 4561: 4539: 4532: 4526: 4525: 4499: 4493: 4492: 4480: 4466: 4441: 4431: 4422:(3): 1121–1174. 4401: 4371: 4353: 4327: 4294: 4257: 4219: 4181: 4143: 4113: 3994: 3992: 3991: 3986: 3984: 3983: 3971: 3970: 3945: 3943: 3942: 3937: 3935: 3934: 3930: 3910: 3908: 3907: 3902: 3890: 3888: 3887: 3882: 3880: 3879: 3774:Types of sieving 3769: 3767: 3766: 3761: 3749: 3747: 3746: 3741: 3725: 3723: 3722: 3717: 3693: 3691: 3690: 3685: 3683: 3671: 3669: 3668: 3663: 3652: 3651: 3635: 3633: 3632: 3627: 3616: 3615: 3599: 3597: 3596: 3591: 3589: 3575: 3574: 3565: 3553: 3551: 3550: 3545: 3534: 3533: 3517: 3515: 3514: 3509: 3504: 3503: 3488: 3487: 3474: 3472: 3471: 3466: 3440: 3439: 3426: 3424: 3423: 3418: 3406: 3404: 3403: 3398: 3396: 3395: 3376: 3374: 3373: 3368: 3363: 3319: 3315: 3297: 3253: 3228: 3226: 3225: 3220: 3205: 3203: 3202: 3197: 3192: 3191: 3173: 3172: 3153: 3151: 3150: 3145: 3143: 3142: 3126: 3124: 3123: 3118: 3116: 3115: 3099: 3097: 3096: 3091: 3085: 3080: 3061: 3059: 3058: 3053: 3047: 3042: 3023: 3021: 3020: 3015: 3010: 3009: 2990: 2988: 2987: 2982: 2954: 2952: 2951: 2946: 2934: 2932: 2931: 2926: 2914: 2912: 2911: 2906: 2887: 2885: 2884: 2879: 2820: 2819: 2810: 2809: 2784: 2782: 2781: 2776: 2765: 2764: 2742: 2690: 2651: 2650: 2641: 2640: 2618: 2616: 2615: 2610: 2599: 2598: 2582: 2580: 2579: 2574: 2563: 2562: 2546: 2544: 2543: 2538: 2523: 2521: 2520: 2515: 2513: 2437: 2435: 2434: 2429: 2405: 2403: 2402: 2397: 2386: 2385: 2346: 2345: 2326: 2324: 2323: 2318: 2307: 2306: 2282: 2280: 2279: 2274: 2272: 2256: 2255: 2234: 2233: 2212: 2211: 2190: 2189: 2168: 2167: 2146: 2145: 2124: 2123: 2102: 2101: 2076: 2068: 2067: 2041: 2039: 2038: 2033: 2031: 2023: 2022: 2009: 2007: 2006: 2001: 1975: 1973: 1972: 1967: 1962: 1961: 1951: 1950: 1896: 1895: 1877: 1875: 1874: 1869: 1867: 1866: 1853: 1851: 1850: 1845: 1834: 1833: 1810: 1808: 1807: 1802: 1791: 1790: 1768: 1732: 1731: 1722: 1721: 1688: 1686: 1685: 1680: 1672: 1667: 1666: 1657: 1649: 1644: 1643: 1634: 1626: 1621: 1620: 1611: 1603: 1598: 1597: 1588: 1580: 1575: 1574: 1565: 1557: 1552: 1551: 1542: 1534: 1529: 1528: 1519: 1511: 1503: 1495: 1490: 1489: 1480: 1465: 1463: 1462: 1457: 1445: 1443: 1442: 1437: 1419: 1417: 1416: 1411: 1409: 1404: 1403: 1394: 1382: 1380: 1379: 1374: 1372: 1367: 1366: 1357: 1345: 1343: 1342: 1337: 1335: 1330: 1329: 1320: 1308: 1306: 1305: 1300: 1298: 1293: 1292: 1283: 1271: 1269: 1268: 1263: 1261: 1256: 1255: 1246: 1234: 1232: 1231: 1226: 1214: 1212: 1211: 1206: 1194: 1192: 1191: 1186: 1184: 1179: 1178: 1169: 1157: 1155: 1154: 1149: 1147: 1142: 1141: 1132: 1121:the cardinality 1120: 1118: 1117: 1112: 1110: 1102: 1086: 1084: 1083: 1078: 1076: 1075: 1056: 1054: 1053: 1048: 1001: 1000: 987: 985: 984: 979: 977: 972: 971: 962: 950: 948: 947: 942: 937: 911: 910: 894: 892: 891: 886: 884: 883: 861: 859: 858: 853: 851: 850: 841: 840: 822: 821: 796: 795: 783: 782: 764: 744: 743: 724: 722: 721: 716: 714: 713: 692: 690: 689: 684: 655: 653: 652: 647: 639: 638: 618: 616: 615: 610: 599: 598: 586: 585: 566: 564: 563: 558: 553: 552: 542: 511: 508: 477: 476: 467: 466: 444:sifting function 438: 436: 435: 430: 424: 411: 410: 371: 369: 368: 363: 351: 349: 348: 343: 341: 333: 332: 316: 314: 313: 308: 272: 270: 269: 264: 253: 252: 240: 239: 220: 218: 217: 212: 207: 206: 191: 190: 159:who died in the 129:weight functions 82: 75: 71: 68: 62: 57:this article by 48:inline citations 27: 26: 19: 4569: 4568: 4564: 4563: 4562: 4560: 4559: 4558: 4544: 4543: 4542: 4533: 4529: 4522: 4501: 4500: 4496: 4482: 4481: 4477: 4473: 4451: 4448: 4404: 4391: 4374: 4330: 4317: 4297: 4284: 4270:Opera de cribro 4262:Iwaniec, Henryk 4260: 4246: 4222: 4200: 4184: 4171: 4153:Springer-Verlag 4146: 4133: 4123:Springer-Verlag 4116: 4103: 4079: 4076: 4060:quadratic sieve 4020: 3975: 3962: 3957: 3956: 3918: 3913: 3912: 3893: 3892: 3871: 3866: 3865: 3776: 3752: 3751: 3732: 3731: 3696: 3695: 3674: 3673: 3643: 3638: 3637: 3607: 3602: 3601: 3566: 3556: 3555: 3525: 3520: 3519: 3495: 3477: 3476: 3429: 3428: 3409: 3408: 3385: 3384: 3317: 3316: 3234: 3233: 3211: 3210: 3183: 3164: 3159: 3158: 3134: 3129: 3128: 3107: 3102: 3101: 3064: 3063: 3026: 3025: 3001: 2993: 2992: 2964: 2963: 2937: 2936: 2917: 2916: 2897: 2896: 2793: 2792: 2756: 2624: 2623: 2590: 2585: 2584: 2554: 2549: 2548: 2529: 2528: 2451: 2450: 2411: 2410: 2377: 2337: 2332: 2331: 2298: 2293: 2292: 2289: 2270: 2269: 2247: 2225: 2203: 2181: 2159: 2137: 2115: 2093: 2086: 2047: 2046: 2012: 2011: 1986: 1985: 1982: 1953: 1887: 1882: 1881: 1856: 1855: 1825: 1820: 1819: 1816:Möbius function 1782: 1705: 1704: 1695: 1658: 1635: 1612: 1589: 1566: 1543: 1520: 1481: 1471: 1470: 1448: 1447: 1422: 1421: 1395: 1385: 1384: 1358: 1348: 1347: 1321: 1311: 1310: 1284: 1274: 1273: 1247: 1237: 1236: 1217: 1216: 1197: 1196: 1170: 1160: 1159: 1133: 1123: 1122: 1093: 1092: 1067: 1062: 1061: 990: 989: 963: 953: 952: 902: 897: 896: 895:denote the set 867: 866: 832: 813: 787: 774: 735: 730: 729: 703: 702: 699: 666: 665: 630: 625: 624: 590: 577: 572: 571: 570:In the case of 544: 450: 449: 374: 373: 354: 353: 322: 321: 275: 274: 244: 231: 226: 225: 198: 180: 179: 169: 83: 72: 66: 63: 52: 38:related reading 28: 24: 17: 12: 11: 5: 4567: 4565: 4557: 4556: 4546: 4545: 4541: 4540: 4527: 4520: 4494: 4474: 4472: 4469: 4468: 4467: 4454:"Sieve method" 4447: 4446:External links 4444: 4443: 4442: 4402: 4389: 4372: 4344:(1): 383–413. 4332:Maynard, James 4328: 4315: 4295: 4282: 4258: 4244: 4236:Academic Press 4220: 4198: 4182: 4169: 4144: 4131: 4114: 4101: 4075: 4072: 4025:parity problem 4019: 4016: 4015: 4014: 3996: 3982: 3978: 3974: 3969: 3965: 3947: 3933: 3929: 3925: 3921: 3900: 3878: 3874: 3852: 3820:Chen's theorem 3816: 3812:Brun's theorem 3775: 3772: 3759: 3739: 3715: 3712: 3709: 3706: 3703: 3682: 3661: 3658: 3655: 3650: 3646: 3625: 3622: 3619: 3614: 3610: 3588: 3584: 3581: 3578: 3573: 3569: 3564: 3543: 3540: 3537: 3532: 3528: 3507: 3502: 3498: 3494: 3491: 3486: 3464: 3461: 3458: 3455: 3452: 3449: 3446: 3443: 3438: 3416: 3394: 3378: 3377: 3366: 3362: 3358: 3355: 3351: 3347: 3344: 3341: 3338: 3335: 3332: 3329: 3326: 3323: 3314: 3310: 3307: 3303: 3300: 3296: 3292: 3289: 3288: 3285: 3281: 3278: 3275: 3272: 3269: 3266: 3263: 3260: 3257: 3252: 3249: 3246: 3242: 3218: 3207: 3206: 3195: 3190: 3186: 3182: 3179: 3176: 3171: 3167: 3141: 3137: 3114: 3110: 3089: 3084: 3079: 3075: 3071: 3051: 3046: 3041: 3037: 3033: 3013: 3008: 3004: 3000: 2980: 2977: 2974: 2971: 2944: 2924: 2904: 2889: 2888: 2877: 2874: 2871: 2868: 2865: 2862: 2859: 2856: 2853: 2850: 2847: 2844: 2841: 2838: 2835: 2832: 2829: 2826: 2823: 2818: 2813: 2808: 2803: 2800: 2786: 2785: 2774: 2771: 2768: 2763: 2759: 2755: 2752: 2749: 2746: 2741: 2738: 2735: 2732: 2729: 2726: 2722: 2718: 2715: 2712: 2709: 2706: 2703: 2700: 2697: 2694: 2689: 2686: 2683: 2680: 2677: 2674: 2670: 2666: 2663: 2660: 2657: 2654: 2649: 2644: 2639: 2634: 2631: 2608: 2605: 2602: 2597: 2593: 2572: 2569: 2566: 2561: 2557: 2536: 2525: 2524: 2512: 2508: 2505: 2501: 2498: 2495: 2492: 2489: 2486: 2483: 2480: 2476: 2473: 2470: 2467: 2464: 2461: 2458: 2427: 2424: 2421: 2418: 2407: 2406: 2395: 2392: 2389: 2384: 2380: 2376: 2373: 2370: 2367: 2364: 2361: 2358: 2355: 2352: 2349: 2344: 2340: 2316: 2313: 2310: 2305: 2301: 2288: 2285: 2284: 2283: 2268: 2265: 2262: 2259: 2254: 2250: 2246: 2243: 2240: 2237: 2232: 2228: 2224: 2221: 2218: 2215: 2210: 2206: 2202: 2199: 2196: 2193: 2188: 2184: 2180: 2177: 2174: 2171: 2166: 2162: 2158: 2155: 2152: 2149: 2144: 2140: 2136: 2133: 2130: 2127: 2122: 2118: 2114: 2111: 2108: 2105: 2100: 2096: 2092: 2089: 2087: 2085: 2082: 2079: 2075: 2071: 2066: 2061: 2058: 2055: 2054: 2030: 2026: 2021: 1999: 1996: 1993: 1981: 1978: 1977: 1976: 1965: 1960: 1956: 1949: 1946: 1942: 1939: 1934: 1931: 1928: 1925: 1922: 1919: 1916: 1912: 1908: 1905: 1902: 1899: 1894: 1890: 1865: 1843: 1840: 1837: 1832: 1828: 1812: 1811: 1800: 1797: 1794: 1789: 1785: 1781: 1778: 1775: 1772: 1767: 1764: 1761: 1758: 1755: 1752: 1748: 1744: 1741: 1738: 1735: 1730: 1725: 1720: 1715: 1712: 1694: 1691: 1690: 1689: 1678: 1675: 1671: 1665: 1661: 1656: 1652: 1648: 1642: 1638: 1633: 1629: 1625: 1619: 1615: 1610: 1606: 1602: 1596: 1592: 1587: 1583: 1579: 1573: 1569: 1564: 1560: 1556: 1550: 1546: 1541: 1537: 1533: 1527: 1523: 1518: 1514: 1510: 1506: 1502: 1498: 1494: 1488: 1484: 1479: 1455: 1435: 1432: 1429: 1408: 1402: 1398: 1393: 1371: 1365: 1361: 1356: 1334: 1328: 1324: 1319: 1297: 1291: 1287: 1282: 1260: 1254: 1250: 1245: 1224: 1204: 1183: 1177: 1173: 1168: 1146: 1140: 1136: 1131: 1109: 1105: 1101: 1074: 1070: 1046: 1043: 1040: 1037: 1034: 1031: 1028: 1025: 1022: 1019: 1016: 1013: 1010: 1007: 1004: 999: 976: 970: 966: 961: 940: 936: 932: 929: 926: 923: 920: 917: 914: 909: 905: 882: 877: 874: 863: 862: 849: 844: 839: 835: 831: 828: 825: 820: 816: 811: 808: 805: 802: 799: 794: 790: 786: 781: 777: 773: 770: 767: 763: 759: 756: 753: 750: 747: 742: 738: 712: 698: 695: 682: 679: 676: 673: 645: 642: 637: 633: 608: 605: 602: 597: 593: 589: 584: 580: 568: 567: 556: 551: 547: 541: 538: 535: 532: 529: 526: 523: 520: 517: 514: 506: 503: 500: 497: 493: 489: 486: 483: 480: 475: 470: 465: 460: 457: 428: 423: 420: 417: 414: 409: 404: 401: 397: 393: 390: 387: 384: 381: 372:as a function 361: 340: 336: 331: 306: 303: 300: 297: 294: 291: 288: 285: 282: 262: 259: 256: 251: 247: 243: 238: 234: 210: 205: 201: 197: 194: 189: 168: 165: 155:mathematician 147:mathematician 114:Legendre sieve 85: 84: 42:external links 31: 29: 22: 15: 13: 10: 9: 6: 4: 3: 2: 4566: 4555: 4552: 4551: 4549: 4537: 4531: 4528: 4523: 4517: 4513: 4509: 4505: 4498: 4495: 4490: 4486: 4479: 4476: 4470: 4465: 4461: 4460: 4455: 4450: 4449: 4445: 4439: 4435: 4430: 4425: 4421: 4417: 4416: 4411: 4407: 4406:Zhang, Yitang 4403: 4400: 4396: 4392: 4390:0-521-41261-7 4386: 4382: 4378: 4373: 4369: 4365: 4361: 4357: 4352: 4347: 4343: 4339: 4338: 4333: 4329: 4326: 4322: 4318: 4316:0-521-20915-3 4312: 4308: 4304: 4300: 4296: 4293: 4289: 4285: 4279: 4275: 4271: 4267: 4263: 4259: 4255: 4251: 4247: 4245:0-12-318250-6 4241: 4237: 4233: 4232:Sieve Methods 4229: 4225: 4221: 4217: 4213: 4209: 4205: 4201: 4195: 4191: 4187: 4183: 4180: 4176: 4172: 4170:3-540-41647-1 4166: 4162: 4158: 4154: 4150: 4145: 4142: 4138: 4134: 4132:3-540-12281-8 4128: 4124: 4120: 4115: 4112: 4108: 4104: 4102:0-521-84816-4 4098: 4094: 4090: 4086: 4085:Murty, M. Ram 4082: 4078: 4077: 4073: 4071: 4069: 4065: 4061: 4057: 4052: 4050: 4046: 4042: 4038: 4034: 4029: 4027: 4026: 4017: 4012: 4008: 4004: 4000: 3997: 3980: 3976: 3972: 3967: 3963: 3954: 3953: 3948: 3931: 3927: 3923: 3919: 3898: 3876: 3872: 3863: 3859: 3858: 3853: 3851:respectively. 3850: 3846: 3842: 3838: 3834: 3830: 3826: 3822: 3821: 3817: 3814: 3813: 3809: 3808: 3807: 3805: 3801: 3797: 3793: 3789: 3785: 3784:Selberg sieve 3781: 3773: 3771: 3757: 3737: 3729: 3710: 3707: 3704: 3656: 3648: 3644: 3620: 3612: 3608: 3579: 3571: 3567: 3538: 3530: 3526: 3500: 3496: 3489: 3459: 3456: 3453: 3450: 3447: 3441: 3414: 3407:with the set 3382: 3364: 3356: 3353: 3345: 3336: 3330: 3327: 3324: 3308: 3305: 3301: 3298: 3290: 3279: 3273: 3267: 3261: 3255: 3250: 3247: 3244: 3232: 3231: 3230: 3216: 3193: 3188: 3184: 3180: 3177: 3174: 3169: 3165: 3157: 3156: 3155: 3139: 3135: 3112: 3108: 3082: 3077: 3073: 3044: 3039: 3035: 3006: 3002: 2975: 2969: 2961: 2956: 2942: 2922: 2915:respectively 2902: 2894: 2875: 2869: 2866: 2863: 2857: 2854: 2848: 2845: 2842: 2836: 2833: 2830: 2824: 2821: 2811: 2798: 2791: 2790: 2789: 2769: 2761: 2757: 2750: 2744: 2736: 2730: 2727: 2724: 2716: 2710: 2704: 2698: 2692: 2684: 2678: 2675: 2672: 2664: 2661: 2655: 2652: 2642: 2629: 2622: 2621: 2620: 2603: 2595: 2591: 2567: 2559: 2555: 2534: 2506: 2503: 2499: 2496: 2490: 2484: 2481: 2478: 2474: 2471: 2468: 2462: 2456: 2449: 2448: 2447: 2445: 2441: 2422: 2416: 2390: 2382: 2378: 2374: 2371: 2365: 2359: 2356: 2350: 2342: 2338: 2330: 2329: 2328: 2311: 2303: 2299: 2286: 2266: 2260: 2252: 2248: 2244: 2238: 2230: 2226: 2222: 2216: 2208: 2204: 2200: 2194: 2186: 2182: 2178: 2172: 2164: 2160: 2156: 2150: 2142: 2138: 2134: 2128: 2120: 2116: 2112: 2106: 2098: 2094: 2090: 2088: 2080: 2077: 2069: 2056: 2045: 2044: 2043: 2024: 1997: 1994: 1991: 1979: 1963: 1958: 1954: 1944: 1940: 1932: 1929: 1926: 1923: 1920: 1917: 1914: 1906: 1900: 1892: 1888: 1880: 1879: 1878: 1838: 1830: 1826: 1817: 1814:by using the 1795: 1787: 1783: 1776: 1770: 1762: 1756: 1753: 1750: 1742: 1736: 1733: 1723: 1710: 1703: 1702: 1701: 1700: 1676: 1673: 1663: 1659: 1650: 1640: 1636: 1627: 1617: 1613: 1604: 1594: 1590: 1581: 1571: 1567: 1558: 1548: 1544: 1535: 1525: 1521: 1512: 1504: 1496: 1486: 1482: 1469: 1468: 1467: 1453: 1433: 1430: 1427: 1400: 1396: 1363: 1359: 1326: 1322: 1289: 1285: 1252: 1248: 1222: 1202: 1175: 1171: 1138: 1134: 1103: 1090: 1072: 1068: 1058: 1041: 1038: 1035: 1032: 1029: 1026: 1023: 1020: 1017: 1014: 1011: 1008: 1002: 968: 964: 930: 927: 924: 921: 918: 912: 907: 903: 875: 872: 842: 837: 833: 829: 826: 823: 818: 814: 809: 803: 800: 792: 788: 784: 779: 775: 771: 768: 757: 754: 751: 745: 740: 736: 728: 727: 726: 696: 694: 677: 671: 663: 662:prime factors 659: 643: 640: 635: 631: 622: 603: 595: 591: 587: 582: 578: 554: 549: 545: 539: 536: 527: 521: 518: 515: 504: 501: 498: 495: 487: 481: 478: 468: 455: 448: 447: 446: 445: 440: 426: 421: 418: 415: 412: 402: 399: 391: 385: 379: 359: 334: 320: 319:sifting range 301: 298: 295: 292: 289: 283: 280: 257: 249: 245: 241: 236: 232: 224: 203: 199: 192: 177: 172: 166: 164: 162: 158: 154: 150: 146: 142: 137: 135: 130: 126: 122: 117: 115: 111: 107: 103: 102:prime numbers 99: 95: 94:number theory 91: 81: 78: 70: 60: 56: 50: 49: 43: 39: 35: 30: 21: 20: 4554:Sieve theory 4530: 4503: 4497: 4488: 4484: 4478: 4457: 4419: 4413: 4376: 4341: 4335: 4302: 4269: 4231: 4189: 4186:Harman, Glyn 4148: 4118: 4088: 4053: 4032: 4030: 4023: 4021: 4011:Maynard 2015 4001:'s theorem ( 3950: 3861: 3855: 3837:Chen Jingrun 3828: 3824: 3818: 3810: 3796:larger sieve 3777: 3600:of some set 3380: 3379: 3208: 2957: 2890: 2788:or in short 2787: 2526: 2442:, meaning a 2439: 2408: 2290: 1983: 1813: 1698: 1696: 1059: 864: 700: 623:of a subset 569: 443: 441: 318: 273:of some set 173: 170: 140: 138: 136:of the set. 124: 121:almost prime 118: 105: 97: 90:Sieve theory 89: 88: 73: 64: 53:Please help 45: 3792:large sieve 3788:Turán sieve 621:cardinality 161:World War I 157:Jean Merlin 98:sifted sets 59:introducing 4471:References 4216:1220.11118 4074:Literature 4033:elementary 4003:Zhang 2014 3827:such that 3780:Brun sieve 2446:such that 149:Viggo Brun 4464:EMS Press 4351:1311.4600 3899:ε 3877:ε 3833:semiprime 3457:≤ 3381:Notation: 3357:∈ 3350:∀ 3328:− 3309:∈ 3284:∏ 3256:μ 3248:∣ 3241:∑ 3181:≤ 3175:≤ 3170:− 3113:− 3074:λ 3045:− 3036:λ 3003:λ 2970:μ 2745:μ 2728:∣ 2721:∑ 2693:μ 2676:∣ 2669:∑ 2507:∈ 2482:≤ 2245:− 2157:− 2135:− 2113:− 1930:≡ 1918:≤ 1911:∑ 1771:μ 1754:∣ 1747:∑ 1677:⋯ 1651:− 1582:− 1536:− 1513:− 1309:and adds 1042:… 931:∈ 876:∈ 843:∈ 827:… 785:⋯ 755:∈ 641:⊆ 499:≤ 492:∑ 403:∈ 396:∏ 335:⊆ 299:≤ 176:countable 145:norwegian 139:The term 132:than the 67:July 2009 4548:Category 4408:(2014). 4301:(1976), 4268:(2010), 4230:(1974). 4188:(2007). 4087:(2006), 4062:and the 3847:and the 3798:and the 3726:for the 951:and let 4438:3171761 4399:1342300 4368:3272929 4325:0404173 4292:2647984 4254:0424730 4208:2331072 4179:1836967 4141:0735437 4111:2200366 2440:density 1980:Example 725:define 660:to the 658:coprime 55:improve 4518:  4436:  4397:  4387:  4366:  4323:  4313:  4290:  4280:  4252:  4242:  4214:  4206:  4196:  4177:  4167:  4139:  4129:  4109:  4099:  3794:, the 3790:, the 3786:, the 3782:, the 3209:Since 2893:bounds 2409:where 153:french 125:per se 4346:arXiv 3999:Zhang 2438:is a 141:sieve 40:, or 4516:ISBN 4385:ISBN 4311:ISBN 4278:ISBN 4240:ISBN 4194:ISBN 4165:ISBN 4127:ISBN 4097:ISBN 3949:The 3854:The 3750:and 3127:and 3062:and 2960:Brun 2935:and 2895:for 2583:and 2527:and 2497:< 2010:and 1984:Let 1487:sift 1446:and 1346:and 1215:and 1158:and 1073:sift 741:sift 701:For 636:sift 419:< 4508:doi 4424:doi 4420:179 4356:doi 4342:181 4212:Zbl 4157:doi 4051:). 4039:or 3730:of 1941:mod 664:of 509:gcd 4550:: 4514:. 4489:34 4487:. 4462:, 4456:, 4434:MR 4432:. 4418:. 4412:. 4395:MR 4393:, 4364:MR 4362:. 4354:. 4340:. 4321:MR 4319:, 4309:, 4288:MR 4286:, 4276:, 4264:; 4250:MR 4248:. 4238:. 4226:; 4210:. 4204:MR 4202:. 4175:MR 4173:, 4163:, 4155:, 4137:MR 4135:, 4125:, 4107:MR 4105:, 4095:, 4083:; 3770:. 2955:. 2253:30 2231:15 2209:10 1664:30 1641:15 1618:10 1401:30 1364:15 1327:10 1039:13 1033:11 1003::= 746::= 693:. 439:. 44:, 36:, 4538:) 4534:( 4524:. 4510:: 4491:. 4440:. 4426:: 4370:. 4358:: 4348:: 4256:. 4218:. 4159:: 3995:. 3981:4 3977:b 3973:+ 3968:2 3964:a 3932:2 3928:/ 3924:1 3920:N 3873:N 3862:N 3829:p 3825:p 3758:b 3738:a 3714:) 3711:b 3708:, 3705:a 3702:( 3681:P 3660:) 3657:x 3654:( 3649:d 3645:A 3624:) 3621:x 3618:( 3613:d 3609:A 3587:| 3583:) 3580:x 3577:( 3572:d 3568:A 3563:| 3542:) 3539:x 3536:( 3531:d 3527:A 3506:) 3501:n 3497:a 3493:( 3490:= 3485:A 3463:} 3460:x 3454:s 3451:: 3448:s 3445:{ 3442:= 3437:A 3415:A 3393:A 3365:. 3361:N 3354:n 3346:, 3343:) 3340:) 3337:p 3334:( 3331:g 3325:1 3322:( 3313:P 3306:p 3302:; 3299:n 3295:| 3291:p 3280:= 3277:) 3274:d 3271:( 3268:g 3265:) 3262:d 3259:( 3251:n 3245:d 3217:g 3194:. 3189:+ 3185:S 3178:S 3166:S 3140:+ 3136:S 3109:S 3088:) 3083:+ 3078:d 3070:( 3050:) 3040:d 3032:( 3012:) 3007:d 2999:( 2979:) 2976:d 2973:( 2943:R 2923:G 2903:S 2876:. 2873:) 2870:z 2867:, 2864:x 2861:( 2858:R 2855:+ 2852:) 2849:z 2846:, 2843:x 2840:( 2837:G 2834:X 2831:= 2828:) 2825:z 2822:, 2817:P 2812:, 2807:A 2802:( 2799:S 2773:) 2770:x 2767:( 2762:d 2758:r 2754:) 2751:d 2748:( 2740:) 2737:z 2734:( 2731:P 2725:d 2717:+ 2714:) 2711:d 2708:( 2705:g 2702:) 2699:d 2696:( 2688:) 2685:z 2682:( 2679:P 2673:d 2665:X 2662:= 2659:) 2656:z 2653:, 2648:P 2643:, 2638:A 2633:( 2630:S 2607:) 2604:x 2601:( 2596:d 2592:r 2571:) 2568:x 2565:( 2560:1 2556:A 2535:X 2511:P 2504:p 2500:1 2494:) 2491:p 2488:( 2485:g 2479:0 2475:, 2472:1 2469:= 2466:) 2463:1 2460:( 2457:g 2426:) 2423:d 2420:( 2417:g 2394:) 2391:x 2388:( 2383:d 2379:r 2375:+ 2372:X 2369:) 2366:d 2363:( 2360:g 2357:= 2354:) 2351:x 2348:( 2343:d 2339:A 2315:) 2312:x 2309:( 2304:d 2300:A 2267:. 2264:) 2261:x 2258:( 2249:A 2242:) 2239:x 2236:( 2227:A 2223:+ 2220:) 2217:x 2214:( 2205:A 2201:+ 2198:) 2195:x 2192:( 2187:6 2183:A 2179:+ 2176:) 2173:x 2170:( 2165:5 2161:A 2154:) 2151:x 2148:( 2143:3 2139:A 2132:) 2129:x 2126:( 2121:2 2117:A 2110:) 2107:x 2104:( 2099:1 2095:A 2091:= 2084:) 2081:7 2078:, 2074:P 2070:, 2065:A 2060:( 2057:S 2029:P 2025:= 2020:P 1998:7 1995:= 1992:z 1964:. 1959:n 1955:a 1948:) 1945:d 1938:( 1933:0 1927:n 1924:, 1921:x 1915:n 1907:= 1904:) 1901:x 1898:( 1893:d 1889:A 1864:P 1842:) 1839:x 1836:( 1831:d 1827:A 1799:) 1796:x 1793:( 1788:d 1784:A 1780:) 1777:d 1774:( 1766:) 1763:z 1760:( 1757:P 1751:d 1743:= 1740:) 1737:z 1734:, 1729:P 1724:, 1719:A 1714:( 1711:S 1674:+ 1670:| 1660:E 1655:| 1647:| 1637:E 1632:| 1628:+ 1624:| 1614:E 1609:| 1605:+ 1601:| 1595:5 1591:E 1586:| 1578:| 1572:6 1568:E 1563:| 1559:+ 1555:| 1549:3 1545:E 1540:| 1532:| 1526:2 1522:E 1517:| 1509:| 1505:A 1501:| 1497:= 1493:| 1483:A 1478:| 1454:5 1434:3 1431:, 1428:2 1407:| 1397:E 1392:| 1370:| 1360:E 1355:| 1333:| 1323:E 1318:| 1296:| 1290:5 1286:E 1281:| 1259:| 1253:6 1249:E 1244:| 1223:3 1203:2 1182:| 1176:3 1172:E 1167:| 1145:| 1139:2 1135:E 1130:| 1108:| 1104:A 1100:| 1069:A 1045:} 1036:, 1030:, 1027:7 1024:, 1021:5 1018:, 1015:3 1012:, 1009:2 1006:{ 998:P 975:| 969:p 965:E 960:| 939:} 935:N 928:n 925:: 922:n 919:p 916:{ 913:= 908:p 904:E 881:P 873:p 848:P 838:k 834:p 830:, 824:, 819:1 815:p 810:, 807:} 804:1 801:= 798:) 793:k 789:p 780:1 776:p 772:, 769:a 766:( 762:| 758:A 752:a 749:{ 737:A 711:P 681:) 678:z 675:( 672:P 644:A 632:A 607:) 604:n 601:( 596:A 592:1 588:= 583:n 579:a 555:. 550:n 546:a 540:1 537:= 534:) 531:) 528:z 525:( 522:P 519:, 516:n 513:( 505:, 502:x 496:n 488:= 485:) 482:z 479:, 474:P 469:, 464:A 459:( 456:S 427:p 422:z 416:p 413:, 408:P 400:p 392:= 389:) 386:z 383:( 380:P 360:z 339:P 330:P 305:} 302:x 296:s 293:: 290:s 287:{ 284:= 281:A 261:) 258:n 255:( 250:A 246:1 242:= 237:n 233:a 209:) 204:n 200:a 196:( 193:= 188:A 106:X 80:) 74:( 69:) 65:( 51:.

Index

list of references
related reading
external links
inline citations
improve
introducing
Learn how and when to remove this message
number theory
prime numbers
sieve of Eratosthenes
Legendre sieve
almost prime
weight functions
characteristic function
norwegian
Viggo Brun
french
Jean Merlin
World War I
countable
indicator function
cardinality
coprime
prime factors
inclusion–exclusion principle
Möbius function
multiplicative function
bounds
Brun
greatest common divisor

Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.

↑