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
fim-para

/* 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
        fim-para
    fim-se
fim-para

Vêem como é simples?

Crivo de Eratóstenes implementado em C

#include
#include
// 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
raiz=sqrt(valorMaximo);

// Terceiro passo
for (i=2; i<=valorMaximo; i++) {
vetor[i]=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!

5,326 thoughts on “Crivo de Eratóstenes

  1. Doramectin (Dectomax) is a veterinary drug approved by the Food and Drug Administration (FDA) for the treatment of parasites such as gastrointestinal roundworms, lungworms, eyeworms, grubs, sucking lice and mange mites in cattle.]

    It is used for the treatment and control of internal parasitosis (gastrointestinal and pulmonary nematodes), ticks and mange (and other ectoparasites). Doramectin is a derivative of ivermectin. Its spectrum includes: Haemonchus spp., Ostertagia spp., Trichostrongylus spp., Cooperia spp., Oesophagostomum spp., Dictyocaulus viviparus, Dermatobia hominis, Boophilus microplus, Psoroptes bovis, among many other internal and external parasites. It is available in 2 dosage forms: as an injection and as a 5 mg/ml topical solution.

    Doramectin is also marketed in many Latin-American and some Asia and Africa countries as Doramec L.A. (manufactured by Agrovet Market Animal Health]) in an 1% Doramectin Long Acting Injectable Solution for cattle, sheep, swine] and others. Its oleous carrier confers to Doramec L.A. a slow and prolonged liberation, extending its action up to 42 days.

    Doramectin is also available for horses] as an oral flavored bioadhesive gel under the name Doraquest L.A. Oral Gel.] It can be used to control and treat internal parasites as roundworms, lungworms and some external parasites.
    From TCS INDUSTRY LTD.

  2. With every thing which appears to be developing within this specific area, all your perspectives are somewhat stimulating. Even so, I am sorry, but I do not subscribe to your whole theory, all be it stimulating none the less. It seems to everybody that your opinions are not totally justified and in reality you are generally yourself not even thoroughly convinced of your point. In any event I did enjoy reading it.

  3. that when he’s looking at stupid videos on line. “Dad, I’m just doing research.” When ever I buy a cartridge I try to imagine how many it would take to fill an oil barrel. What would that cost me? About 1o grand? Before I can do the math I’m on to the next thing.

  4. video.Let?s take a look at the mainstream sports.The CUT, along with unions and women’s rights movements, protested outside the headquarters of the National Social Security Institute in Sao Paulo. It also covers treatment associated with unconscious person together with, last but possibly not least, bleeding pains, burns, and cracks. Men, who could not successfully boost sperm motility, can opt for IVF.
    Cheap Jerseys From China

  5. Импортное оборудование для переработки полимерных отходов

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

    Одним из новейших предпринимательских трендов является переработка таких отходов, с производством полезных и коммерчески привлекательных товаров: плитки для тротуара, почти вечных покрытий для кровли и других полезных товаров. Производственная компания ПК «Полимерстрой18» предлагает заказать специализированное оборудование для переплавки таких отходов в дорогостоящие материалы.

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

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

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

    А ещё такие линии найдут свое место рядышком с предприятиями, в процессе работы которых вырабатывается большой объём полимерных отходов.

  6. You can turn her on using the foreplay tips like kissing on the breasts, neck and on the back. Buy the gear online, perhaps through a welldesigned, sleek website (heh heh), and then you are ready to go (after reviewing safety rules, of course). Another available class is wilderness and remote medical.Jenny Braun writes about a number of topics, mainly about holidays. The sports assistance classes also make it easier to educate other athletes on methods for reducing risks regarding injury or ailment.
    Wholesale NHL Jerseys

  7. I think this is among the most significant info for me. And i am glad reading your article. But want to remark on some general things, The site style is perfect, the articles is really excellent : D. Good job, cheers

  8. проститутки иркутска
    купить огнестрельное оружие бу
    элитные проститутки
    купить наркотик цена
    проститутки екатеринбург
    зоо порно с собакой

  9. Peticionar para que os imposos nao aumentem nao é nada. É prolongar a agonia. Cm este nivel de impostos nunca chegaremos a bom porto. Mas pronto, contetam-se por ficar encalhados numa ilha deserta….Às vezes dou comigo a querer muto que façam mesmo as asneiras todas de uma vez. Que é para ver se afundam o país mais rápido…. e renascer das cinzas. Chafurdar na lama nao interessa. .Rb

  10. Современное оборудование для переработки пластика

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

    Одним из относительно новых предпринимательских трендов становится переработка подобных отходов, с выработкой полезных и коммерчески привлекательных товаров: плитки для тротуара, долговечных кровельных покрытий и других полезных вещей. Наша фирма ПК «Полимерстрой18» предлагает заказать специальное оборудование для переработки полимерного мусора в долговечные строительные материалы.

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

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

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

    А ещё подобные линии найдут своё место рядом с заводами, в процессе работы которых образуется большой объем полимерных отходов.

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>