Решето Сундарама

Решето Сундара́ма — детерминированный алгоритм нахождения всех простых чисел до некоторого целого числа . Разработан индийским студентом Сундарамом в 1934 году.

Пошаговая демонстрация работы алгоритма для

Алгоритм предусматривает исключение из ряда натуральных чисел от 1 до всех чисел вида:

,

где индексы пробегают все натуральные значения, для которых , а именно значения и Затем каждое из оставшихся чисел умножается на 2 и увеличивается на 1. Полученная в результате последовательность представляет собой все простые числа в отрезке .

Обоснование

Алгоритм работает с нечётными натуральными числами большими единицы, представленными в виде , где является натуральным числом.

Если число является составным, то по определению оно может быть представлено в виде произведения двух нечётных чисел, больших единицы, то есть:

, где и  — натуральные числа. Раскрывая скобки, получаем, что
, или
, из чего следует, что
.

Таким образом, если из ряда натуральных чисел исключить все числа вида (), то для каждого из оставшихся чисел число обязано быть простым. И, наоборот, если число является простым, то число невозможно представить в виде и, таким образом, не будет исключено в процессе работы алгоритма.

См. также

Ссылки

  • Б. А. Кордемский. Математическая смекалка. — М.: ГИФМЛ, 1958.
  • Baxter, Andrew. «Sundaram’s Sieve». Topics from the History of Cryptography. MU Department of Mathematics.

Read other articles:

Menara TV Saint Petersburg Menara TV Saint Petersburg merupakan nama menara yang terletak di St. Petersburg, Rusia. Menara ini merupakan menara khusus televisi pertama yang dibangun di Uni Soviet, dan digunakan untuk menyiarkan gelombang FM / siaran televisi ke seluruh kota di negara Rusia.[1][2][3] Menara ini memiliki panjang 310 m. Letak menara ini di 3 Ulitsa Akademika Pavlova. Sejarah Pembangunan Menara TV Saint Petersburg ini dimulai pada tahun 1962. Saat selesai ...

 

Artikel ini tidak memiliki referensi atau sumber tepercaya sehingga isinya tidak bisa dipastikan. Tolong bantu perbaiki artikel ini dengan menambahkan referensi yang layak. Tulisan tanpa sumber dapat dipertanyakan dan dihapus sewaktu-waktu.Cari sumber: SMA Negeri 34 Jakarta – berita · surat kabar · buku · cendekiawan · JSTOR SMA Negeri 34 JakartaInformasiDidirikan13 September 1978JenisNegeriAkreditasiANomor Statistik Sekolah301016307051Nomor Pokok Seko...

 

Artikel ini menggunakan kata-kata yang berlebihan dan hiperbolis tanpa memberikan informasi yang jelas. Silakan buang istilah-istilah yang hiperbolis tersebut. (Pelajari cara dan kapan saatnya untuk menghapus pesan templat ini) Bukit Fraser (Inggris: Fraser's Hillcode: en is deprecated ) adalah resor bukit yang terletak di Punggung Bukit Titiwangsa di Negara Bagian Pahang, Malaysia. Bukit Fraser mendapatkan namanya dari James Louis Fraser, seorang petualang kolonial dan pemburu hebat asal Bri...

هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (يونيو 2019) نورجموغين تسيدينبال معلومات شخصية الميلاد 12 سبتمبر 1988 (العمر 35 سنة)[1]منغوليا  الطول 1.78 م (5 قدم 10 بوصة) مركز اللعب مدافع الجنسية منغوليا  معلو...

 

Gadis yang memakai celana jins pendek Celana pendek adalah bagian bawah pakaian bercabang dua yang umumnya digunakan perempuan dengan panjang di atas lutut.[1] Celana pendek dipakai di bagian pinggul, mengitari pinggang, dan menutupi kaki bagian atas.[2] Biasanya, ukuran celana lebih panjang sampai ke bawah lutut, tetapi celana pendek tidak menutupi seluruh panjang kaki, baik sebagai pakaian luar atau pun dalam. Hal ini membuat celana pendek nyaman dan mudah dipakai. Dinamakan...

 

Lawrence Lessig tahun 2015, seorang aktivis gerakan budaya bebas. Gerakan budaya bebas adalah gerakan sosial yang menggalakkan kebebasan untuk mendistribusikan dan memodifikasi karya kreatif orang lain dalam bentuk konten bebas[1] atau konten terbuka[2][3] tanpa adanya kompensasi atau persetujuan dari pencipta asli karya tersebut, dengan memberdayakan Internet dan bentuk media lainnya. Gerakan tersebut menolak sesuatu yang dianggap terlalu membatasi dalam undang-undang...

City in Grand Est, France For other uses, see Colmar (disambiguation). Prefecture and commune in Grand Est, FranceColmar Colmer (Alsatian)Kolmar (German)Prefecture and communeColmar's Little Venice FlagCoat of armsLocation of Colmar ColmarShow map of FranceColmarShow map of Grand EstCoordinates: 48°04′54″N 7°21′20″E / 48.0817°N 7.3556°E / 48.0817; 7.3556CountryFranceRegionGrand EstDepartmentHaut-RhinArrondissementColmar-RibeauvilléCantonColmar-1 and 2...

 

Cet article est une ébauche concernant une localité italienne et le Trentin-Haut-Adige. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Ronchi Valsugana Administration Pays Italie Région Trentin-Haut-Adige  Province Trentin   Code postal 38051 Code ISTAT 022157 Code cadastral H532 Préfixe tel. 0461 Démographie Population 450 hab. (1er janvier 2023[1]) Densité 45 hab./km2 Géographie Coo...

 

Berglund CenterBerglund CenterLocation within VirginiaShow map of VirginiaBerglund CenterLocation within the United StatesShow map of the United StatesFormer namesRoanoke Civic Center (1971–2014)Location710 Williamson Road NortheastRoanoke, VA 24016OwnerCity of RoanokeOperatorCity of RoanokeCapacityBasketball: 8,614Ice hockey: 8,672End stage: 10,500Center stage: 10,600Eclipse: 4,276Performing Arts Center: 2,151SurfaceMulti-surfaceConstructionBroke ground1969OpenedOctober 3, 1971Renovated200...

1967 American film See also: Flying Fickle Finger of Fate Award in Rowan & Martin's Laugh-in This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: The Fickle Finger of Fate – news · newspapers · books · scholar · JSTOR (February 2024) (Learn how and when to remove this message) The Fickle Finger of FateDVD cov...

 

Флаг гордости бисексуалов Бисексуальность      Сексуальные ориентации Бисексуальность Пансексуальность Полисексуальность Моносексуальность Сексуальные идентичности Би-любопытство Гетерогибкость и гомогибкость Сексуальная текучесть Исследования Шк...

 

Kejatuhan KabulBagian dari serangan Taliban 2021 dalam perang di AfganistanOrang-orang mencoba memasuki Bandar Udara Internasional Kabul yang dihentikan oleh militan Taliban.Tanggal15 Agustus 2021LokasiKabul, AfganistanStatus Taliban merebut Kabul; pembicaraan sedang berlangsung untuk peralihan kekuasaan secara damai Presiden Ashraf Ghani terbang ke Tajikistan[1][2] Taliban mengklaim mereka akan segera mendeklarasikan Keamiran Islam Afganistan[3] Menteri Pertahanan Bis...

Cycling race 2014 Tour de France2014 UCI World Tour, race 18 of 29Route of the 2014 Tour de FranceRace detailsDates5–27 July 2014Stages21Distance3,660.5[a] km (2,275 mi)Winning time89h 59' 06Results Winner  Vincenzo Nibali (ITA) (Astana)  Second  Jean-Christophe Péraud (FRA) (Ag2r–La Mondiale)  Third  Thibaut Pinot (FRA) (FDJ.fr) Points  Peter Sagan (SVK) (Cannondale) Mountains  Rafał Majka (POL) (Tinkoff–S...

 

Town in Hunan, People's Republic of ChinaLingyang Town 零阳镇TownLingyang TownLocation in HunanCoordinates: 29°25′21″N 111°07′19″E / 29.42250°N 111.12194°E / 29.42250; 111.12194CountryPeople's Republic of ChinaProvinceHunanPrefecture-level cityZhangjiajieCountyCiliArea • Total316 km2 (122 sq mi)Population130,000Time zoneUTC+8 (China Standard)Area code0744 Lingyang Town (simplified Chinese: 零阳镇; traditional Chinese:...

 

Future Primitive: The New Ecotopias First editionEditorKim Stanley RobinsonCover artistCarol RussoLanguageEnglishPublished1994 (Tor Books)Publication placeUnited StatesMedia typeHardcoverPages352ISBN978-0-312-85474-4 Future Primitive: The New Ecotopias is a 1994 collection of short stories edited by Kim Stanley Robinson. It republishes notable short works of utopian and dystopian fiction that incorporate elements of primitivism and of eco-anarchism. Contents An introduction by Robin...

Traprock mountain in the American state of Connecticut Higby MountainLedges of Higby MountainHighest pointElevationest. 892 ft (272 m) (ridge high point)Coordinates41°34′02″N 72°43′28″W / 41.56722°N 72.72444°W / 41.56722; -72.72444 to41°31′49″N 72°44′37″W / 41.53028°N 72.74361°W / 41.53028; -72.74361GeographyLocationMiddletown, Meriden, and MiddlefieldParent rangeMetacomet RidgeGeologyAge of rock200 MaMount...

 

Main article: Military awards and decorations of Sri Lanka This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (February 2023) (Learn how and when to remove this message) AwardVadamarachchi Operation MedalMedal, obverseTypeCampaign medalAwarded forActive involvement in the Vadamarachchi Operation[1]DescriptionSuspended from a plain suspension barPresented ...

 

Marl-Chemiepark Power Station is an ensemble of three thermal power stations. One of these power stations has a 300 meters tall, another a 241 meters tall chimney. The 300 meters chimney was demolished in 1995, using a special excavator. External links Germany portalEnergy portal abbruchtechnik.de vteIndustrial Heritage Trail (Ruhr) – Visitor Centres, Anchor Points, Theme RoutesVisitor centres andanchor points German Inland Waterways Museum Duisburg Inner Harbour Oberhausen Industrial Muse...

State highway in northern New Jersey, US Route 21Route informationMaintained by NJDOTLength14.3 mi[1] (23.0 km)Existed1927–presentMajor junctionsSouth end I-78 / US 1-9 / US 22 in NewarkMajor intersections Route 27 in Newark I-280 in Newark Route 7 / CR 506 in Belleville Route 3 in Clifton North end US 46 / Route 20 in Clifton LocationCountryUnited StatesStateNew JerseyCountiesEssex, Passaic Highway syst...

 

Nel seguente testo sull'argomento ingegneria è presente una sospetta violazione di copyright. Motivo: Voce creata da utente infinitato a causa di ripetute violazioni di copyright È sconsigliato wikificare o ampliare il testo attuale, che potrebbe essere cancellato. Puoi invece riformulare il testo con parole tue o partecipare alla discussione. Segui i suggerimenti del progetto di riferimento.Avvisa l'autore: {{Avvisocontrolcopy|voce=Materiali rinforzati con fibre a matrice polimerica}...