Crivo de Eratóstenes

Encontrar números primos é um problema comum em olimpíadas e maratonas de programação. Até hoje não existe uma maneira fácil de determinar se um número é ou não primo, mas para resolver estes problemas é indispensável o conhecimento de alguns algoritmos clássicos e simples, como o Crivo de Eratóstenes.

O Crivo de Eratóstenes é um método bastante prático para encontrar os primos de 2 até um valor limite, que pode ser feito a mão e é fácil de implementar.

O algoritmo consiste em:

  1. Determinar (ou receber na entrada do programa) o valor limite, isto é, o maior número que desejamos saber se é primo.
  2. Fazer a raiz quadrada do valor limite. Pode-se arredondar para baixo caso a raiz não seja exata (e quase nunca é).
  3. Criar um vetor (lista) com os números de 2 até o valor limite.
  4. Para i=2 até raiz do valor limite, caso o número (i) não esteja riscado insira-o na lista dos primos (ou imprima-o, ou não faça nada, isso depende da utilidade que você quer dar para o crivo) e risque todos os seus múltiplos na lista.

Há várias maneiras de implementar este algoritmo. Eu pseudocodaria (meu pseudocódigo é bem próximo de uma linguagem normal, porque acho que assim é mais fácil de entender e depois implementar) ele assim:

/* Primeiro passo */
recebe valorLimite

/* Segundo passo */
raiz [tex]\leftarrow[/tex] [tex]\sqrt{valorLimite}[/tex]

/* Terceiro passo */
para i [tex]\leftarrow[/tex] 2 até valorLimite
    vetor[i] [tex]\leftarrow[/tex] i

/* Quarto passo */
para i [tex]\leftarrow[/tex] 2 até raiz
    se vetor[i] = i
        imprima "O número " i " é primo."
        para j [tex]\leftarrow[/tex] i+i até valorLimite, de i e i
            vetor[j] [tex]\leftarrow[/tex] 0

Vêem como é simples?

Crivo de Eratóstenes implementado em C

// necessário para raiz

#define NMAX 1000000 // valor máximo para o valor máximo

int main() {
int i, j, vetor[NMAX];
int valorMaximo, raiz;

// Primeiro passo
scanf("%d", &valorMaximo);

// Segundo passo

// Terceiro passo
for (i=2; i<=valorMaximo; i++) {

// Quarto passo
for (i=2; i<=raiz; i++) {
if (vetor[i]==i) {
printf("%d é primo!\n", i);
for (j=i+i; j<=valorMaximo; j+=i) {
vetor[j]=0; // removendo da lista

return 0;

No USACO Training Program Gateway (programa de treinamento para olimpíadas dos estado-unidenses) há um problema muito interessante (Prime Palindromes) cujo objetivo é determinar palíndromos primos de X a Y. Uma das melhores situações que já encontrei para usar o Crivo e sem dúvidas é um ótimo treinamento. Além de determinar primos, você terá que determinar palíndromos e é outro ótimo exercício lógico-matemático.

Divirtam-se e qualquer dúvida usem os comentários!

1,146 thoughts on “Crivo de Eratóstenes

  1. I simply wanted to construct a simple remark in order to appreciate you for those great items you are giving at this site. My time intensive internet search has finally been paid with extremely good strategies to exchange with my family. I would admit that many of us site visitors are quite fortunate to dwell in a very good site with many outstanding individuals with very beneficial solutions. I feel somewhat fortunate to have encountered your weblog and look forward to tons of more fabulous times reading here. Thanks once again for a lot of things.

  2. It is a pity, that now I can not express – it is very occupied. But I will be released – I will necessarily write that I think.

    [url=]cialis generic[/url]
    [url=]buy cialis[/url]

  3. You do not need a computer expert to run an online business, but you need to create a website, or the resources to pay someone to do it for you.Singaporean former President Tony Tan Keng Yam ended his sixyear term in office at the end of August.That and strong performances in iPad and Mac sales in the quarter lifted the company’s overall growth to 7 percent yearonyear. Information Products are always good sellers – most important to solve a particular problem. Stainless steel exhaust systems will give you great durability, and sport exhaust systems are available for true grease monkeys.
    Cheap Soccer Jerseys China

  4. Attorney’s office in Detroit started investigating into Flint water crisis in January this year, along with the Environmental Protection Agency. In addition, those who know much about fishing beginners can find a small company offering specialized products, sales, WalMart center. Central delegation visits residents in Inner MongoliaIn pics: China’s PLA Air Force Aviation Open DayInside ice cave in N China’s Ningwu36 killed, dozens injured in train crash in EgyptHighlights of multinational drill in GeorgiaPeople mark national Fitness Day around ChinaAerial view of Gula Town in S ChinaQiandao Lake: Home to 114 known fish species</Car manufacturers these days comply with the myths and expectations of mainstream customers who hold the notion that low velocity superquiet exhaust systems are ideal.鈥?How the procedure works 鈥?Online brochure printing is a simple process.As the country's first female president, Halimah Yacob assured all Singaporeans she would serve every one, regardless of race, language or religion.
    Cheap NFL Jerseys From China

  5. I enjoy you because of all of the work on this website. Ellie take interest in carrying out research and it’s easy to see why. Most of us learn all regarding the powerful means you convey simple tricks via your website and in addition encourage contribution from some others on this content and our favorite child has always been discovering a great deal. Take pleasure in the remaining portion of the year. You are doing a remarkable job.

  6. I and also my friends came following the good information found on your site and so instantly got an awful feeling I never expressed respect to the web blog owner for those techniques. Those men had been so very interested to study them and have now absolutely been loving those things. Many thanks for really being quite accommodating and for making a choice on variety of magnificent information millions of individuals are really eager to understand about. My very own honest regret for not expressing appreciation to you earlier.

  7. I'm excited about this; I just found your blog last night after downloading your "50 things" lists. Super fun idea! I've added your blog to my daily list of blogs to read and look forward to checking back often! Your simple things Sunday posts are inspiring…I'm going to do one as well! Thanks!

  8. I saw your advert in the paper How could you not notice the t shirt, the pink pig from Pooh on the table next to the bed was better. Anyways, totally hot, I give props to both of them. The guy for being able to fuck like that and not blow his load, and the girl for not screaming while he did it.

  9. haa! Patch loveste din nou! Eu nu am cartea si BFF-u' meu, da' mi-o trebuie si miee. In schimb am Crescendo (ai de capu' meu!) si inca asteptam Silence, volumul 3 :) Ma bucur ca ti-a placut…acum, daca iti zic ca Jace zici ca e geamanul pierdut al lui Patch, da mult mai auriu, te apuci si de IM? :D sunt curiassa ce vei crede :D

  10. Peripetii mai degraba neplacute am avut…de fiecare data aproape. Intr-un an, in Grecia, m-a muscat un peste (sau un arici de mare), altadata, tot acolo am facut insolatie si am ajuns la spital in perfuzii, in Spania a nins in mai cand noi eram la plaja, in Mamaia m-a prins controlorul fara bilet si m-a amenintat ca ma duce la politie… si lista poate continua.

  11. Thank you SO MUCH Charlotte! I believe the Lord must’ve prompted you to write this post because I SO needed it. I can’t tell you how encouraging it is to hear your recount of your weeks and your good words of wisdom. I lost 26″ the first 30 days, but 1/2″, 0″, etc since. And that’s with doing BWO+ everyday. I have SO far to go….but I will keep Tapping. Thank you. THANK YOU. You are such a blessing.

  12. I am also commenting to let you understand of the incredible experience my cousin’s child experienced using your blog. She noticed plenty of pieces, with the inclusion of what it’s like to have a wonderful coaching heart to make other people very easily fully understand chosen complex matters. You undoubtedly exceeded visitors’ expectations. I appreciate you for giving such productive, trustworthy, educational and fun guidance on the topic to Ethel.

  13. O problema é mesmo esse… É que a CGD se comprometeu a financiar na totalidade a obra (os 13 milhões de euros) que seriam "pagos" com o nome do pavilhão e patrocínios nas modalidades e agora diz que a troika nao permite! E agora temos que nós resolver o problema.

  14. I wanted to post you this little bit of word just to say thanks a lot once again just for the pretty methods you’ve discussed on this page. This is really particularly open-handed of you to grant freely just what a few people would’ve supplied as an e-book to earn some money for themselves, even more so now that you might have tried it in the event you considered necessary. Those inspiring ideas as well worked to be the easy way to recognize that many people have the same keenness like mine to understand good deal more with respect to this issue. I am sure there are thousands of more pleasant occasions ahead for people who see your website.

  15. Residents immediately complained about the water’s color and odor, and independent investigators discovered elevated lead levels in the water and blood of children.Finally Cristian Herrera’s second goal of the season looked to have put Elche on the way to a vital win at home to Sevilla with just 10 minutes remaining, but Daniel Carrico’s diving header two minutes from time assured a share of the points and maintains Sevilla’s unbeaten run away from home.”Apple’s financial results in the latest quarter showed that the company has become increasingly dependent on revenue from services, including digital content and services, Apple Pay and licensing. The score remains live on the official website for two years enabling students to apply for admission in reputed universities.He is constantly working on his Hunan accent, the provincial inflected Chinese of Mao’s home, and the leader’s particular style of calligraphy, still used for the masthead of the ruling party’s mouthpiece newspaper the People’s Daily.
    Cheap NFL Jerseys China Wholesale

  16. Hi, Neat post. There is a problem along with your website in web explorer, may test this? IE still is the market leader and a large section of folks will miss your great writing because of this problem.

  17. Usually it is best to scope out the first five websites you see for your brochure printing. However, many people want to build a product company to start without a barrier. Auto experts have been through twenty years of reining and upgrading this exhaust system. An iron exhaust manifold will yield great results when utilized with a Techtonics Tuned downpipe and sports exhaust system. A company that could be around for years is the wanted one.
    Cheap NFL Jerseys Wholesale

  18. I would like to show some appreciation to the writer just for rescuing me from this type of condition. After surfing throughout the online world and meeting proposals which were not helpful, I figured my life was done. Living devoid of the strategies to the difficulties you’ve resolved as a result of the short post is a serious case, as well as the kind that might have badly affected my entire career if I had not encountered your website. Your primary understanding and kindness in maneuvering every item was precious. I am not sure what I would’ve done if I had not come upon such a thing like this. I can also at this moment look ahead to my future. Thanks so much for the impressive and results-oriented help. I will not be reluctant to propose your web sites to any individual who desires direction on this issue.

  19. I simply wanted to thank you very much again. I am not sure the things I would have accomplished without the type of basics provided by you concerning this subject. It has been a very fearsome problem for me personally, nevertheless encountering your expert fashion you processed the issue took me to leap with happiness. Now i am thankful for your help and hope that you recognize what a powerful job you’re getting into instructing the rest using your websites. Most likely you’ve never met all of us.

  20. Thank you for every one of your hard work on this website. Debby delights in carrying out investigations and it’s really obvious why. All of us know all regarding the lively way you provide helpful tips and hints on the web site and in addition boost response from some other people about this article then my daughter is without question understanding a whole lot. Enjoy the remaining portion of the year. You’re conducting a first class job.

  21. I have to express appreciation to this writer just for bailing me out of such a circumstance. Just after looking out throughout the world wide web and seeing solutions which are not beneficial, I thought my entire life was over. Living devoid of the solutions to the issues you have sorted out by way of your article is a crucial case, as well as the ones which could have negatively damaged my career if I had not encountered your web blog. That know-how and kindness in playing with everything was priceless. I don’t know what I would have done if I hadn’t discovered such a subject like this. I can also at this moment look ahead to my future. Thanks for your time very much for the professional and sensible help. I won’t be reluctant to endorse your web site to anybody who will need support on this subject.

  22. Donc les hommes payent pour vos « manque de jugements » dans le choix de candidats ?S’il fallait qu’on arrête d’avoir des one-night pour pas passer pour des charrues y’a pu AUCUN célibataire qui baiserait…Est-ce que ce serait mieux pour autant ?C’que j’essaie de dire c’est qu’encore là la GROSSE DIFFÉRENCE entre comment un homme et une femme vivent un one-night est dans leur perception de l’événement…

  23. I have to show appreciation to you just for rescuing me from this problem. Just after researching throughout the internet and obtaining opinions that were not powerful, I thought my life was gone. Living devoid of the solutions to the difficulties you have resolved by means of your good website is a critical case, as well as ones which may have in a wrong way affected my entire career if I had not noticed your web blog. Your main capability and kindness in touching a lot of stuff was helpful. I am not sure what I would have done if I had not encountered such a thing like this. I can at this moment relish my future. Thanks so much for the expert and results-oriented guide. I will not be reluctant to endorse your web page to any individual who needs and wants care on this subject matter.

  24. Gwen, I was wondering how you overwinter your Japanese Maples indoors. I bought 3 this year that I want to keep as pot plants, rather than planting them in the garden. I was reading Margaret Roach and she overwinters hers in her barn so that was the way I had thought of going, but you have sucess wintering them inside?Any info would be helpful.Deborah

  25. So, if I understand Possum’s analysis, the under 50′s have shifted more against the Government, than the over 50′s.And given the usual expectations about age and voting patterns, this suggests that the loss in the Government’s support comes from younger people unhappy about lack of compassion towards refugees.Not the way the MSM and the opposition is spinning it at the moment.

  26. How is it that we’re so close in age (young)…yet we both feel ‘old-fashioned’? Maybe because our parents were friends…?I’m sure we could have a great conversation/rant about the above and more! Don’t even get me started on kids these days (and their parents)!

  27. I would like to express some thanks to this writer just for bailing me out of this crisis. As a result of looking out throughout the the net and coming across ideas which were not productive, I believed my life was gone. Living without the answers to the problems you have resolved all through your posting is a critical case, as well as ones that might have adversely affected my career if I hadn’t encountered your blog post. Your actual skills and kindness in dealing with a lot of stuff was helpful. I don’t know what I would’ve done if I hadn’t come across such a step like this. I can at this point look forward to my future. Thanks a lot so much for your professional and result oriented guide. I won’t be reluctant to refer the sites to any person who should have recommendations about this subject.

  28. 3.As a result, the State Department of Environmental Quality Director Dan Wyant and department spokesman Brad Wurfel resigned; former head of the DEQ’s Office of Drinking Water and Municipal Assistance Liane Shekter Smith has been fired. Practicing good safety habits is a reasonable procedure to follow as well. However, it only takes one poor tenant who does not pay their rent, neglects or damages the property and uses the fullness of the time allowed by law before they vacate, to cause a serious shortfall in cash flow. It is necessary for students to choose an exam carefully to avoid failing in the test which delays in moving forward in their careers.
    Cheap Jerseys China

  29. Если вы есть поклонником техники Apple и у вас есть телефон, вам будет занимательно узнать о различных фичах и моментах. Сейчас у большинства владельцев техники Apple появляются вопросы об использовании техники. Вы можете зайти [url=]dell ноутбук n5110[/url] сюда, где вам будут видны новости, исследования и приложения.

    На вы узнаете полезную справку. Помимо этого, на ресурсе есть онлайн-игры, которые вы можете сохранить на персональные гаджеты. Всем известно, что фирма Apple регулярно добавляет новые обзоры.

    Достаточно много выгодных предложений можно найти на портале. Там вы узнаете и утилиты для iOS. Если вам нужно добавить какое-то приложение, но ключевые скачать вы не можете – перейдите на ресурс

    Руководство портала регулярно публикует софт и добавляет много интересного. Вы прочитаете также занимательные новости, которые предоставят шанс вам экономить заряд батареи, улучшить функционал техники и многое другое.

    С помощью добавленных данных на ресурсе вы имеете шанс моментально выбрать всё необходимое. У вас появится возможность моментально сохранить нужный файл или выбрать необходимую программу.

    Перейдя на сайт, вы сможете созерцать за [url=]две операционные системы на одном компьютере[/url] новостями и рецензиями от менеджеров, которые есть действительно очень интересными. Вовремя формирования обзора администрация использует реальные источники, а у вас будет доступна возможность увидеть многое и почерпнуть важные знания.

    Если у вас поднимутся вопросы, вы сможете написать к администрации. Руководство сайта вкладывают силы в развитие сайта и делают сайт максимально информативным. На сайт переходят не только владельцы устройств Apple, но и все те, кто стремиться купить новый гаджет от лучшего бренда в мире! Если вы стремитесь узнать больше об аксессуарах Apple, сделать это возможно также на сайте в определённом блоке.

  30. Together, with the latest in technology for better energy efficiency, this can be the beginning of a new system that offers any company a way to better manage their current energy consumption and offer savings for the future. Not enough information to post and start writing. “Exciting match but stupid foul,” the China international wrote. You’ll see the moneylines for each team published as a plus or minus number, each related to the amount you can gain based on what amount you gamble. It can help all of the following aspects for better energy efficiency.
    Cheap NFL Jerseys Free Shipping

  31. Иногда бывает так, что подобрать надёжные вещи для ухода за младенцами невероятно проблемно. В наши дни многие делают заказ на надёжные товары из Европы, или длительное время ищут для своего новорожденного толковый товар в паутине.

    Если вы не уверены, куда обратиться, советуем рассмотреть этот [url=]купить Детские велосипеды с ручкой[/url] вариант, где вы сможете найти стоящие вещи для себя.

    На есть в продаже изделия для новорожденных и не только. Если вы в поиске кровати для малыша, вы сможете без особых трудностей приобрести колыбель или любой предпочтительный вам товар. Толковые детские вещи с любой раскраской также есть в продаже.

    В компании вы найдёте как колыбельки для одного, так и для двоих малых. К ним также идут и сумки для мамочек. При интересе их реально заказать отдельно. Изделия для особого удобства также есть в ассортименте. Тем не менее, их моментально разбирают. По этой причине рекомендуется делать заказ преждевременно.

    Если вы не владеете информацией, где купить детскую спецодежду, перейдите на ресурс. Там находится в наличии и одежда для крещения и белье в колыбельную. Вы без трудностей найдёте всё то, что вам надо. Если у вашего малыша есть аллергия на какие-то товары, консультанты учтут это при реализации.

    Важно и то, что текстиль из Турции, который есть в присутствии сетевого магазина очень высокого качества. Вы найдёте различные товары по интересной цене. Приобрести прыгуны можно без особых трудностей. Надо кликнуть на сайт, выбрать наилучший и заказать его. После чего с вами свяжутся менеджеры и проконсультируют по всем нюансам.

    Если вам необходима содействие администраторов, вы имеете возможность соединиться с ними. Инфо их можно найти в соответствующем меню. Важным есть и то, что на сайте постоянно проходят акции. Вы можете попасть на интересующую вас акцию, вплоть до акции на детский трикотаж [url=]Верхняя одежда для детей[/url] или полотенца детские.

    Приобрести качели подвесные тоже реально по интересующей вас цене. Вас проконсультируют о всех нюансах и подробностях вовремя закупки. Благодаря этому вы сделаете наилучший выбор!

  32. Thanks for spelling out your perspective, Mike. As I understand your position, whether membership in an organisation counts as a conflict of interest depends on whether the organisation subscribes to rational beliefs. Correct?This criterion for what does and doesn’t count as a conflict of interest is the most original I’ve seen for ages. Can you point me to any editorial policies, or commentaries on COI, that express this view? Have you seen it applied to other issues, such as research on climate change, fluoridation or parapsychology? Or is your criterion especially tailored for the vaccination issue?Regards,Brian

  33. Mark, Apologies for the late response! 2-FMA is a very difficult research chemical to acquire, and so unfortunately, it occasionally takes us a little longer to stock up on it. Soon, we will have a ‘email me when it’s in stock’ area.Let us know if you’d like to be added!!

  34. I simply desired to thank you so much once more. I am not sure the things that I would have undertaken without those tricks shared by you directly on this situation. Completely was the frustrating issue in my opinion, nevertheless looking at a professional approach you dealt with it forced me to jump for delight. I’m just thankful for your support as well as have high hopes you are aware of an amazing job you happen to be carrying out educating the others all through a site. I know that you haven’t got to know all of us.

  35. Подобрать инвестора в Российской Федерации сейчас не так уж и легко. Чтобы найти компанию, которая поддержит идею инвестиции в недвижимость – тяжко. Однако, варианты есть. Вы сможете перейти [url=]найти инвестора для бизнеса в Волгограде[/url] сюда, где вам раскроется колоссальное количество возможностей.

    На вам будет шанс извлечь финансы в моментальные сроки. Механизм оформления происходит не более пары дней. Организация предоставляет охотно деньги для среднего бизнеса. Найти вкладчика для бизнеса довольно легко. Условия инвестиционных процессов вас также заинтригуют.

    Компания предоставляет средства на выгодных условиях. Вы сможете быстро найти инвестора для стартапа. Всё, что вам нужно – соединиться с менеджерами. Они проконсультируют вас о всех нюансах сделки. После этого вы имеете возможность в сжатые сроки принять активы, а ваши дела пойдут на верх!

    Условия инвестирования приемлемые во многих административных центах. Вы имеете шанс получить средства под залог недвижимости. При желании вы сможете получить активы и на выгодных условиях. Получение средств допускается на различных условиях. Если вы не думаете, что ваш бизнес будет успешным, вы имеете шанс также посоветоваться с консультантами. Они подскажут, куда выгодно вложить средства.

    Финансирование проекта на приемлемых условиях – это основное направление организации. Выбрать инвестора для бизнеса вы сможете мгновенно, если кликните [url=]доходы инвесторов[/url] тут, финансирование стартапа за 3 дня любого направления в целом возможно. Всё, что вам нужно – собрать документы.

    После чего администраторы проинформируют вас о дальнейших действиях. Выгодные условия вложения вы получите мгновенно, если обратитесь в компанию к администраторам. Интересное вложение средств быстро окупается. Однако нужно помнить, что сегодня на рынке достаточно много мошенников.

    Если вы не желаете попасть в руки мошенников, позвоните к опытным профессионалам. Они проконсультируют вас, затем вы сможете продвигать успешно свой стартап или бизнес.

  36. Иногда бывает так, что купить проверенные вещи для ухода за новорожденными невероятно трудно. Сегодня многие делают заказ на проверенные вещи из Финляндии, или длительное время подыскивают для своего малыша достойный товар в паутине.

    Если вы не уверены, куда обратиться, рекомендуем рассмотреть этот [url=]купить Мольберты детские[/url] вариант, где вы подберете качественные вещи для малого.

    На находятся в продаже изделия для малых и не только. Если вы в поиске кровати для малыша, вы можете без особых сложностей подобрать колыбель или любой интересующий вас товар. Проверенные детские вещи с любой раскраской также есть в продаже.

    В компании вы найдёте как колыбельные для одного, так и для двоих малышей. К ним также в наличии и сумки для мам. При интересе их реально заказать порознь. Изделия для особого комфорта тоже есть в наличии. Хотя, их очень быстро раскупают. По этой причине рекомендуется делать заказ раньше срока.

    Если вы не знаете, где приобрести детскую одежду, кликните на ресурс. Там находится в наличии и вещи для крещения и белье в кроватку. Вы без трудностей найдёте всё то, что вам надо. Если у вашего ребенка есть нетерпимость на какие-то вещи, консультанты учтут это при сбыте.

    Отметим и то, что текстиль из Турции, который есть в наличии сетевого магазина очень высокого качества. Вы подберете различные вещи по лучшей цене. Приобрести прыгуны реально без особых трудностей. Достаточно кликнуть на ресурс, подобрать наилучший и купить его. После чего с тобой свяжутся администраторы и проинформируют по всем моментам.

    Если вам потребуется помощь менеджеров, вы имеете возможность связаться с ними. Контактные данные их реально найти в соответствующем блоке. Важно и то, что на портале постоянно проходят акции. Вы можете попасть на любую акцию, вплоть до акции на детский трикотаж [url=]купить Коляски трансформеры[/url] или полотенца детские.

    Заказать качели подвесные тоже возможно по приемлемой цене. Вас проконсультируют о всех моментах и подробностях вовремя закупки. Благодаря этому вы сделаете наилучший выбор!

  37. What i dοn’t understood is іn fact how you’re no longer rrеally
    much more neatly-appreciаted thn you migh be right now.
    You’rе soo intelⅼigent. You know theref᧐re significantly
    relating to this matteг, maⅾe me individuallʏ imagine it from so
    many varied angles. Its like women and men are not involved except it’s one thing to accomplish
    with Lady gaga! Your persоnal stuffs outstanding.
    All thе time handle iit up!

Leave a Reply

Your email address will not be published. Required fields are marked *


You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>