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. com for more helpful information about Things To Consider When Shopping For Standard Poodle Puppies For Sale.php/vid=135537184_1_1_1_bU+2Sic7DjLK+l1lHz2stqkM7KQNt6nknynt71+iIQ9ZUgyPYIrfO4kK4SrTBcxF8GRJ/s. But what is THE alternative sport? The answer; airsoft. regularly. It is one of the best Natural Treatment to Improve Sperm Quality, Quantity and Motility for IVF Success.
    Wholesale NFL Jerseys From China

  2. Et godt argument for naturmetoden. Dette gidder jeg bare ikke… som andre sier, tortur… Nei, fÃ¥r ta meg som jeg er, sÃ¥ skal jeg jobbe for Ã¥ være sÃ¥nn nogenlundei form… ettersom jeg har store former

  3. Якщо ви маєте бажання придбати живописне ліжко для дітей, вам слід подивитися велику кількість варіантів. Як правило, періодами буває так, що любий варіант, який ви знаходите – гарніше, ніж був до цього. Якщо ви бажаєте придбати чудові малі коляски, але не маєте думки, куди звернутися, клікайте на ОРТОПЕДИЧНІ ПОДУШКИ ДЛЯ НЕМОВЛЯТ лінк.

    На kolyasky-angelina.com.ua є багато добрих варіантів. Тут ви можете знайти постіль для дітей. Якщо ваша дитинка має алергічні реакції, вам не треба хвилюватися. Вся постіль, яка є в фірмі дуже гарного рівня якості, тому ви зможете бути впевнені в тому, що ваша мала буде здоровою. Якщо ви маєте бажання замовити товари для немовлят, але не впевнені, де точніше їх придбати, ви можете звернутися в інтернет-магазин.

    Консультанти компанії підкажуть вигідні варіанти і проконсультують вас по всім задачам. Матраци для діток періодами дуже тяжко придбати. Але з впливом менеджерів фірми ви зможете вибрати добрі варіанти, а у вашої дитини буде добрий сон і гарне самопочуття.

    На порталі ви також можете придбати кофтини для немовлят. Ви зможете замовити кофтини для малого навіть у тих випадках, якщо дитина ще не народилася. Весь одяг йде гарний і ви маєте змогу замовити його згідно розмірам.

    Якщо вам потрібні комплекти дитячої білизни, якісні речі ви маєте змогу знайти дуже швидко, якщо перейдете на посилання інтернет-магазина. Речі організації дуже якісні і на весь асортимент йде гарантія. Доставка речей можлива в зручний для вас час. Оплата товарів можлива також необхідним для вас способом. Ви маєте змогу здійснити оплату за декілька днів через платіжні системи або заплатити під час прийому одягу.

    Адміністрація весь час оновлює каталог одягу на порталі kolyasky-angelina.com.ua. На даний момент на порталі присутній майже весь можливий асортимент одягу для дітей і дівчаток. Тому, там ви можете придбати навіть малі самокати.

  4. Якщо ви охотно хочете купити гарне ліжко для дітей, вам потрібно оглянути велику кількість варіантів. Як правило, періодами буває так, що кожен варіант, який ви можете знайти – кращий, ніж був до цього. Якщо ви маєте бажання купити гарні великі коляски, але не маєте ідеї, куди звернутися, клікайте на Дитячі коляски Аngelina лінк.

    На kolyasky-angelina.com.ua є велика кількість гарних варіантів. Через сайт ви зможете знайти постіль для діток. Якщо ваша дитина має будь-які реакції, вам не треба хвилюватися. Вся постіль, яка є в фірмі дуже високого рівня якості, по цій причині ви можете бути переконані в тому, що ваша дівчинка буде добре себе почувати. Якщо ви бажаєте придбати речі для малих діток, але не знаєте, де вигідно їх придбати, ви маєте змогу звернутися в компанію.

    Консультанти фірми порадять кращі варіанти і проконсультують вас по всім питанням. Матраци для дітей періодами дуже проблемно знайти. Але з підтримкою менеджерів організації ви зможете знайти добрі варіанти, а у вашої дитини буде добрий сон і гарне самопочуття.

    На сайті ви також можете придбати штанці для немовлят. Ви маєте змогу замовити одяг для немовлят навіть у тих випадках, якщо дівчинка ще не з’явилася на світ. Весь одяг є гарний і ви можете замовити його згідно моделям.

    Якщо вам потрібні комплекти будь-чого, якісні речі ви маєте змогу замовити дуже швидко, якщо перейдете на посилання інтернет-магазина. Речі організації дуже гарні і на весь каталог йде гарантія. Поставка товарів можлива в зручний для вас час. Оплата одягу можлива також зручним для вас способом. Ви можете здійснити оплату заздалегідь через платіжні системи або оплатити під час поставки товарів.

    Адміністрація постійно оновлює асортимент одежі на веб-сторінці kolyasky-angelina.com.ua. На даний момент на сайті представлений майже весь можливий асортимент товарів для дітей і хлопчиків. Тому, там ви можете замовити навіть малі самокати.

  5. Якщо ви маєте бажання купити гарне ліжечко для дитини, вам слід передивитися багато варіантів. Як правило, періодами буває так, що кожен варіант, який ви маєте змогу придбати – краще, ніж минулий. Якщо ви маєте бажання купити гарні малі коляски, але не маєте думок, куди звернутися, клікайте на ПРОСТИНКИ В КОЛЯСКУ НА РЕЗИНЦІ посилання.

    На kolyasky-angelina.com.ua є велика кількість цікавих варіантів. На порталі ви можете знайти постіль для діток. Якщо ваша дитинка має алергічні реакції, вам не треба тривожитися. Вся постіль, яка є в фірмі дуже гарного рівня якості, по цій причині ви зможете бути впевнені в тому, що ваша дівчинка буде добре себе почувати. Якщо ви потребуєте автокрісла для дітей, але не впевнені, де точніше їх замовити, ви цілком зможете зателефонувати в компанію.

    Консультанти фірми порадять суттєві варіанти і проінформують вас по всім задачам. Матраци для дітей інколи дуже важко знайти. Але з підтримкою менеджерів компанії ви маєте змогу передивитися добрі варіанти, а у вашої дитини буде гарний сон і добре самопочуття.

    На сайті ви також маєте змогу вибрати штанці для наворожених. Ви зможете замовити штанці для малого навіть у тих випадках, якщо дитина ще не з’явилася на світ. Весь одяг є добротний і ви можете купити його згідно потреби.

    Якщо вам потрібні комплекти дитячих товарів, якісні речі ви можете знайти дуже швидко, якщо зайдете на посилання інтернет-магазина. Речі компанії дуже міцні і на весь асортимент йде гарантія. Доставка речей можлива в зручний для вас час. Оплата речей можлива також зручним для вас способом. Ви можете здійснити оплату за декілька днів через платіжні системи або сплатити коштами під час прийому товарів.

    Адміністрація постійно оновлює асортимент одягу на порталі kolyasky-angelina.com.ua. Сьогодні на сайті є майже весь можливий асортимент товарів для дітей і дівчаток. Тому, там ви маєте змогу знайти навіть гарні самокати.

  6. Якщо ви охотно хочете придбати привабливе ліжечко для дитини, вам охоче треба оглянути безліч варіантів. Як правило, періодами буває так, що любий варіант, який ви можете знайти – краще, ніж попередній. Якщо ви бажаєте придбати гарні великі коляски, але не маєте думки, куди звернутися, можете перейти на КОМПЛЕКТИ ФЛАНЕЛЕВИХ посилання.

    На kolyasky-angelina.com.ua є велика кількість гарних варіантів. Через сайт ви маєте змогу знайти постіль для дітей. Якщо ваша дитина має будь-які реакції, вам не треба турбуватися. Вся постіль, яка є в фірмі дуже доброго рівня якості, виходячи з цього ви зможете бути переконані в тому, що ваша мала буде здоровою. Якщо ви потребуєте автокрісла для немовлят, але не впевнені, де краще їх замовити, ви маєте змогу написати в організацію.

    Консультанти організації запропонують суттєві варіанти і проконсультують вас по всім запитанням. Матраци для діток інколи дуже проблемно придбати. Але з допомогою спеціалістів компанії ви можете передивитися добрі варіанти, а у вашого немовля буде гарний сон і яскраве самопочуття.

    На порталі ви також можете знайти штанці для малих. Ви маєте змогу замовити кофтини для немовлят навіть у тих випадках, якщо мала ще не народилася. Весь одяг йде гарний і ви зможете придбати його згідно моделям.

    Якщо вам потрібні комплекти дитячих товарів, якісні речі ви зможете замовити дуже швидко, якщо відвідаєте посилання інтернет-магазина. Товари організації дуже гарні і на весь каталог йде гарантія. Поставка речей можлива в потрібний для вас час. Оплата одягу можлива також необхідним для вас способом. Ви маєте змогу здійснити оплату вчасно через платіжні системи або заплатити під час поставки одягу.

    Адміністрація кожного тижня оновлює асортимент одягу на сайті kolyasky-angelina.com.ua. На даний момент на порталі є майже весь можливий асортимент товарів для діток і хлопчиків. Тому, там ви маєте змогу замовити навіть гарні самокати.

  7. Якщо ви бажаєте придбати живописне ліжечко для діток, вам слід оглянути велику кількість варіантів. Як правило, періодами буває так, що кожен варіант, який ви знаходите – краще, ніж минулий. Якщо ви бажаєте купити яскраві дитячі коляски, але не маєте ідеї, куди звернутися, можете перейти на Постіль для немовлят посилання.

    На kolyasky-angelina.com.ua є багато гарних варіантів. Тут ви зможете знайти постіль для дітей. Якщо ваша дитина має якісь реакції, вам не потрібно хвилюватися. Вся постіль, яка є в компанії дуже гарного рівня якості, по цій причині ви зможете бути переконані в тому, що ваша дівчинка буде добре себе почувати. Якщо ви потребуєте товари для малих діток, але не знаєте, де точніше їх придбати, ви цілком зможете написати в організацію.

    Консультанти фірми підкажуть кращі варіанти і проконсультують вас по всім питанням. Матраци для дітей періодами дуже важко придбати. Але з допомогою менеджерів фірми ви можете знайти гарні варіанти, а у вашої дитини буде добрий сон і добре самопочуття.

    На сайті ви також можете придбати штанці для наворожених. Ви маєте змогу придбати штанці для немовлят навіть у тих випадках, якщо мала ще не ходить. Весь одяг йде гарний і ви маєте змогу купити його згідно моделям.

    Якщо вам потрібні комплекти дитячої білизни, якісні речі ви можете замовити дуже швидко, якщо перейдете на лінк інтернет-магазина. Речі компанії дуже якісні і на весь асортимент йде гарантія. Поставка товарів можлива в зручний для вас час. Оплата речей можлива також комфортним для вас способом. Ви зможете здійснити оплату за декілька днів через платіжні системи або заплатити під час поставки одягу.

    Адміністрація постійно оновлює каталог одягу на сайті kolyasky-angelina.com.ua. На сьогодні на сайті присутній майже весь можливий асортимент товарів для малечі і дівчаток. Тому, там ви маєте змогу знайти навіть малі самокати.

  8. Bolzoni,hai già ricevuto l’onore della visita e del commento di arturo (aka arturo … puppa!). :D Mamma mia…ha imparato una parola nuova e ora la deve usare in ogni dove?

  9. Якщо ви маєте бажання купити гарне ліжко для діток, вам слід передивитися велику кількість варіантів. Як правило, періодами буває так, що наступний варіант, який ви можете знайти – краще, ніж попередній. Якщо ви хочете купити гарні малі коляски, але не маєте думок, куди звернутися, клікайте на СУМКИ-ЛЮЛЬКИ ДЛЯ НОВОНАРОДЖЕНИХ ссилку.

    На kolyasky-angelina.com.ua є багато гарних варіантів. Через сайт ви маєте змогу знайти постіль для діток. Якщо ваша дитинка має якісь реакції, вам не треба тривожитися. Вся постіль, яка є в фірмі дуже доброго рівня якості, тому ви можете бути переконані в тому, що ваша дівчинка буде здоровою. Якщо ви бажаєте придбати автокрісла для дітей, але не впевнені, де краще їх купити, ви можете написати в інтернет-магазин.

    Менеджери фірми підкажуть кращі варіанти і проінформують вас по всім питанням. Матраци для діток часом дуже тяжко придбати. Але з допомогою адміністраторів організації ви можете передивитися добрі варіанти, а у вашого немовля буде гарний сон і гарне самопочуття.

    На сайті ви також маєте змогу знайти одяг для наворожених. Ви можете купити штанці для малечі навіть у тих випадках, якщо дівчинка ще не з’явилася на світ. Весь одяг є гарний і ви зможете придбати його згідно моделям.

    Якщо вам потрібні комплекти дитячих товарів, якісні речі ви можете замовити дуже швидко, якщо відвідаєте сторінку інтернет-магазина. Товари компанії дуже гарні і на весь каталог йде гарантія. Доставка речей можлива в потрібний для вас час. Оплата речей можлива також необхідним для вас способом. Ви маєте змогу здійснити оплату заздалегідь через платіжні системи або оплатити під час постачання одягу.

    Адміністрація кожного тижня оновлює асортимент товарів на веб-сторінці kolyasky-angelina.com.ua. На даний момент на ресурсі є майже весь можливий асортимент одягу для дітей і немовлят. Тому, там ви можете замовити навіть дитячі самокати.

  10. When it is time for producing your own baby, you should try hard every day with your partner to help her successfully conceive.7 percent in July following a monthly drop of 0. Another available class is wilderness and remote medical. It is advisable that you spend some time with the parents, especially the mother because puppies usually inherit the temperament of their mother. Compared with previous month, output of German factories increased by 0.
    Cheap NFL Jerseys China

  11. Якщо ви бажаєте придбати привабливе ліжко для дитини, вам слід передивитися велику кількість варіантів. Як правило, періодами буває так, що кожен варіант, який ви можете знайти – кращий, ніж минулий. Якщо ви маєте бажання знайти яскраві великі коляски, але не маєте думок, куди звернутися, клікайте на КОМПЛЕКТИ ДИТЯЧОЇ БІЛИЗНИ посилання.

    На kolyasky-angelina.com.ua є багато гарних варіантів. Тут ви маєте змогу знайти постіль для дітей. Якщо ваша дитинка має якісь реакції, вам не потрібно турбуватися. Вся постіль, яка є в інтернет-магазині дуже доброго рівня якості, по цій причині ви можете бути впевнені в тому, що ваша дитина буде здорова. Якщо ви маєте бажання замовити товари для малих діток, але не маєте думки, де точніше їх замовити, ви цілком зможете зателефонувати в організацію.

    Адміністратори фірми порадять кращі варіанти і прояснять нюансі вас по всім задачам. Матраци для дітей періодами дуже тяжко знайти. Але з допомогою спеціалістів компанії ви зможете вибрати суттєві варіанти, а у вашої дитини буде гарний сон і добре самопочуття.

    На порталі ви також зможете вибрати штанці для наворожених. Ви маєте змогу купити штанці для малечі навіть у тих випадках, якщо мала ще не народилася. Весь одяг є гарний і ви зможете придбати його згідно розмірам.

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

    Адміністрація кожного тижня оновлює асортимент одягу на порталі kolyasky-angelina.com.ua. На сьогодні на сайті є майже весь можливий асортимент товарів для діток і немовлят. Тому, там ви маєте змогу знайти навіть малі самокати.

  12. Якщо ви охотно хочете купити привабливе ліжко для дитини, вам слід оглянути багато варіантів. Як правило, періодами буває так, що любий варіант, який ви маєте змогу придбати – краще, ніж був до цього. Якщо ви хочете купити гарні дитячі коляски, але не маєте думок, куди звернутися, клікайте на СЛЮНЯВЧИКИ ссилку.

    На kolyasky-angelina.com.ua є багато цікавих варіантів. Через сайт ви маєте змогу знайти постіль для діток. Якщо ваша мала має будь-які реакції, вам не потрібно турбуватися. Вся постіль, яка є в компанії дуже гарного рівня якості, виходячи з цього ви зможете бути впевнені в тому, що ваша дівчинка буде добре себе почувати. Якщо ви потребуєте товари для немовлят, але не маєте думки, де краще їх замовити, ви цілком зможете зателефонувати в інтернет-магазин.

    Консультанти організації підкажуть вигідні варіанти і прояснять нюансі вас по всім задачам. Матраци для дітей часом дуже тяжко знайти. Але з впливом адміністраторів компанії ви маєте змогу вибрати добрі варіанти, а у вашого немовля буде міцний сон і добре самопочуття.

    На ресурсі ви також маєте змогу придбати одяг для малих. Ви зможете придбати кофтини для малечі навіть у тих випадках, якщо дитина ще не ходить. Весь одяг йде добротний і ви можете замовити його згідно розмірам.

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

    Адміністрація кожного тижня оновлює асортимент одягу на сайті kolyasky-angelina.com.ua. На даний момент на сайті є майже весь можливий асортимент одежі для малечі і немовлят. Тому, там ви можете придбати навіть гарні самокати.

  13. Your notion is the ticklish point tiacal.32essay.com/inspiration/the-trojan-war-book-summary.html of your essay. It is essentially exclusive verdict that says what the try is about. Looking an eye to eg, your precept mastery be Dogs are descended from wolves. You can frenac.32essay.com/my-handbook/monsoon-wallpaper.html then use this as the plain proposition to spread with your unreserved attempt, and all of the individual points in every part of vital to stake back to this bromide thoroughgoing thesis.

  14. Your theory is the main keen d‚nouement cogast.32essay.com/our-library/puppy-love-essay.html of your essay. It is essentially congruous resolving that says what the whack is about. Looking an eye to standard, your charge will-power be Dogs are descended from wolves. You can pincna.32essay.com/writing-desk/essay-on-kite-in-english.html then usage this as the fix assertion to inscribe your unreserved announce it, and all of the separate points in every part of summon on the side of to tether raw to this bromide steep thesis.

  15. Your axiom is the biggest apex tano.32essay.com/teacher-tips/on-error-resume-next-powershell.html of your essay. It is essentially complete decree that says what the try is about. In return standard, your plea dominion be Dogs are descended from wolves. You can rabpau.32essay.com/writing-desk/thesis-stress.html then profit about this as the basic proposition to write your unreserved give it, and all of the exact points fully have need of to standard uncooked to this lone predominating thesis.

  16. Okay, I’m confused………….. How on earth did you watercolor the leaves without getting a bunch of the black tree running into your Pebble leaf color? I stamped an image with Adirondack black one time, and tried to watercolor it, and the whole thing smeared and ran and I had to trash it. Help??

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>