10mi de dígitos - Como calcular

Mattheus Henrique · 14-09-2004, 11:12

Alguém me dá uma luz de como tratar números de 10milhões de caracteres?
Pode ser C/C++, PHP, Python, Shell Script, qualquer coisa

Lgub · 14-09-2004, 11:48

Bem, você vai ter que usar um vetor, e alocado dinamicamento pelo que me parece:
A matematica é mais ou menos essa aqui

Soma)

Código:

v1[5]={1,2,3,4,5}, v2[5]={6,5,4,3,2}.
for( int cont =4;cont==0;cont--)
 resultado[cont]=v1[cont]+v2[cont];

Esse codigo acima tem um problema se a soma der mais de 9 é necessário passa o valor para a proxima posição, coisa que o codigo acima não faz.
mais a ideia é essa.

Mattheus Henrique · 14-09-2004, 14:15

Então deixa eu explicar o meu raciocínio que fica mais fácil, daí todo mundo ajuda.
Quero achar um número de 10milhões de caracteres que é primo e é dado pela fórmula

Código:

2 elevado a X menos um

Alguém pode me ajudar?

Lgub · 14-09-2004, 14:37

Vc quer algo realmente dificil, hiem, mais 10 milhoes de caracter não é muita coisa não?

fdbelo · 14-09-2004, 14:48

Bem, primeiro você vai ter que gerar os números em sequencia, até achar o que você quer, vai ter que ter um loop que faça o X até um certo número desejado.

Depois vai ter que testar para ver se cada um desses números é primo, alguém conhece algum algoritmo matemático que faça essa verificação? Se não existir vai ficar complicado, pois será necessário ver se o número só é divisível por ele mesmo e por um, ou seja, vai ter que testar todos os números abaixo dele e ver se a divisão dá algo exato (sem casas decimais), se der, ele não é primo, e dá pra partir para o próximo número. Vai demorar um bocado para processar isso.

Mattheus Henrique · 14-09-2004, 15:09

Citação:

Postado Originalmente por Lgub

Vc quer algo realmente dificil, hiem, mais 10 milhoes de caracter não é muita coisa não?

Hehe, vai me abrir possibilidades 8)

Citação:

Bem, primeiro você vai ter que gerar os números em sequencia, até achar o que você quer, vai ter que ter um loop que faça o X até um certo número desejado.

Depois vai ter que testar para ver se cada um desses números é primo, alguém conhece algum algoritmo matemático que faça essa verificação? Se não existir vai ficar complicado, pois será necessário ver se o número só é divisível por ele mesmo e por um, ou seja, vai ter que testar todos os números abaixo dele e ver se a divisão dá algo exato (sem casas decimais), se der, ele não é primo, e dá pra partir para o próximo número. Vai demorar um bocado para processar isso.

Certo, obrigado em gente, quando eu avançar eu vou postando

Mattheus Henrique · 14-09-2004, 15:51

Pronto:
Depois de uma googlada eu achei isso, mas to com dificuldade pra passar pra C/C++

Código:

Etapa 1. Aliste os inteiros, começando com "2". 
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 
Etapa 2. Marque o primeiro número na lista como a prima. 
Primos conhecidos: 2 
Lista principal: 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 
Etapa 3. A etapa através da lista principal que elimina todos os múltiplos do número adicionado apenas à lista do sabido apronta. Sabido apronta: lista de 2 canos principais: 3 5 7 9 11 13 15 17 19 Etapa 4. Se o número o maior na lista principal for menos do que o quadrado do número o maior na lista principal sabida, marque todos os números na lista principal como a prima; se não, retorne a etapa 2. Desde que 19 são mais grandes do que o quadrado de 2 (4), nós retornamos a etapa 2: Sabido apronta: 2 lista de 3 canos principais: 5 7 9 11 13 15 17 19 Então etapa 3: Sabido apronta: 2 lista de 3 canos principais: 5 7 11 13 17 19 19 são mais grandes do que o quadrado de 3 (9), assim que nós retornamos a etapa 2: Sabido apronta: 2 3 lista de 5 canos principais: 7 11 13 17 19 Então etapa 3 (nenhumas mudanças a uma ou outra lista). 19 são menos do que o quadrado de 5 (25), assim que a lista restante é principal. 
RESULTADO: Apronta na escala 2 a 20 são: 2. 3, 5, 7, 11, 13, 17, 19.

Tava sem tempo dai eu pus no babelfish, mas o link é esse http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

fdbelo · 14-09-2004, 16:13

Acho que o maior problema de usar esse algoritmo, é que seria necessário criar um vetor com 10 elevado a 10 milhões de caracteres. Ou seja, inviável. Como vc sabe que o número é na forma "2 elevado a X - 1" acho melhor fazer da seguinte forma:

1) Faça X elevado a um valor inicial (por exemplo 3), o número que você vai ter é 8. Falta testar se ele é primo.
2) Um número é primo quando ele só é divisível por 1 e ele mesmo, então faça um loop que teste se ele é divisível por algum número entre 2 (incluindo) e ele mesmo menos um.
3) Se achar um número pelo qual ele é divisível, pode parar, pois ele não é primo, incremente o seu X, e recomece.

Mattheus Henrique · 14-09-2004, 16:27

Acho que é meio impossível

Eu queria é achar um primo de mersenne, de 10mi, mas tá muito complicado, então tá bom como tá.
Valeu a todos

fdbelo · 14-09-2004, 16:38

Se me lembro bem, tem um teorema que diz que se 2n - 1 é primo então n é primo. Isso já facilitaria bastante os cálculos, que ainda assim seria complexos (na verdades não complexos, e sim dispendiosos, :lol: )

Primo de mersenne? Você tá querendo achar o maior número primo existente é? Sabia que o prime95 que a gente tanto usa para testar over, na verdade é destinado a achar o maior número primo existente ainda não descoberto?

fdbelo · 14-09-2004, 16:42

Ahhh, perambulando na internet um pouco achei um texto interessante sobre o assunto: http://www.uniandrade.br/simposio/pdf/mat104.pdf

Mattheus Henrique · 14-09-2004, 17:37

Citação:

Postado Originalmente por fdbelo

Se me lembro bem, tem um teorema que diz que se 2n - 1 é primo então n é primo. Isso já facilitaria bastante os cálcu...

Sabia sim

Tem o mprime pro linux mas eu queria fazer o meu

pulsar · 14-09-2004, 18:03

Se um número não é divisível (se a divisão tem resto!) por nenhum dos algarismos até aquele que compõe sua raiz quadrada menos a mantissa então ele é primo.

Entenderam? Vou dar uns exemplos:

x = 71
sqrt(71) = 8.4261497732 (mantissa é 0.4261497732)
Se 71 não for divisível por 2, 3, 4, 5, 6, 7 ou 8 então é primo.

Mas aí você cai no problema de achar um bom algoritmo para o cálculo da raiz quadrada.

Outra coisa, como assim o "maior número primo existente"? Se o conjunto dos números naturais é infinito como garantir que encontramos o "maior número primo"?

pulsar · 14-09-2004, 18:16

Opa, agora que eu li o "ainda não encontrado"! Então está tudo certo!

fdbelo · 15-09-2004, 9:58

Acho que outro grande problema também de programar algo desse padrão, é que a maioria das linguagens (se não todas) não estão preparadas para trabalhar com número tão grandes (10mi de dígitos no caso). Acho que C trabalho no máximo com 64 bits (long long), e 2 elevado a 64 vai ser 18446744073709551616, 20 dígitos, bem menos do que 10 mi de dígitos

. Ou seja, o programa vai ter que utilizar um métodos para separar em outras variáveis as partes do número.

Concordam comigo, ou eu estou viajando na maionese?

Ricardo de Castilho · 15-09-2004, 11:29

TuiTo · 15-09-2004, 16:12

Eae.. Esse algoritmo citado (marcar um número e remover os múltiplos dele), eu implementei em C, faz um tempinho.. qualquer coisa manda uma MP. Tu informa um N e ele te mostra todos os números primos entre 2 e N... e faz isso bem rápido.. :lol: entretanto, ele cria um vetor e vai marcando as posições... (ou seja, se botar algo tipo 300 mil, vai criar um vetor de 300 mil posições).. pensei em implementar utilizando uma lista... mas acho q vai dar um overhead da po*** qndo começar a apagar os nodos :S qualquer hora eu tenho pra ver como fica..

Números primos eh uma das coisas que eu gosto.. eu to tentando achar uma fórmula fechada para calcular números primos... tipo: f(n) = n-ésimo primo... mas ta mto ****.. to usando o Maple pra desenhar uma função aproximadora... peguei os 50 primeiros números primos e plotei-os... eles seguem um certo padrão, mas não consigo enxergar como eh....

jqueiroz · 15-09-2004, 17:51

Mattheus, talvez ajude se vc mudar de base: trazendo pra base binária, esse número "2 elevado a X menos 1" é um número com exatamente X bits 1... ou uma string de bits.

Essa string de bits, se vc definir X como 10 milhões, vai ocupar 1,25 milhões de caracteres (8 bits/caracter). Já diminuiu bastante, né?

Pensando bem agora, lembro de ter visto alguma coisa como uma "biblioteca de precisão arbitrária" em Perl.

pulsar · 15-09-2004, 21:25

TuiTo,

Se você achar uma função f(x) tal que para todo x, y é primo, ganhará um bom dinheiro.

Outro problema que envolve números primos, e esbarra no que você falou além de quem resolver poder reivindicar a singela quantia de um milhão de dólares no Instituto Clay, é a Hipótese de Riemann:

http://www.claymath.org/millennium/Riemann_Hypothesis/

TuiTo · 15-09-2004, 22:26

Eh, eu to sabendo q dá uma boa grana... :twisted: :twisted: :twisted:

mas a minha função não funciona para todos os valores... dentro de um dado intervalo, se tu truncares o y da função, tu tem um número primo.... Testei com alguns e funciona.. mto bacana.. mas depois de um certo valor, ele se distancia... :?

Soh 50 números plotados no maple... de repente com 1000 números primos fica mais fácil de enxergar um padrão.... mas se vcs olharem, soh com 50, da pra ver um certo comportamento de tempos em tempos.. eh mto curioso...teria q ter uma idéia de qnto em qnto tempo esse padrão se repete... daí tentar trabalhar em cima...

14-09-2004, 11:12	#1 (permalink)
Mattheus Henrique Ubbergeek Registrado em: Jul 2003 Mensagens: 4.512 Reputação: 24	10mi de dígitos - Como calcular Alguém me dá uma luz de como tratar números de 10milhões de caracteres? Pode ser C/C++, PHP, Python, Shell Script, qualquer coisa

14-09-2004, 11:48	#2 (permalink)
Lgub Super Participante Registrado em: Dec 2001 Mensagens: 937 Reputação: 22	Bem, você vai ter que usar um vetor, e alocado dinamicamento pelo que me parece: A matematica é mais ou menos essa aquiSoma) Código: v1[5]={1,2,3,4,5}, v2[5]={6,5,4,3,2}. for( int cont =4;cont==0;cont--) resultado[cont]=v1[cont]+v2[cont]; Esse codigo acima tem um problema se a soma der mais de 9 é necessário passa o valor para a proxima posição, coisa que o codigo acima não faz. mais a ideia é essa. __________________ Linux User:#326216 Intel I7 - 920 - 6G DDR3 Tripple Channel @1600 - Geforce 285 1G. Programador ADVPL(Fazer o que é o que ta pagando as contas no momento...)

14-09-2004, 14:15	#3 (permalink)
Mattheus Henrique Ubbergeek Registrado em: Jul 2003 Mensagens: 4.512 Reputação: 24	Então deixa eu explicar o meu raciocínio que fica mais fácil, daí todo mundo ajuda. Quero achar um número de 10milhões de caracteres que é primo e é dado pela fórmula Código: 2 elevado a X menos um Alguém pode me ajudar?

14-09-2004, 14:37	#4 (permalink)
Lgub Super Participante Registrado em: Dec 2001 Mensagens: 937 Reputação: 22	Vc quer algo realmente dificil, hiem, mais 10 milhoes de caracter não é muita coisa não? __________________ Linux User:#326216 Intel I7 - 920 - 6G DDR3 Tripple Channel @1600 - Geforce 285 1G. Programador ADVPL(Fazer o que é o que ta pagando as contas no momento...)

14-09-2004, 14:48	#5 (permalink)
fdbelo Tô em todas Registrado em: Jul 2001 Localização: Ludwigsburg - Alemanha Mensagens: 1.927 Reputação: 24	Bem, primeiro você vai ter que gerar os números em sequencia, até achar o que você quer, vai ter que ter um loop que faça o X até um certo número desejado. Depois vai ter que testar para ver se cada um desses números é primo, alguém conhece algum algoritmo matemático que faça essa verificação? Se não existir vai ficar complicado, pois será necessário ver se o número só é divisível por ele mesmo e por um, ou seja, vai ter que testar todos os números abaixo dele e ver se a divisão dá algo exato (sem casas decimais), se der, ele não é primo, e dá pra partir para o próximo número. Vai demorar um bocado para processar isso. __________________ \|Dell Inspiron 6400\|Intel Core 2 Duo T7200 (2GHz) \|2GB DDR-2 RAM\|120GB HD (5.400)\|15.4" Wide True Life (1280x800)\|Bluetooth integrado, bateria 9 células e mais umas coisinhas \| Folding@Home Member!

		FórumGdH > Profissional > Programação, scripts, web e banco de dados
10mi de dígitos - Como calcular

14-09-2004, 16:13	#8 (permalink)
fdbelo Tô em todas Registrado em: Jul 2001 Localização: Ludwigsburg - Alemanha Mensagens: 1.927 Reputação: 24	Acho que o maior problema de usar esse algoritmo, é que seria necessário criar um vetor com 10 elevado a 10 milhões de caracteres. Ou seja, inviável. Como vc sabe que o número é na forma "2 elevado a X - 1" acho melhor fazer da seguinte forma: 1) Faça X elevado a um valor inicial (por exemplo 3), o número que você vai ter é 8. Falta testar se ele é primo. 2) Um número é primo quando ele só é divisível por 1 e ele mesmo, então faça um loop que teste se ele é divisível por algum número entre 2 (incluindo) e ele mesmo menos um. 3) Se achar um número pelo qual ele é divisível, pode parar, pois ele não é primo, incremente o seu X, e recomece. __________________ \|Dell Inspiron 6400\|Intel Core 2 Duo T7200 (2GHz) \|2GB DDR-2 RAM\|120GB HD (5.400)\|15.4" Wide True Life (1280x800)\|Bluetooth integrado, bateria 9 células e mais umas coisinhas \| Folding@Home Member!

14-09-2004, 16:27	#9 (permalink)
Mattheus Henrique Ubbergeek Registrado em: Jul 2003 Mensagens: 4.512 Reputação: 24	Acho que é meio impossível Eu queria é achar um primo de mersenne, de 10mi, mas tá muito complicado, então tá bom como tá. Valeu a todos

14-09-2004, 16:38	#10 (permalink)
fdbelo Tô em todas Registrado em: Jul 2001 Localização: Ludwigsburg - Alemanha Mensagens: 1.927 Reputação: 24	Se me lembro bem, tem um teorema que diz que se 2n - 1 é primo então n é primo. Isso já facilitaria bastante os cálculos, que ainda assim seria complexos (na verdades não complexos, e sim dispendiosos, :lol: ) Primo de mersenne? Você tá querendo achar o maior número primo existente é? Sabia que o prime95 que a gente tanto usa para testar over, na verdade é destinado a achar o maior número primo existente ainda não descoberto? __________________ \|Dell Inspiron 6400\|Intel Core 2 Duo T7200 (2GHz) \|2GB DDR-2 RAM\|120GB HD (5.400)\|15.4" Wide True Life (1280x800)\|Bluetooth integrado, bateria 9 células e mais umas coisinhas \| Folding@Home Member!

14-09-2004, 16:42	#11 (permalink)
fdbelo Tô em todas Registrado em: Jul 2001 Localização: Ludwigsburg - Alemanha Mensagens: 1.927 Reputação: 24	Ahhh, perambulando na internet um pouco achei um texto interessante sobre o assunto: http://www.uniandrade.br/simposio/pdf/mat104.pdf __________________ \|Dell Inspiron 6400\|Intel Core 2 Duo T7200 (2GHz) \|2GB DDR-2 RAM\|120GB HD (5.400)\|15.4" Wide True Life (1280x800)\|Bluetooth integrado, bateria 9 células e mais umas coisinhas \| Folding@Home Member!

14-09-2004, 18:03	#13 (permalink)
pulsar Membro Senior Registrado em: Apr 2003 Localização: Rio de Janeiro Mensagens: 342 Reputação: 20	Se um número não é divisível (se a divisão tem resto!) por nenhum dos algarismos até aquele que compõe sua raiz quadrada menos a mantissa então ele é primo. Entenderam? Vou dar uns exemplos: x = 71 sqrt(71) = 8.4261497732 (mantissa é 0.4261497732) Se 71 não for divisível por 2, 3, 4, 5, 6, 7 ou 8 então é primo. Mas aí você cai no problema de achar um bom algoritmo para o cálculo da raiz quadrada. Outra coisa, como assim o "maior número primo existente"? Se o conjunto dos números naturais é infinito como garantir que encontramos o "maior número primo"?

14-09-2004, 18:16	#14 (permalink)
pulsar Membro Senior Registrado em: Apr 2003 Localização: Rio de Janeiro Mensagens: 342 Reputação: 20	Opa, agora que eu li o "ainda não encontrado"! Então está tudo certo!

15-09-2004, 9:58	#15 (permalink)
fdbelo Tô em todas Registrado em: Jul 2001 Localização: Ludwigsburg - Alemanha Mensagens: 1.927 Reputação: 24	Acho que outro grande problema também de programar algo desse padrão, é que a maioria das linguagens (se não todas) não estão preparadas para trabalhar com número tão grandes (10mi de dígitos no caso). Acho que C trabalho no máximo com 64 bits (long long), e 2 elevado a 64 vai ser 18446744073709551616, 20 dígitos, bem menos do que 10 mi de dígitos . Ou seja, o programa vai ter que utilizar um métodos para separar em outras variáveis as partes do número. Concordam comigo, ou eu estou viajando na maionese? __________________ \|Dell Inspiron 6400\|Intel Core 2 Duo T7200 (2GHz) \|2GB DDR-2 RAM\|120GB HD (5.400)\|15.4" Wide True Life (1280x800)\|Bluetooth integrado, bateria 9 células e mais umas coisinhas \| Folding@Home Member!

15-09-2004, 11:29	#16 (permalink)
Ricardo de Castilho Ubbergeek Registrado em: Sep 2002 Localização: Ponta Grossa - PR Mensagens: 4.411 Reputação: 26

15-09-2004, 16:12	#17 (permalink)
TuiTo Super Participante Registrado em: Jan 2002 Localização: Porto Alegre/RS Idade: 28 Mensagens: 672 Reputação: 21	Eae.. Esse algoritmo citado (marcar um número e remover os múltiplos dele), eu implementei em C, faz um tempinho.. qualquer coisa manda uma MP. Tu informa um N e ele te mostra todos os números primos entre 2 e N... e faz isso bem rápido.. :lol: entretanto, ele cria um vetor e vai marcando as posições... (ou seja, se botar algo tipo 300 mil, vai criar um vetor de 300 mil posições).. pensei em implementar utilizando uma lista... mas acho q vai dar um overhead da po* qndo começar a apagar os nodos :S qualquer hora eu tenho pra ver como fica.. Números primos eh uma das coisas que eu gosto.. eu to tentando achar uma fórmula fechada para calcular números primos... tipo: f(n) = n-ésimo primo... mas ta mto *.. to usando o Maple pra desenhar uma função aproximadora... peguei os 50 primeiros números primos e plotei-os... eles seguem um certo padrão, mas não consigo enxergar como eh.... __________________ / Yew Woodie is: C2D E8400 P5K SE Seagate 500GB Sata II 4120B Ati HD4850 512 MB Kingston HX2GB DDR2 800 XP PRO SyncMaster 2232BW+ X-Fi Platinum ST420W Casemall CP202L */ Dell D520

15-09-2004, 17:51	#18 (permalink)
jqueiroz Highlander Registrado em: May 2002 Localização: Tijuca/RJ Idade: 9 Mensagens: 87.724 Reputação: 778	Mattheus, talvez ajude se vc mudar de base: trazendo pra base binária, esse número "2 elevado a X menos 1" é um número com exatamente X bits 1... ou uma string de bits. Essa string de bits, se vc definir X como 10 milhões, vai ocupar 1,25 milhões de caracteres (8 bits/caracter). Já diminuiu bastante, né? Pensando bem agora, lembro de ter visto alguma coisa como uma "biblioteca de precisão arbitrária" em Perl. __________________ Visite Quepolis (link de indicação) \| "chmod 777 nunca ajudou ninguém" (c) 2002-2010 JQueiroz/FGdH CCNP: √ ² CCSI: □ \| Conheça o Novo Bebuns

15-09-2004, 21:25	#19 (permalink)
pulsar Membro Senior Registrado em: Apr 2003 Localização: Rio de Janeiro Mensagens: 342 Reputação: 20	TuiTo, Se você achar uma função f(x) tal que para todo x, y é primo, ganhará um bom dinheiro. Outro problema que envolve números primos, e esbarra no que você falou além de quem resolver poder reivindicar a singela quantia de um milhão de dólares no Instituto Clay, é a Hipótese de Riemann: http://www.claymath.org/millennium/Riemann_Hypothesis/

15-09-2004, 22:26	#20 (permalink)
TuiTo Super Participante Registrado em: Jan 2002 Localização: Porto Alegre/RS Idade: 28 Mensagens: 672 Reputação: 21	Eh, eu to sabendo q dá uma boa grana... :twisted: :twisted: :twisted: mas a minha função não funciona para todos os valores... dentro de um dado intervalo, se tu truncares o y da função, tu tem um número primo.... Testei com alguns e funciona.. mto bacana.. mas depois de um certo valor, ele se distancia... :? Soh 50 números plotados no maple... de repente com 1000 números primos fica mais fácil de enxergar um padrão.... mas se vcs olharem, soh com 50, da pra ver um certo comportamento de tempos em tempos.. eh mto curioso...teria q ter uma idéia de qnto em qnto tempo esse padrão se repete... daí tentar trabalhar em cima... __________________ /* Yew Woodie is: C2D E8400 P5K SE Seagate 500GB Sata II 4120B Ati HD4850 512 MB Kingston HX2GB DDR2 800 XP PRO SyncMaster 2232BW+ X-Fi Platinum ST420W Casemall CP202L */ Dell D520

Opções do Tópico
Exibir Versão para Impressão Envie essa página por e-mail