Argus - Challenge 2 - HardCore - C++

Argus Ter Jul 19, 2011 9:09 pm

Bom, não ando tendo muito tempo já que tenho que estudar certos assuntos nas férias. Mas só para não deixar a inércia reinar, resolvi solucionar um dos problemas do Challenge 2. Já havia solucionado um parecido quando resolvi alguns problemas do projecteuler. Como havia codificado em python naquela época, resolvi criar essa solução em C++ (até porque nunca estudei python como deveria). A solução foi codificada em C++ levando em consideração a portabilidade do código. Assim, deve ser possível compilar o código em qualquer compilador que suporte os padrões da linguagem C++. No entanto, como foi usada a biblioteca matemática cmath, em alguns sistemas pode ser necessário a linkagem de tal biblioteca, como é o caso do GNU/Linux. Basta passar o parâmetro -lm ao gcc para que se possa compilar nesse sistema. Em caso de dúvida vocês podem consultar a documentação dos seus compiladores. Na solução usei o crivo de eratóstenes, que é bem simples e bastante famoso. Tentei comentar ao máximo os detalhes cruciais da solução. Codifiquei apressadamente, mas o algoritmo não demora décadas para retornar a solução. No meu computador (processador intel core i3 e sistema operacional windows 7 32 bits), obtive a resposta em cerca de 3~4 segundos. Então, vamos ao problema e respectiva codificação da solução.

2 - A soma dos números primos abaixo de 10 é 2 + 3 + 5 + 7 = 17.
Faça um programa que encontre e imprima a soma de todos os números primos abaixo de dois milhões como também, imprima quantos números foram encontrados.

Solução:

#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <vector>

using namespace std;

// Crivo de eratostenes
vector< int > sieve;

// Funcao que preenche, inicialmente, o vetor que armazenara os primos
void fill_sieve( const int n )
{
  for ( int i = 2; i < ( n + 1 ); i++ )
    sieve.push_back( i );
}

// Essa funcao encontra todos os primos na faixa de 2 a 2000000
// usando o famoso crivo de eratostenes
void eratosthenes( const int n )
{
  // Inicialmente, preenchemos um vetor de 2 a 2000000
  fill_sieve( n );
  // O algoritmo estabelece um limite que garante que, apos esse limite,
  // ja teremos encontrado todos os primos ate n
  int len = sqrt( n );

  // O algoritmo em si. O principio de funcionamento e simples.
  // Pegamos o primeiro primo do vetor e eliminamos todos os multiplos
  // dele (atribuindo zero na posicao desses numeros). A seguir,
  // pegamos o proximo numero diferente de zero (que nada mais e do
  // que o proximo primo). Fazemos isso ate a raiz de n. Nesse momento
  // ja teremos encontrado todos os primos no intervalo de 2 a n
  for ( int i = 0; i <= len; i++ )
  {
    // Teste necessario para pegarmos o proximo primo e
    // evitarmos divisoes por zero
    if ( sieve[ i ] == 0 )
      continue;

    for ( int j = i + 1; j < ( n - 1 ); j++ )
      if ( sieve[ j ] && !( sieve[ j ] % sieve[ i ] ) )
        sieve[ j ] = 0;
  }
}

// Funcao para remover os zeros deixados pela funcao que calcula
// os primos
void remove_zeros( )
{
  vector< int >::iterator it;
  // Ordenamos o vetor com os primos encontrados e os zeros
  // com a finalidade de deixarmos todos os zeros em
  // posicoes consecutivas
  sort( sieve.begin(), sieve.end() );

  // Removemos todos os elementos duplicados que estejam em
  // posicoes consecutivas
  it = unique( sieve.begin(), sieve.end() );

  // Necessario recalcular o tamanho do vetor apos a remocao
  // dos elementos duplicados
  sieve.resize( it - sieve.begin() );

  // Caso ainda exista algum zero, encontra-se na primeira posicao
  // do vetor, devemos elimina-lo
  if ( sieve[ 0 ] == 0 )
    sieve.erase( sieve.begin() );
}


// Essa funcao retorna a soma de todos os primos encontrados
// pelo algoritmo. Como nao sabemos se um inteiro contem capacidade
// para armazenar a soma, usamos um unsigned long long
unsigned long long sum( )
{
  long long tmp = 0ULL;

  for ( int i = 0; i < sieve.size(); i++ )
    tmp += sieve[ i ];

  return tmp;
}

int main()
{
  eratosthenes( 2000000 );
  remove_zeros();
  cout << "Foram encontrados " << sieve.size() << " primos abaixo de 2000000." << endl;
  cout << "Sendo a soma de todos os primos encontrados " << sum() << '.' << endl;
  return EXIT_SUCCESS;
}

Z3r0 Qua Jul 20, 2011 10:53 am

Seja bem vindo ao Challenge Argus. E.. fico feliz em ver C++ na competição. Pois, ja ouço algumas pessoas dizerem que estão afim de entrar com C++ .... além disso, estudo python e estou começando no C++ por agora também. Espero que tire o máximo de proveito do forum ...que compartilhe e aprenda junto conosco. Valeu.

Argus Qui Jul 21, 2011 9:39 pm

Bom, como ninguém ainda propôs uma solução para a questão 3 desse desafio, vim aqui compartilhar um pouco do que descobri a respeito. É um assunto de teoria dos números que exigiu dos Matemáticos alguma dedicação. O assunto trata de somas e diferenças de quadrados. Como não sou matemático, fui pesquisar a respeito. A solução aqui proposta é inteiramente baseada em um artigo que trata desse assunto, provavelmente o assunto foi muito estudado por Euler. Para entender a solução, é necessário o entendimento de três lemas mecionados no artigo. O que se fez foi obter os números x, y e z a partir de alguns fatores p, q, r e s. Só entrando um pouco no assunto, suponha que x + y = a^2 e x - y = d^2. Resolvendo esse sistema chegamos a x = (a^2 + d^2)/2 e y = (a^2 - d^2)/2. Através de um dos lemas citados no artigo, conclui-se que p = (a + d)/2 e q = (a - d)/2 e, consequentemente, x = pp + qq e y = 2pq. Em um outro lema, mostra-se que p = ac + bd, q = ad - bc, r = ad + bc e s = ac - bd. O artigo mostra ainda que z = 2rs. Mostra-se também que o problema pode ser reduzido às seguintes equações:

a = d = 4ffgg
b = f^4 - 2ffgg + 9g^4
c = f^4 + 2ffgg + 9g^4

Com isso, atribuindo valores a f e g, obtem-se os termos a, b, c e d e os fatores p, q, r e s. Por fim obtemos x, y e z. Para quem interessar, é importante a leitura do artigo a esse respeito. O título do artigo é Sums That Are Squares cujo autor é Ed Sandifer. O artigo pode ser encontrado aqui.

3 - Faça um programa que encontre o menor número de x + y + z com inteiros x> y> z> 0 tal que x + y, x - y, x + z, x - z, y + z, y - z sejam quadrados perfeitos.

Solução:

#include <cmath>
#include <cstdlib>
#include <iostream>
#include <utility>
#include <vector>

using namespace std;

// Vetor que guardara as solucoes obtidas
// Aqui implementei uma tripla como sendo um par entre um numero e outro par
vector< pair< unsigned long long, pair< unsigned long long, unsigned long long > > > answer;

// Obtem x, y e z a partir dos fatores p, q, r e s
// Aqui, temos:
// x = p*p + q*q
// y = 2 * p * q
// z = 2 * r * s
void getSolutions( const unsigned long p, const unsigned long q, const unsigned long r, const unsigned long s )
{
  answer.push_back( make_pair( p * p + q * q, make_pair( 2 * p * q, 2 * r * s ) ) );
}

// Obtem os fatores em funcao dos coeficientes determinados anteriormente
// Note que:
// p = ac + bd
// q = ad - bc
// r = ad + bc
// s = ac - bd
void getFactors( const int a, const int b, const int c, const int d )
{
  long p, q, r, s;

  p = a * c + b * d;
  q = a * d - b * c;
  // Como aqui podemos obter um valor negativo, devemos pegar o modulo
  q = abs( q );
  r = a * d + b * c;
  s = a * c - b * d;
  // Como no caso anterior, pegamos o modulo.
  s = abs( s );

  getSolutions( p, q, r, s );
}

// Obtem os coeficientes a, b, c, d em funcao das variaveis f e g
// Perceba que:
// a = d = 4*f^2*g^2
// b = f^4 - 2*f^2*g^2 + 9*g^4
// c = f^4 + 2*f^2*g^2 + 9*g^4
void getCoefficients( )
{
  int a, b, c, d;

  // Testamos solucoes para f = g = 1, f = 1 e g = 2, f = 2 e g = 1
  // e f = g = 2
  for ( int g = 1; g < 3; g++ )
    for ( int f = 1; f < 3; f++ )
    {
      a = d = 4 * f * f * g * g;
      b = f * f * f * f - 2 * f * f * g * g + 9 * g * g * g * g;
      c = f * f * f * f + 2 * f * f * g * g + 9 * g * g * g * g;
      getFactors( a, b, c, d );
    }
}

// Checamos se existe algum x = y, x = z ou y = z nas solucoes obtidas
// Caso afirmativo, descartamos essa solucao 
void checkSolutions( )
{
  int i = 0;
  int len = answer.size();

  // Loop que percorre o vetor que pode ter seu tamanho
  // alterado a todo momento
  while ( i < len )
  {
    // Se achamos elementos repetidos na nossa solucao, descartamos
    // e recalculamos o tamanho do vetor. Caso contrario, incrementamos
    // a variavel que controla nosso laco.
    if ( ( answer[ i ].first == answer[ i ].second.first ) || ( answer[ i ].first == answer[ i ].second.second ) || ( answer[ i ].second.first == answer[ i ].second.second ) )
    {
      answer.erase( answer.begin() + i );
      len = answer.size();
    }
    else
      i++;
  }
}

// Imprime o resultado
// Note que, como ja obtemos o resultado de forma ordenada
// imprimimos somente a solucao da posicao zero do vetor
void print( )
{
  if ( answer.size() > 0 )
  {
    cout << "x = " << answer[ 0 ].first << " y = " << answer[ 0 ].second.first << " z = " << answer[ 0 ].second.second << endl;
    cout << "x + y + z = " << answer[ 0 ].first + answer[ 0 ].second.first + answer[ 0 ].second.second << endl;
    cout << "x + y = " << answer[ 0 ].first + answer[ 0 ].second.first << " ( " << sqrt( answer[ 0 ].first + answer[ 0 ].second.first ) << "^2 )" << endl;
    cout << "x - y = " << answer[ 0 ].first - answer[ 0 ].second.first << " ( " << sqrt( answer[ 0 ].first - answer[ 0 ].second.first ) << "^2 )" << endl;
    cout << "x + z = " << answer[ 0 ].first + answer[ 0 ].second.second << " ( " << sqrt( answer[ 0 ].first + answer[ 0 ].second.second ) << "^2 )" << endl;
    cout << "x - z = " << answer[ 0 ].first - answer[ 0 ].second.second << " ( " << sqrt( answer[ 0 ].first - answer[ 0 ].second.second ) << "^2 )" << endl;
    cout << "y + z = " << answer[ 0 ].second.first + answer[ 0 ].second.second << " ( " << sqrt( answer[ 0 ].second.first + answer[ 0 ].second.second ) << "^2 )" << endl;
    cout << "y - z = " << answer[ 0 ].second.first - answer[ 0 ].second.second << " ( " << sqrt( answer[ 0 ].second.first - answer[ 0 ].second.second ) << "^2 )" << endl;
  }
}

int main( )
{
  getCoefficients();
  checkSolutions();
  print();
  return EXIT_SUCCESS;
}

Argus Qui Jul 21, 2011 9:40 pm

Mais uma vez, não esqueçam de linkar a biblioteca matemática.

Z3r0 Qui Jul 21, 2011 9:45 pm

Que bagulho.............. mirabolante hein!? vou ainda meditar em cima disso...

OmegaMK-XII Dom Jul 24, 2011 6:54 pm

Deu uma luz mas ainda vou pesquisar mais a respeito. Vlw

rmzelnick Seg Jul 25, 2011 3:22 pm

Olá Argus. O seu algoritmo do crivo não está simplificado pelo motivo de que você testa todos os números abaixo de 2,000,000 que são pares mas na matemática a teoria é de que não exista números pares primos com exceção do único número: 2.

Eu já usei este método para resolver o project euler (tenho 17 questões resolvidas por lá) mas existe um método melhor para resolver isso aí.

Argus Seg Jul 25, 2011 11:51 pm

Por isso eu disse que codifiquei de forma apressada. E sim, eu sei que existe algoritmo mais eficiente pra testar primalidade. Inclusive, conheço o famoso AKS, mas nunca implementei e nem achei necessário, já que o crivo, mesmo incluindo todos os pares, encontra rapidamente os primos para este caso. Como ainda não estudei teoria dos números, fico com o crivo por enquanto.

[]'s

rmzelnick Ter Jul 26, 2011 4:58 am

Olá Argus! Eu compilei o seu código-fonte e fiz um profile dele usando o gprof. Na minha máquina Intel atom N455, 1GB RAM, ubuntu 11.04, kernel linux 2.6.38-10-generic, gcc version 4.5.2 (Ubuntu/Linaro 4.5.2-8ubuntu4). Demorou 1 minuto e 12.76 segundos!

Por outro lado, o meu algoritmo rodou em 0.14 segundos (olha o meu post).

Se você estiver duvidando (comum porque eu também duvidaria), dê uma olhada nos relatórios:

O relatório do seu programa:
http://pastebin.com/byFtcsBw

O relatório do meu programa:
http://pastebin.com/03CreyW9

OmegaMK-XII Ter Jul 26, 2011 6:41 pm

Dei uma pequena olhada e vi que esse negócio de jogar os zeros no início pra eliminar depois tem um custo um pouco alto. Se vc simplesmente deixasse os zeros onde estão e fosse somando os elementos ignorando-os, seria um pouco mais rápido.

Argus Qua Jul 27, 2011 1:57 pm

Tudo bem, já que vocês estão tocando muito no assunto eficiência, re-implementei o algoritmo de forma a otimizar a busca pelos primos no intervalo dado. Notem, porém que a mudança feita foi somente nos múltiplos dos primos encontrados no intervalo. De qualquer forma, o algoritmo passou a rodar instantaneamente no meu computador. Como sou curioso, fui testar esse gprof, já que nunca tinha ouvido falar e, percebi que 74% do tempo gasto pelo programa otimizado se deve ao uso do container vector. O algoritmo otimizado passou a rodar em 0.19 segundos no meu computador dos quais cerca de 0.14 segundos se deve o uso do vector. Não quis editar a solução original para que percebam a diferença de tempo. Então, eis a solução otimizada a seguir.
No entanto, ainda pode-se otimizar a solução para usar menos memória e executar mais rapidamente.

2 - A soma dos números primos abaixo de 10 é 2 + 3 + 5 + 7 = 17.
Faça um programa que encontre e imprima a soma de todos os números primos abaixo de dois milhões como também, imprima quantos números foram encontrados.

Solução otimizada:

#include <cmath>
#include <cstdlib>
#include <iostream>
#include <vector>

using namespace std;

// Crivo de eratostenes
vector< int > sieve;

// Funcao que preenche, inicialmente, o vetor que armazenara os primos
void fill_sieve( const int n )
{
  for ( int i = 2; i <= n; i++ )
    sieve.push_back( i );
}

// Essa funcao encontra todos os primos na faixa de 2 a 2000000
// usando o famoso crivo de eratostenes
void eratosthenes( const int n )
{
  // Inicialmente, preenchemos um vetor de 2 a 2000000
  fill_sieve( n );
  // O algoritmo estabelece um limite que garante que, apos esse limite,
  // ja teremos encontrado todos os primos ate n
  int len = sqrt( n );

  // O algoritmo em si. O principio de funcionamento e simples.
  // Pegamos o primeiro primo do vetor e eliminamos todos os multiplos
  // dele (atribuindo zero na posicao desses numeros). A seguir,
  // pegamos o proximo numero diferente de zero (que nada mais e do
  // que o proximo primo). Fazemos isso ate a raiz de n. Nesse momento
  // ja teremos encontrado todos os primos no intervalo de 2 a n
  for ( int i = 0; i <= len; i++ )
  {
    // Teste necessario para pegarmos o proximo primo e
    // evitarmos divisoes por zero
    if ( sieve[ i ] == 0 )
      continue;

    // Remove os multiplos de cada primo encontrado ate a raiz de 2000000
    for ( int j = sieve[ i ] * sieve[ i ]; j <= sieve.size() + 1; j += sieve[ i ] )
      sieve[ j - 2 ] = 0;
  }

}

// Essa funcao retorna a soma de todos os primos encontrados
// pelo algoritmo. Como nao sabemos se um inteiro contem capacidade
// para armazenar a soma, usamos um unsigned long long
unsigned long long sum( int & len )
{
  long long tmp = 0ULL;

  for ( int i = 0; i < sieve.size(); i++ )
  {
    if ( sieve[ i ] != 0 )
    {
      tmp += sieve[ i ];
      len++; 
    }
  }

  return tmp;
}

int main()
{
  long long tmp;
  int len = 0;

  eratosthenes( 2000000 );
  tmp = sum( len );
  cout << "Foram encontrados " << len << " primos abaixo de 2000000." << endl;
  cout << "Sendo a soma de todos os primos encontrados " << tmp << '.' << endl;

  return EXIT_SUCCESS;
}

Conteúdo patrocinado

Argus - Challenge 2 - HardCore - C++