Tópico: Cientistas definem número primo com 13 milhões de dígitos

[Unknown]

Cientistas definem número primo com 13 milhões de dígitos
 
Matemáticos americanos se qualificaram para receber um prêmio de US$ 100 mil por encontrar um número primo - que só pode ser dividido por um e por si mesmo – com quase 13 milhões de dígitos.

O prêmio da Electronic Frontier Foundation (EFF) era oferecido há quase dez anos para a primeira equipe de cientistas capazes de encontrar um número primo de Mersenne – em homenagem ao matemático francês Marin Mersenne, que os popularizou no século 17 – com mais de 10 milhões de dígitos.

Os primos de Mersenne seguem a fórmula 2 elevado à potência "p" menos 1, sendo que "p" é em si um número primo.

No fim do mês passado, um computador na Universidade da Califórnia definiu o 45º primo de Mersenne conhecido: 2 elevado à 43.112.609ª potência menos 1, com 12.978.189 de dígitos.

No dia 6 de setembro, o 46º primo de Mersenne conhecido foi encontrado por uma equipe em Langenfeld, perto de Colônia, na Alemanha: 2 elevado à 37.156.667ª potência menos 1, com 11.185.272 de dígitos.

O numeral encontrado pelos alemães foi o primeiro primo de Mersenne a ser descoberto fora de ordem desde que os matemáticos Colquitt e Welsh definiram 2 elevado à 110.503ª potência menos 1.

A busca por um primo de Mersenne com mais de dez milhões de dígitos já durava quase dez anos.

Cientistas dizem que o exercício tem a importância indireta de abrir espaço para a criação de teoremas e hipóteses matemáticas, promover pesquisas cooperativas na internet e incentivar o gosto pela pesquisa científica, entre outros efeitos.

Os coordenadores das duas pesquisas, Edson Smith e Hans-Michael Elvenich, faziam parte da rede Gimps (iniciais em inglês para Grande Busca de Primos de Mersenne na Internet), formada em 1996 para descobrir "agulhas num palheiro" – números primos gigantescos – operando 29 trilhões de cálculos simultâneos.

Do total da recompensa, US$ 50 mil irão para os matemáticos da UCLA, que venceram a corrida proposta pela EFF, outros US$ 25 mil serão doados para entidades de caridade, e o restante, dividido entre os descobridores dos primos de Mersenne anteriores.

http://www.bbc.co.uk/portuguese/reporterbbc/story/2008/09/080929_primo10milhoes_pu.shtml

[Tupac]

putz, achei que tinha sido na "mão"...

[SnowRaptor]

Haja poder de processamento pra fatorar essa birosca

[Pregador]

Qual a utilidade disso?

[SnowRaptor]

Criptografia. Esses números primos ogros servem como chaves públicas e privadas pra criptografia. Por exemplo: Eu tenho um arquivo secreto que quero compartilhar com você. Aí eu criptografo esse arquivo usando como chave uma potência de um número que é produto de dois primos grandes. Eu sei os dois números primos e compartilho apenas um dos números primos com você. Sabendo esse número primo, você consegue desencriptar a minha mensagem, mas não consegue descobrir o outro número primo (pois você teria de fatorar o número gigante, que demora), assim não consegue enviar mensagens fingindo que sou eu.

[FxF]

pois você teria de fatorar o número gigante, que demora

Esse é o princípio. O hacker só poderia deixar para uma futura geração...

[Eleitor de Mário Oliveira]

Qual a utilidade disso?

Além da aplicação direta prática que o SnowRaptor mostrou, esta competividade leva ao aprimoramento de hardware e software.

[Herf]

Já foi provada a impossibilidade de existir uma "fórmula dos primos"? (Como a expressão do termo geral de uma seqüência, que permite encontrar o x-ésimo termo da seqüência)

[SnowRaptor]

A coisa mais próxima disso são os primos de Mersenne, mas não é garantido. Nem todo número na forma com primo é necessariamente primo.

[Unknown]

A coisa mais próxima disso são os primos de Mersenne, mas não é garantido. Nem todo número na forma com primo é necessariamente primo.

[SnowRaptor]

Oopsie! My bad.

[Unknown]

Oopsie! My bad.

Na verdade foi até bom esse pequeno lapso porque notei algo que me deixou curioso. Na fórmula com primo e p ≠ 2, todos os resultados serão divisíveis por 3? Em caso afirmativo, como se prova isso?
Testei os primos de 3 até 61 e todos os resultados foram divisíveis por 3.

[Unknown]

Só por curiosidade, achei uma tabela com os 1000 primeiros números primos.

[Eleitor de Mário Oliveira]

Só por curiosidade, achei uma tabela com os 1000 primeiros números primos.

Grande coisa. Eu fiz um programa em C que calculou todos os primos entre 2 e 9872827:

http://www.filefactory.com/file/200d28/n/primos_pdf

[Tupac]

ixi... o Snow criou um monstro...

Oh não!! É o Primozilla....


aaaaahhhhhhhhrrrrggg

[SnowRaptor]

Grande coisa. Eu fiz um programa em C que calculou todos os primos entre 2 e 9872827:

Cadê o código-fonte?

Tinha uma época que eu ficava tentando otimizar meu programinha de primos pra competir com o primes que vinha com o debian

Aprendi bastante sobre otimização em tempo de compilação

[Eleitor de Mário Oliveira]

Grande coisa. Eu fiz um programa em C que calculou todos os primos entre 2 e 9872827:

Cadê o código-fonte?

Tinha uma época que eu ficava tentando otimizar meu programinha de primos pra competir com o primes que vinha com o debian

Aprendi bastante sobre otimização em tempo de compilação

Código: [Selecionar]

/*
Autor: Dante Cardoso Pinto de Almeida
Licenca: Dominio Publico - Public Domain
*/

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

int main(int argc, char *argv[])
{
 unsigned long int m, n, x, y, z, divisores, resto, loop, ver;
 int time1, time2;
 int rodando;
 rodando=1;
 while(rodando==1)/*Este laco mantem o programa rodando enquanto o usuario desejar*/
 {


  n=0;
  m=0;
  loop=0;


         while(n<2) /*Este laco impede a entrada de numeros menores que dois*/
                    {
                     printf("Entre com um numero inteiro maior ou igual a 2: ");
                     scanf("%d", &n);
                     }

         while(m<=n) /*Este laco impede a entrada de numeros menores que n*/
                     {
                      printf("Entre com um outro numero inteiro, maior que %d: ", n);
                      scanf("%d", &m);
                      }

         printf("Existem os seguintes primos no intervalo entre %d e %d:\n\n", n, m);
         time1 = clock();   /*Comeco da contagem do tempo de execucao*/

         for(x=n; x!=m; x++) /*Este laco varre todos os numeros do intervalo*/
                  {
                   divisores=0;
                   ver=1;
                   z=sqrt(x);

                    if((x%2==0 && x!=2)||(x%3==0 && x!=3)||(x%5==0 && x!=5)||(x%7==0 && x!=7)||(x%11==0 && x!=11)||(x%13==0 && x!=13)||(x%17==0 && x!=17)||(x%19==0 && x!=19)||(x%23==0 && x!=23)||(x%29==0 && x!=29))
                               {
                               ver=0;
                               }
 /*Estas duas condições fazem o programar pular os multiplos de 2, 3, 5, 7, 11, 13, 17, 19, 23 e 29*/
                    if(ver==1)
                              {
                              while(divisores<1) /*Este laco faz parar o teste de um numero assim que se verificar mais de dois divisores*/
                                  {
                                  for(y=1; y<z+1; y++) /*Este laço faz um numero ser dividido por todos antecessores de sua raiz quadrada*/
                                              {
                                              resto = x%y;
                                                 if(resto==0)
                                                      {
                                                      divisores++;  /*conta a quantidade de divisores*/
                                                      }
                                               }
                                   }
                              }
                    if (divisores==1) /*Esta condicao imprime todos os numeros verificados como primos*/
                       {
                       printf("%8ld", x);
                       loop++;   /*Contagem da quantidade de primos no intervalo*/
                       }
                  }
 printf("\nO que totaliza %d numeros primos dentro do intervalo.\n", loop);
 time2 = clock();
 printf("Levou %d unidades de tempo para executar o teste.",time2-time1);
 printf("\nDigite 1 para continuar rodando o programa.");

 printf("\nDigite qualquer outro numero para encerrar o programa.\n");
 scanf("%d", &rodando);
 }
 return 0;
}

[SnowRaptor]

A tag [code] é bem útil nessas horas

[SnowRaptor]

Quer uma sugestão?

Em vez de implementar na mão os primos como vc fez na linha 47, experimenta armazenar os números primos numa lista ligada e dividir só pelos primos. Vai beeem mais rápido e o código fica mais elegante

[Eleitor de Mário Oliveira]

A tag [code] é bem útil nessas horas

Satisfeito?

[SnowRaptor]

A tag [code] é bem útil nessas horas

Satisfeito?

Sim, agora otimiza essa merda

[Eleitor de Mário Oliveira]

Quer uma sugestão?

Em vez de implementar na mão os primos como vc fez na linha 47, experimenta armazenar os números primos numa lista ligada e dividir só pelos primos. Vai beeem mais rápido e o código fica mais elegante

Eu tô ligado! Mas listas ligadas é meu fraco. Nunca aprendi a usá-las. O pior é que eu sei o quanto elas são úteis.

Por exemplo, uma vez eu fiz um programa que estabeleza uma bijeção entre N e Q segundo o método do Cantor,

Código: [Selecionar]

//Autor: Dante Cardoso Pinto de Almeida
//Licença/License: Domínio Público/Public Domain
//Descrição: Este programa efetua uma função bijetora de N para Q


#include <stdio.h>
#include <stdlib.h>
#define MAX 100 //Altere este valor para expandir ou contrair o contradomínio
#define dom 25 //Altere este valor para expandir ou contrair o domínio

void selecao(int x, int y)//Esta rotina imprime as razões, eliminando as repetidas.
             {
             static int natural=2;
             int maior, menor;
             int divisor;
             short int verificador=0;
             if(x>y){
                     maior=x;
                     menor=y;
                     }else{maior=x; menor=y;}

              for(divisor=2; divisor<maior+1; divisor++)
                             {
                              if(maior%divisor==0 && menor%divisor==0)
                                      {
                                      verificador=1;
                                      break;
                                      }
                                       }
                 if(verificador==0)
                                    {
                                    printf("f(%d)=%d/%d\n", natural, maior, menor);
                                    natural++;   
                                     }
                                 
                }

int main(int argc, char *argv[])
{
  int i, j, k, l, m, n;
  int numeradores[MAX][MAX];
  int denominadores[MAX][MAX];
 
  for(i=0; i<MAX; i++)//Este laço preenche a matriz dos denominadores
           {
           for(j=0; j<MAX; j++)
                    {
                    denominadores[i][j]=j+1;       
                    }       
           }

  for(i=0; i<MAX; i++)//Este laço preenche a matriz dos numeradores
           {
           for(j=0; j<MAX; j++)
                    {
                    numeradores[i][j]=i+1;       
                    }       
           }
           

  printf("f(0)=0\n");
  printf("f(1)=1/1\n");
  l=0; m=0;       
  for(k=0; k<dom; k++) //Este laço percorre as matrizes em  zig-zag.
           {
           if(numeradores[l][m]%2!=0&&denominadores[l][m]==1)
                      {
                      l++;
                      selecao(numeradores[l][m], denominadores[l][m]);
                      }
                     
                   
                     
           if(numeradores[l][m]==1&&denominadores[l][m]%2==0)
                      {
                      m++;
                      selecao(numeradores[l][m], denominadores[l][m]);
                      }
                     
           if(numeradores[l][m]%2==0&&denominadores[l][m]==1)
                      {
                       do
                          {
                          m++;
                          l--;
                          selecao(numeradores[l][m], denominadores[l][m]);
                          }while(numeradores[l][m]!=1);
                       }   
                     
                     
           if(numeradores[l][m]==1&&denominadores[l][m]%2!=0)
                      {
                       do
                          {
                          m--;
                          l++;
                          selecao(numeradores[l][m], denominadores[l][m]);                                         
                          }while(denominadores[l][m]!=1);
                       }       
                       
                       
                                       
           }   
           
               
 
  system("PAUSE");
  return 0;
}

Pô! Seria bem mais elegante usar listas ligadas para alterar o tamanho das matrizes durante a execução do programa do que fazê-lo no código fonte.

[SnowRaptor]

Vamos pro tópico de programação: ../forum/topic=11443.100.html#msg366969

[Eremita]

Descobri que preciso aprender mais sobre programação. E sobre matemática.

Oopsie! My bad.

Na verdade foi até bom esse pequeno lapso porque notei algo que me deixou curioso. Na fórmula com primo e p ≠ 2, todos os resultados serão divisíveis por 3? Em caso afirmativo, como se prova isso?
Testei os primos de 3 até 61 e todos os resultados foram divisíveis por 3.

Sei que isso deveria ser tratado teoricamente, mas eu taquei numa tabela os cálculos para (2^p +1)/3 e descobri que se "p" é ímpar, o resultado é inteiro. Ou seja, não funciona somente com primos, mas com qualquer "p" ímpar. Testei até o 45 usando o oocalc para fazer as contas.

[Fenrir]

Queria ver eles descobrirem um numero enorme, cuja quantidade de digitos fosse um numero primo e cujos digitos fossem todos numeros primos!