Python : matemática : números primos

segunda-feira, 27/02/2012 2:32 pm  

Esses dias realizando alguns exercícios matemáticos e algoritmos em python me deparei com um que me solicitou:

Implementar uma função que retorne verdadeiro se o número for primo (falso caso contrário). Testar de 1 a 100.

Bom primeira coisa que fiz foi pensar em dividir esta atividade em 2 funções, uma para realizar a interação dos números e dentro chamar outra função para validar um respectivo número solicitado, sendo o retorno dessa função Verdadeiro (é um número primo) ou Falso (não é um número primo)

Sabendo que os números primos possuem a regra que os definem:

Um número primo é aquele que é divisível por apenas 2 números, 1 e por ele mesmo. Sabe-se também que o número 1, não é primo pois possui apenas um único divisor. O único número par que é primo é o número 2.

Tendo em mente o conhecimento geral sobre os números primos, implementei 2 versões de validação de número primo, a primeira versão uma varredura, dentro do universo dos números ímpares (verificaNumeroPrimoV1), inicialmente sem nenhuma otimização, porém após algumas leituras evoluí até a situação que será apresentada a seguir. Também implementei uma segunda versão de validação dos números primos dentro do universo de números ímpares (verificaNumeroPrimoV2), onde neste realizado uma validação verificando se o resto da divisão é zero e o divisor é diferente do número a ser validado, o que define que o número não é primo, e uma segunda checagem que valida se o Quociente da divisão é menou ou igual ao divisor, o que define que este número é um número primo.

Como comentei, após algumas leituras realizei umas otimizações, dentre elas:

– delimitei a validação até a raíz quadrada do número a ser validado

– verificação se o número possuí raíz quadrada, o que define que não é um número primo

– validação se o quociente da divisão do próximo número ímpar após a raíz quadrada do número é inferior ou igual ao divisor, o que define que o número validado é primo.

Com essas otimizações obtive o respectivo algoritmo:

 

Link do arquivo raw, no final do arquivo, tem um array com os números primos encontrados de 1 a 100000

 

Links de referência: 

Algoritmo em C

Como identificar se um número é primo ou não? (verificação do quociente da divisão) 

Crivo de Eratóstenes

 

, ,

Este post foi escrito por:

- que escreveu 500 post(s).


Entre em contato

  • Muito bom!

  • Rodrigo

    Na boa, olha a forma que implementei esse problema: (desculpa a falta de identação)
    print (“Esse programa lista todos os números primos até o limite que usuário o desejar.n”)

    x=int(input(“Até que número deseja que eu teste? “))
    #pede ao usuario o valor e converte a string em inteiro

    print(“nOs números primos até %s são: ” % x)

    for j in range(1, x+1):
    # vai usar todos os valores de 1 até o valor x definido pelo usuário

    y=1
    # Define a variável y como 1 que é o elemento neutro da multiplicação.

    for i in range(2, int(j**0.5+1)):
    # para cada j ele testa todos os restos possiveis das divisões até dividir pela raiz quadrada + 1.

    y=(j%i)*y
    # Multiplica todos os restos entre si.

    if y>0:
    # caso tenha havido qualquer divisão interia, sem resto, a multiplicação terá resultado zero. Se for primo será diferente de zero.

    print (j, end= “, “)

    # mostra a lista dos que foram primos (produto de restos diferentes de zero).
    #O parâmetro end= “, ” serve para não listar um em baixo do outro e coloca virgula e espaço entre os elementos.

  • Fail

    Desde quando o numero 45 ( ou qualquer 1 terminado em 5) é primo? Seu programa esta errado!

  • Pingback: maquetas de madera para armar()

  • Reginaldo Barros da Cunha

    Amigo sou iniciante em TI estou fazendo um curso básico de python e tenho que desenvolver a seguinte função: Escreva a função maior_primo que recebe um número inteiro maior ou igual a 2 como parâmetro e devolve o maior número primo menor ou igual ao número passado à função

    Note que

    maior_primo(100) deve retornar 97

    maior_primo(7) deve retornar 7

    Será que poderia me ajudar??

    • Joice Regina Simões

      Oi Reginaldo

      Consegui fazer até aqui no momento (também tenho dúvidas). No entanto, ele retorna somente o numero primo. Não consegui ainda fazer retornar o maior_primo conforme solicitado no enunciado. Quem sabe alguém daqui não nos esclareça.
      Segue:
      def maior_primo(n):

      if n == 2 or (n != 1 and n % 2 == 1):
      é_primo = True
      return n
      else:
      é_primo = False

      def main():
      divisor = 3
      while divisor < n // 2 and é_primo:
      if n % divisor == 0:
      é_primo = False
      divisor += 2
      while n != é_primo:
      n = n – 1
      print (n)