Exercício para estudo

Prévia do material em texto

Algoritmos e Estrutura de Dados 1
Profa. Dra. Maria´ Cristina Vasconcelos Nascimento
Monitor: Kevin Brennan Guzi
1. Introduc¸a˜o
A teoria dos nu´meros tem como objetivo o estudo das propriedades dos nu´meros e, em par-
ticular, os nu´meros inteiros. Esse ramo da matema´tica e´ estudado desde civilizac¸o˜es antigas,
pore´m e´ na Gre´cia que primeiro identificamos a teoria do nu´meros tal como entendemos hoje
em dia. O que mais chama atenc¸a˜o neste ramo sa˜o as propriedades dos nu´meros primos. Tal
importaˆncia e´ dada por na˜o existir um me´todo eficiente para encontrar esses nu´meros, que tem
grandes aplicac¸o˜es na teoria dos nu´meros e criptografia. A primeira forma de tabelar os nu´meros
primos surgiu com Erato´stenes, por volta de 300 a.C. e 200 a.C., que logo foi denominado como
o Crivo de Erato´stenes.
2. Funcionamento do Crivo de Erato´stenes
O crivo tem como objetivo identificar todos os nu´meros primos ate´ um nu´mero n, sendo n >= 2.
Sa˜o feitos os seguintes passos:
• Listamos todos os nu´meros de 2 a n.
• Pegamos o primeiro nu´mero da lista, no caso 2, que sera´ atribu´ıdo a uma varia´vel m, e
retiramos da lista todos os nu´meros que sa˜o divis´ıveis por 2 que na˜o seja o pro´prio 2.
• Em seguida, e´ escolhido o pro´ximo nu´mero que na˜o foi retirado da lista, no caso, o nu´mero
3. Portanto, agora m vale 3, e sa˜o retirados todos os nu´meros divis´ıveis por 3 desta lista,
exceto o 3.
• Este processo continua ate´ que o pro´ximo nu´mero m tenha a seguinte condic¸a˜o, m2 > n.
Assim a contagem pa´ra. Todos os nu´meros da lista que na˜o foram retirados sa˜o primos.
1
Exemplo:
Um exemplo para n = 120.Primeiramente listamos os nu´meros de 2 a 120, como mostrado
na figura a seguir:
Logo pegamos o primeiro nu´mero da lista e atribuimos-o a m, assim m = 2, e retiramos
da lista os nu´meros divis´ıveis por 2, que na˜o seja 2:
2
Tomaremos como m o pro´ximo nu´mero na˜o retirado da lista, assim m = 3, e enta˜o,
retiramos da lista os nu´meros divis´ıveis por 3, que na˜o seja 3:
Fazemos o mesmo para m = 5:
3
Para m = 7:
Quando m = 11, a condic¸a˜o m2 > n sera´ verdadeira, 112 > 120, portanto a contagem
pa´ra por a´ı. Todos os nu´meros na˜o retirados da lista sa˜o nu´meros primos, como e´ poss´ıvel
verificar na figura a seguir.
Figura 1: Resultado quando m = 11.
Figura 2: figm11
3. Exerc´ıcio
O programa a ser feito consiste em calcular a quantidade de fatores primos de um conjunto
de nu´meros inteiros. O programa deve ler a quantidade de nu´meros a serem analisados N .
Para cada nu´mero lido mi, sendo i ∈ {1, 2, ..., n}, deve ter como sa´ıda o pro´prio mi seguido da
quantidade de fatores primos, separados por ”:”.
4
Exemplo
Entrada
11
346574243
1233543563
1234543628
756432342
985632576
433212557
642345678
321334572
956432312
186314639
345645721
Sa´ıda
346574243 : 3
1233543563 : 3
1234543628 : 5
756432342 : 4
985632576 : 3
433212557 : 2
642345678 : 5
321334572 : 4
956432312 : 4
186314639 : 2
345645721 : 1
Restric¸o˜es:
2 ≤ mi ≤ 2000000000
0 < n ≤ 100
O Crivo de Erato´stenes deve ser usado para a resoluc¸a˜o do problema. Usar Lista Esta´tica
Sequencial para implementar o Crivo de Erato´stenes, tendo que usar func¸o˜es de inicializac¸a˜o,
inserc¸a˜o (inserc¸a˜o ao final da lista), remoc¸a˜o e busca. Uma outra Lista Esta´tica Sequencial
tambe´m deve ser usado para armazenar os nu´meros que sera˜o feitos a fatorac¸a˜o, tendo de
haver func¸o˜es de inicializac¸a˜o, inserc¸a˜o e remoc¸a˜o. As listas e suas func¸o˜es devem ser
implementadas a parte do programa como uma biblioteca. A lista deve ser implementada no
mesmo formato apresentado no slide.
4. Refereˆncias Bibliogra´ficas
• pt.wikipedia.org/wiki/Crivo-de-Erato´stenes.
• Coutinho, S. C. (2007) Nu´meros Inteiros e Criptografia RSA Segunda Edic¸a˜o, IMPA,
Rio de Janeiro.
5