Crivo de Eratóstenes

O Crivo de Eratóstenes é um algoritmo e um método simples e prático para encontrar números primos até um certo valor limite. Segundo a tradição, foi criado pelo matemático grego Eratóstenes[1] ((circa?) 275-194 a.C.),[2][3] o terceiro bibliotecário-chefe da Biblioteca de Alexandria desde 247.[4]

Explicação do algoritmo

Para exemplificá-lo, vamos determinar a lista de números entre 1 e 30.

  • Inicialmente, determina-se o maior número a ser verificado. Ele corresponde à raiz quadrada do valor limite, arredondado para baixo. No caso, a raiz de 30, arredondada para baixo, é 5.
  • Crie uma lista de todos os números inteiros de 2 até o valor limite, neste caso 30.
  • Encontre o primeiro número da lista. Ele é um número primo, 2.
  • Remova da lista todos os múltiplos de 2 (exceto ele próprio) até o valor limite. No nosso exemplo, a lista contem 2 e os números ímpares até 29.
  • O próximo número da lista após o primo anterior é primo. Repita o procedimento. No caso, o próximo número da lista é 3. Removendo seus múltiplos, a lista fica: 2, 3, 5, 7, 11, 13, 17, 19, 23, 25 e 29. O próximo número, 5, também é primo; a lista fica: 2, 3, 5, 7, 11, 13, 17, 19, 23 e 29. 5 é o último número a ser verificado, conforme determinado inicialmente. Assim, a lista encontrada contém somente números primos.[1][5]

Visualização do Crivo

Animação do crivo

Utilização em linguagens de programação

A simplicidade do código faz com que este seja usado como benchmark para comparar compiladores e chips.[5] Uma das versões mais populares deste benchmark foi publicada na Revista Byte, no início dos anos 1980.[6][7]

Ver também

Referências

  1. ↑ a b Paul Hoffman, The Man Who Loved Only Numbers: The Story of Paul Erdős and the Search for Mathematical Truth, (New York: Hyperion), 1998, p. 35. ISBN 0-7868-6362-5
  2. ↑ Morris Klein, Mathematics for The Nonmathematician, Dover Publications, New York, 1967, p. 136:
    "Eratosthenes (275—194 B.C.)"
  3. ↑ The New Century Classical Handbook; Catherine Avery, redator; Appleton-Century-Crofts, New York, 1962, p. 447:
    "Eratosthenes... born... c275 B.C.; died c194 B.C."
  4. ↑ The New Century Classical Handbook; Catherine Avery, redator; Appleton-Century-Crofts, New York, 1962, p. 447:
    "Eratosthenes... the chief librarian (the third to hold the position) of the great Library at Alexandria (247 B.C.)"
    (""Eratóstenes... o bibliotecário-chefe (o terceiro a ocupar o cargo) da grande Biblioteca de Alexandria (247 a.C.)")
  5. ↑ a b Sieve of Eratosthenes - Benchmarks, site www.keil.com
  6. ↑ The Sieve, Factoring and Primes, site home.hccnet.nl
  7. ↑ Código fonte do programa sieve.c, site www.cs.nthu.edu.tw

Read other articles:

Farhad Ghaemi

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada November 2022. Farhad GhaemiGhaemi pada Olimpiade 2016Informasi pribadiNama lengkapFarhad GhaemiLahir28 Agustus 1989 (umur 34)Gonbad-e Kavus, IranTinggi197 m (646 ft 4 in)[1]Berat73 kg (161 pon)Spike3.55 cmBlok3.15 cmInform...

 

Provinsi Semnan

Letak Provinsi Semnān di Iran Provinsi Semnān (Persia: استان سمنان) merupakan satu dari 30 provinsi di Iran. Provinsi ini terletak di bagian tengah di negara itu. Ibu kotanya ialah Semnan. Provinsi ini memiliki luas wilayah 97.491 km² dengan memiliki jumlah penduduk 589.512 jiwa (2005). Pembagian Administrasi Peta Shahrestan Singkatan Peta Bakhsh Pusat Damghan D Central Damghan a Amir Abad Garmsar G Central Garmsar a Aradan e Eyvanakey Semnan S Central Semnan m Mehdishahr s ...

 

Brutal (seri web)

BrutalGenre Drama Laga SkenarioLintang Pramudya WardhaniCeritaLintang Pramudya WardhaniSutradaraArie AzisSutradara lagaDevris BrigelPemeran Zoe Jackson Rezky Aditya Kevin Kambey Siva Aprilia Zack Lee Lagu pembukaJika Kita Bersama oleh Superman Is DeadLagu penutupJika Kita Bersama oleh Superman Is DeadPenata musikBella MaritzaNegara asalIndonesiaBahasa asliBahasa IndonesiaJmlh. musim1Jmlh. episode12ProduksiProduser eksekutif Sutanto Hartono Hermawan Sutanto Tina Arwin SinematografiZeta ...

Orchestre philharmonique de Vienne

(de) Wiener Philharmoniker Orchestre philharmonique de Vienne Logo de l'Orchestre philharmonique de Vienne. Le Musikverein, résidence de l'Orchestre philharmonique de Vienne. Pays de résidence Autriche Ville de résidence Vienne Lieux d'activité Musikverein Années d'activité Depuis 1842 Type de formation Orchestre symphonique Genre Musique symphonique Style Classique Direction Daniel Froschauer Fondateur Otto Nicolai Création 1842 Site web (en + de + ja) wienerphilh...

 

Franco Caccia

Franco Caccia Caccia alla Ternana nella stagione 1976-1977 Nazionalità  Italia Altezza 178 cm Peso 70 kg Calcio Ruolo Centrocampista Termine carriera 1986 Carriera Giovanili 196?-1971 Atalanta Squadre di club1 1971-1972 Pergolettese33 (7)1972-1976 Anconitana113 (26)1976-1979 Ternana83 (6)1979-1980 Sampdoria21 (1)1980-1983 Sambenedettese98 (11)1983-1986 Messina92 (9) 1 I due numeri indicano le presenze e le reti segnate, per le sole partite di campiona...

 

Pembakaran buku di Efesus

Eustache Le Sueur - Kotbah Santo Paulus di Efesus, 1649. Lukisan tersebut menggambarkan buku-buku dengan angka-angka geometri, merujuk kepada Galileo Galilei, yang dikatakan pada 1623 bahwa buku alam ditulis dalam angka-angka matematika.[1] Pembakaran buku di Efesus adalah sebuah peristiwa yang tercatat dalam Kisah Para Rasul 19 dimana para petobat Kristen di Efesus, yang dipengaruhi oleh Santo Paulus, membakar buku-buku sihir mereka. Kis 19 menyatakan Banyak juga di antara mereka, ya...

Emma Hwang

Scientist with Wyle Laboratories and aquanaut on NEEMO 5 Emma HwangBornYu-liang Hwang (1970-07-21) July 21, 1970 (age 53)TaiwanEducationB.A., Biomedical Engineering, Boston University; M.S., Biomedical Engineering, M.S., Electrical Engineering Systems, University of Michigan; Ph.D., Biomedical Engineering, University of MichiganOccupationScientistEmployerWyle LaboratoriesKnown forAquanaut Emma Y. Hwang (born Yu-liang Hwang on July 21, 1970) is a scientist with Wyle Laboratories.[...

 

Steinmaur

Cet article est une ébauche concernant une localité suisse. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Steinmaur Armoiries Administration Pays Suisse Canton Zurich District Dielsdorf Maire M. Andres Binder NPA 8162 No OFS 0101 Démographie Populationpermanente 3 613 hab. (31 décembre 2022) Densité 384 hab./km2 Langue Allemand Géographie Coordonnées 47° 29′ 40″ n...

 

Karim Hafez

Egyptian footballer (born 1996) Karim Hafez Hafez with RC Lens in 2017Personal informationFull name Karim Hafez Ramadan Seifeldin[1]Date of birth (1996-03-12) 12 March 1996 (age 28)[2]Place of birth Beheira, EgyptHeight 1.75 m (5 ft 9 in)[2]Position(s) Left backTeam informationCurrent team PyramidsNumber 29Senior career*Years Team Apps (Gls)2014–2018 Lierse 23 (2)2015–2016 → Omonia (loan) 29 (0)2016–2017 → Lens (loan) 23 (0)2017–2018 �...

Mercedes-AMG R232

Artikel ini memiliki beberapa masalah. Tolong bantu memperbaikinya atau diskusikan masalah-masalah ini di halaman pembicaraannya. (Pelajari bagaimana dan kapan saat yang tepat untuk menghapus templat pesan ini) Artikel ini berisi konten yang ditulis dengan gaya sebuah iklan. Bantulah memperbaiki artikel ini dengan menghapus konten yang dianggap sebagai spam dan pranala luar yang tidak sesuai, dan tambahkan konten ensiklopedis yang ditulis dari sudut pandang netral dan sesuai dengan kebijakan ...

 

Flag of Greece

National flag Hellenic RepublicOther namesΗ Γαλανόλευκη (I Galanolefki, 'The Blue and White'), Η Κυανόλευκη (I Kyanolefki, 'The Azure and White')UseNational flag and ensign Proportion2:3 (and also 7:12)Adopted22 December 1978; 45 years ago (1978-12-22) (Naval Ensign 1822–present, National Flag 1969–70; 1978–present)DesignNine horizontal stripes, in turn blue and white; a white Greek cross throughout a blue canton. The national flag of Greece, pop...

 

List of Spanish words of Celtic origin

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: List of Spanish words of Celtic origin – news · newspapers · books · scholar · JSTOR (January 2024) (Learn how and when to remove this message) This is a list of Spanish words of Celtic origin. It is further divided into words that are known (or thought) to ha...

Turner Layton

American singer-songwriter and pianist (1894–1978) Turner LaytonTurner Layton (left) and his musical partner Clarence Johnstone in 1933Background informationBirth nameJohn Turner Layton, Jr.Born(1894-07-02)2 July 1894Washington, D.C., United StatesDied6 February 1978(1978-02-06) (aged 83)London, EnglandGenresJazz, vocalOccupation(s)SingerYears active1918–1946Musical artist Sheet music cover for a patriotic Creamer & Layton song, 1918 Turner Layton (July 2, 1894 – February 6, 19...

 

2023 Hawthorn Football Club season

Hawthorn Football Club2023 seasonPresidentJeff Kennett (until 13 December 2022)Andrew Gowers (from 13 December 2022)CoachSam MitchellCaptain(s)James SicilyHome groundMelbourne Cricket Ground University of Tasmania StadiumRecord7–16 (16th)Best and FairestWill DayLeading goalkickerLuke Breust (47) ← 2022 2024 → The 2023 Hawthorn Football Club season was the club's 99th season in the Australian Football League and 122nd overall, the 24th season playing home games at the Melbourne ...

 

At the Point

The topic of this article may not meet Wikipedia's notability guideline for music. Please help to demonstrate the notability of the topic by citing reliable secondary sources that are independent of the topic and provide significant coverage of it beyond a mere trivial mention. If notability cannot be shown, the article is likely to be merged, redirected, or deleted.Find sources: At the Point – news · newspapers · books · scholar · JSTOR (May 2024) (Le...

Constituencies of the Parliament of the United Kingdom

Electoral divisions of the parliament of the United Kingdom United Kingdom parliamentary constituenciesConstituencies after the 2023 Periodic ReviewCategoryElectoral districtLocationUnited KingdomNumber650 (as of 2023)GovernmentHouse of Commons This article is part of a series onPolitics of the United Kingdom Constitution Magna Carta Bill of Rights Treaty of Union (Acts of Union) Parliamentary sovereignty Rule of law Separation of powers Other constitutional principles The Crown The Monarch (...

 

Stasiun Shimo-Shibetsu

Stasiun Shimo-Shibetsu (下士別駅 Shimo-Shibetsu-eki) adalah sebuah stasiun kereta api yang berada di Jalur Utama Sōya terletak di Shimo-Shibetsu, Shibetsu, Subprefektur Kamikawa, Hokkaido, Jepang, yang dioperasikan oleh JR Hokkaido. Stasiun ini diberi nomor W43. Stasiun Shimo-Shibetsu下士別駅Bangunan Stasiun Shimo-ShibetsuLokasiShimo-Shibetsucho, Shibetsu, Prefektur Hokkaido 098-0475JepangKoordinat44°12′38.2″N 142°23′46.8″E / 44.210611°N 142.396333°E࿯...

 

Rempart gallo-romain de Toulouse

Rempart gallo-romain de ToulouseCourtine et tour du rempart gallo-romain.PrésentationType Gallo-romainStyle Haut-EmpireConstruction Ier siècle et IVe sièclePropriétaire ÉtatPatrimonialité Classé MH (2022) Inscrit MH (1990)LocalisationDépartement Haute-GaronneCommune ToulouseCoordonnées 43° 35′ 53″ N, 1° 27′ 05″ ELocalisation sur la carte de FranceLocalisation sur la carte de Toulousemodifier - modifier le code - modifier Wik...

جائزة ستيريا الكبرى 2020

يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (نوفمبر 2020) جائزة ستيريا الكبرى 2020 (بالألمانية: Formula 1 Pirelli Großer Preis der Steiermark 2020)‏  السباق 2 من أصل 17 في بطولة العالم ...

 

Museo Pambata

Children's museum in Manila, PhilippinesMuseo PambataThe Museo Pambata, in the 1911 Manila Elks Club bldg.Established1993LocationErmita, Manila, PhilippinesCoordinates14°34′45″N 120°58′38″E / 14.57907°N 120.97711°E / 14.57907; 120.97711TypeChildren's museum Sign for the Museo Pambata children's museum, on Roxas Boulevard, Manila The Museo Pambata (lit. 'Museum for Children') or the Children's Museum, is a children's museum in the Ermita district of M...