Data Science Academy - Python Fundamentos - Capítulo 7

Download: http://github.com/dsacademybr



In [1]:

    
# Versão da Linguagem Python
from platform import python_version
print('Versão da Linguagem Python Usada Neste Jupyter Notebook:', python_version())









    



Versão da Linguagem Python Usada Neste Jupyter Notebook: 3.7.6

Missão: Gerar uma lista de números primos.

Nível de Dificuldade: Médio

Premissas

É correto que 1 não seja considerado um número primo? * Sim
Podemos assumir que as entradas são válidas? * Não
Podemos supor que isso se encaixa na memória? * Sim

Teste Cases

None -> Exception
Not an int -> Exception
20 -> [False, False, True, True, False, True, False, True, False, False, False, True, False, True, False, False, False, True, False, True]

Algoritmo

Para um número ser primo, ele deve ser 2 ou maior e não pode ser divisível por outro número diferente de si mesmo (e 1).

Todos os números não-primos são divisíveis por um número primo.

Use uma matriz (array) para manter o controle de cada número inteiro até o máximo
Comece em 2, termine em sqrt (max) Podemos usar o sqrt (max) em vez do max porque: Para cada valor que divide o número de entrada uniformemente, há um complemento b onde a b = n Se a> sqrt (n) então b <sqrt (n) porque sqrt (n ^ 2) = n * "Cross off" todos os números divisíveis por 2, 3, 5, 7, ... configurando array [index] para False

Animação do Wikipedia:

Solução



In [2]:

    
import math


class PrimeGenerator(object):

    def generate_primes(self, max_num):
        if max_num is None:
            raise TypeError('max_num não pode ser None')
        array = [True] * max_num
        array[0] = False
        array[1] = False
        prime = 2
        while prime <= math.sqrt(max_num):
            self._cross_off(array, prime)
            prime = self._next_prime(array, prime)
        return array

    def _cross_off(self, array, prime):
        for index in range(prime*prime, len(array), prime):
            array[index] = False

    def _next_prime(self, array, prime):
        next = prime + 1
        while next < len(array) and not array[next]:
            next += 1
        return next

Teste da Solução



In [3]:

    
%%writefile missao2.py
from nose.tools import assert_equal, assert_raises


class TestMath(object):

    def test_generate_primes(self):
        prime_generator = PrimeGenerator()
        assert_raises(TypeError, prime_generator.generate_primes, None)
        assert_raises(TypeError, prime_generator.generate_primes, 98.6)
        assert_equal(prime_generator.generate_primes(20), [False, False, True, 
                                                           True, False, True, 
                                                           False, True, False, 
                                                           False, False, True, 
                                                           False, True, False, 
                                                           False, False, True, 
                                                           False, True])
        print('Sua solução foi executada com sucesso! Parabéns!')


def main():
    test = TestMath()
    test.test_generate_primes()


if __name__ == '__main__':
    main()









    



Overwriting missao2.py



In [4]:

    
%run -i missao2.py









    



Sua solução foi executada com sucesso! Parabéns!