Super números primos

Secção dedicada à linguagem de programação favorita dos quarkianos: Python!

Super números primos

Mensagempor Bruno Oliveira em Quinta Mar 15, 2012 11:08 am

Aqui vai mais um problema para treino pitónico!!

Super-primos

Um número primo, como já todos sabem, é um número que só admite dois divisores, ele próprio e a unidade!

Como um subset do conjunto dos números primos, podemos definir os super-primos, que são números que:
[*] são primos
[*] os subnúmeros obtidos após truncar todos os digitos a partir da direita do número, são, eles próprios, primos.

Exemplo:

233 é um super-primo, pois:

233 é primo.
23 (3) é primo.
2 (33) é primo.

A vossa tarefa é escreverem um programa que vos calcule todos os números super-primos de comprimento menor ou igual a 8. :wink:
e^{ix}=cos x + i\,sin x
Avatar do utilizador
Bruno Oliveira
top-Quark!
top-Quark!
 
Mensagens: 1553
Registado: Quarta Nov 14, 2007 10:19 pm
Localização: Lisboa

Re: Super números primos

Mensagempor ruifm em Quinta Mar 15, 2012 10:46 pm

Bruno Oliveira Escreveu:Aqui vai mais um problema para treino pitónico!!

Super-primos

Um número primo, como já todos sabem, é um número que só admite dois divisores, ele próprio e a unidade!

Como um subset do conjunto dos números primos, podemos definir os super-primos, que são números que:
[*] são primos
[*] os subnúmeros obtidos após truncar todos os digitos a partir da direita do número, são, eles próprios, primos.

Exemplo:

233 é um super-primo, pois:

233 é primo.
23 (3) é primo.
2 (33) é primo.

A vossa tarefa é escreverem um programa que vos calcule todos os números super-primos de comprimento menor ou igual a 8. :wink:

é so escrever, não é preciso saber o resultado xD? eu posso escrever um com brute force, mas não garanto que seja rapido.... :XD
off topic: SPOORRTTTING!!!!
ja posto aqui a minha 1st attempt
"Everything is determined, the beginning as well as the end, by forces over which we have no control." - Albert Einstein
Avatar do utilizador
ruifm
down-Quark!
down-Quark!
 
Mensagens: 205
Registado: Segunda Jan 16, 2012 12:04 am
Localização: Lisboa - IST

Re: Super números primos

Mensagempor Bruno Oliveira em Quinta Mar 15, 2012 11:06 pm

Resultados são apenas um produto secundário do racíocinio por detrás do algoritmo!! :wink:

Duvido que consigas sequer correr um brute force, repara que o mínimo número com 8 dígitos de comprimento é 10000000. (10 milhões)

Para percorreres todos os números de comprimento menor ou igual que 8 isso implicaria fazeres um ciclo de 1 até 99999999, isto é, x in range(1, 100000000), o que, convenhamos, é puxadote, mesmo para uma linguagem compilada... :P

OT: GRANDE SPORTING!!!! ORGULHO DE LEÃO EHEH :wink:
e^{ix}=cos x + i\,sin x
Avatar do utilizador
Bruno Oliveira
top-Quark!
top-Quark!
 
Mensagens: 1553
Registado: Quarta Nov 14, 2007 10:19 pm
Localização: Lisboa

Re: Super números primos

Mensagempor ruifm em Sexta Mar 16, 2012 5:55 pm

consegui qualquer coisa, parece estar certo mas fica extremamente lento quando se tenta atingir o target. de qualquer forma, foi o mais rapido que consegui
Código: Seleccionar Todos
k=100000
conjunto=range(3,k,2)
conjunto.insert(0,2)

for i in xrange(len(conjunto)):
    if i<len(conjunto):
        e=str(conjunto[i])
        if len(e)==1:
            print conjunto[i]
        else:
            for s in xrange(2,len(e)):
                if int(e[:s]) in conjunto and int(e[0]) in conjunto:
                    print conjunto[i]
        conjunto=conjunto[:i+1]+filter(lambda hy: y%conjunto[i]!=0, conjunto[i:])

a ultima linha é a linha do crivo.
o resto é a resolução do problema da forma mais simples possivel:
transformar cada elemento numa string
percorrer toda a string a partir da esquerda e ver se esse elemento existe no 'conjunto'. se sim, faz print

EDIT: se ha um metodo alternativo sem ser percorrer pelo menos todos os impares, não estou a ver qual é. eu sei que a 'densidade' de primos a volta de um numero é proporcional é razao 1/logx, sendo x esse numero. Mas isso são so probabilidades. Não posso arriscar por um step maior em numeros de elevada ordem de grandeza, poderia passar por cima de um primo sem querer :o
última vez editado por ruifm s Sábado Mar 17, 2012 12:05 pm, editado 1 vez no total
"Everything is determined, the beginning as well as the end, by forces over which we have no control." - Albert Einstein
Avatar do utilizador
ruifm
down-Quark!
down-Quark!
 
Mensagens: 205
Registado: Segunda Jan 16, 2012 12:04 am
Localização: Lisboa - IST

Re: Super números primos

Mensagempor Bruno Oliveira em Sexta Mar 16, 2012 8:32 pm

A densidade dos números primos até x ser proporcional a 1/log(x), além de ser uma aproximação (o que faria de um método que usasse esse dado, um método heurístico), envolve matemática muito mesmo muito complexa (função zeta de Riemann, passo a redundância :P ) e não é de todo o caminho a seguir aqui.

Neste tipo de problemas, é melhor gerar, em vez de filtrar... Isto é, em vez de considerar todos os primos, vamos "construir" apenas os que nos interessam.

Para isso, temos de nos aperceber de uma característica-chave deste problema? Alguém a descobre? :roll:
e^{ix}=cos x + i\,sin x
Avatar do utilizador
Bruno Oliveira
top-Quark!
top-Quark!
 
Mensagens: 1553
Registado: Quarta Nov 14, 2007 10:19 pm
Localização: Lisboa

Re: Super números primos

Mensagempor ruifm em Sexta Mar 16, 2012 10:13 pm

eu consigo gerar numeros primos pela sua definiçao, desta forma:
Código: Seleccionar Todos
def primes(s):
    n=2
    if s == 2 or s==3:
        return True
       elif s==1 or s==4:
        return False
    else:
        while n<s-1:
            n += 1
            if s%n==0:
                control=False
            else:
                control=True
            if control==False:
                return False
        return True

desta forma posso fazer um loop que verifique numero a numero se ele é primo ou não. so que não vejo como isso pode ser util, porque verificar numero a numero é mais lento que filtrar...
"Everything is determined, the beginning as well as the end, by forces over which we have no control." - Albert Einstein
Avatar do utilizador
ruifm
down-Quark!
down-Quark!
 
Mensagens: 205
Registado: Segunda Jan 16, 2012 12:04 am
Localização: Lisboa - IST

Re: Super números primos

Mensagempor Bruno Oliveira em Domingo Mar 18, 2012 10:20 pm

O truque para resolver este problema, consiste em gerar os números pretendidos, em vez de os filtrar de uma lista de todos os primos até 100000000, que como já vimos seria um processo muito lento e que consumiria imensa memória... :roll:

No entanto, existem algumas observações que tornam a resolução do problema muito fácil.

Observação 1: Todos os super-primos só podem começar por 2, 3, 5 ou 7

Isto é óbvio, visto que se queremos considerar apenas o último dígito, resultante do "corte" sucessivo dos dígitos a partir da direita do número original, para esse dígito ser primo só pode ser 2, 3, 5 ou 7.

Observação 2: Os dígitos que estão presentes no super-primo não podem nunca ser dígitos pares

Isto é, não podemos nunca ver os dígitos 0, 2, 4, 6 ou 8 no nosso super-primo, pois isso faria com que um dos sub-numeros não fosse primo.

Tendo estas observações em consideração, podemos usar o que se chama de Depth First Search com Iterative Deepning para resolver o problema.

O que um Depth First search faz, é gerar todos os números até um dado limite, e ver quais deles verificam a condição de serem primos.

Para os de comprimento 2, teremos os números:

[21 23 25 27 29 31 33 35 37 39 51 53 55 57 59 71 73 75 79]

Do conjunto acima, escolhe-se os que são primos e usando a lista resultante, criamos agora os super-primos de comprimento 3...

Iterativamente, podemos fazer o mesmo até comprimento 8.

Um código muito simples que implementa isto é:

Código: Seleccionar Todos
from math import *

def is_prime(N):
    if N == 2:
        return True

    if N%2 == 0 and N != 2:
        return False
    else:
        limit = floor(sqrt(N));
        while N % limit != 0:
            limit-=1
        if limit == 1:
            return True
    return False

def superprime(L):
    J = []
    digits = ["1","3","5","7","9"]
    for i in range(0, len(L)):
        for j in range(0,len(digits)):
            if is_prime(int(L[i]+digits[j])):
                J.append(L[i]+digits[j])
    return J

def superprime_ID(n):
    T = ["2","3","5","7"]
    if n == 1:
        return T
    else:
        x = 2
        while x < n+1:
            U = superprime(T)
            x+=1
            T = U
    return T


Onde superprime aplica o principio de DFS e superprime_ID(n) devolve todos os super-primos de comprimento igual a n.

:)
e^{ix}=cos x + i\,sin x
Avatar do utilizador
Bruno Oliveira
top-Quark!
top-Quark!
 
Mensagens: 1553
Registado: Quarta Nov 14, 2007 10:19 pm
Localização: Lisboa


Voltar para Pitónica

Quem está ligado

Utilizadores a navegar neste fórum: Nenhum utilizador registado e 1 visitante

cron