Project Euler 49

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <stdlib.h>
using namespace std;
bool esPrimo(int n)
{
    if((n&1)==0)
        return (n==2);
    double raiz = sqrt(n);
    for(int i = 3; i<=raiz ; i+=2)
        if((n%i) == 0)
            return false;
    return true;
}
string parseString(int n)
{
    string sol = "";
    while(n>0)
        sol = (char)((n%10)+'0')+sol , n/=10;
    return sol;
}
bool esValido(string cad)
{
    for(int i= 0 ; i<cad.size(); i++)
        if(cad[i]=='0')
            return false;
    return true;
}
int main()
{

    bool probados[10000]= {false};
    for(int n = 1488; n<=9999; n++)
    {
        if(!probados[n])
        {
            string num = parseString(n);
            if(esValido(num))
            {
                vector<int> permutaciones;
                do
                {
                    int ent = atoi(num.data());
                    probados[ent] = true;
                    permutaciones.push_back(ent);

                }
                while(next_permutation(num.begin(),num.end()));

                int nroPer =permutaciones.size();
                for(int i = nroPer; i>=2 ; i--)
                    if(esPrimo(permutaciones[i]))
                        for(int j= i-1; j>=1 ; j--)
                            if(esPrimo(permutaciones[j]))
                                for(int k = j-1; k>=0; k--)
                                    if(esPrimo(permutaciones[k]))
                                        if(permutaciones[i]-permutaciones[j] == permutaciones[j]-permutaciones[k])
                                        {
                                            cout << permutaciones[k];
                                            cout << permutaciones[j];
                                            cout << permutaciones[i]<<endl;
                                            return 0;
                                        }
            }
        }
    }
    return 0;
}

Project Euler 48

import java.math.BigInteger;
public class Main {
 public static void main(String[] args) {
  BigInteger res = BigInteger.ONE;
  BigInteger modu = new BigInteger("10000000000");
  for (int i = 2; i <= 1000; i++) 
   res = res.add(new BigInteger(i+"").modPow(new BigInteger(i+""), modu));
  System.out.println(res.mod(modu));
 }
}

Project Euler 47

#include <iostream>
#include <vector>
#include <set>
using namespace std;

bool Factorizar(int n,int nrofactores,vector<int>* factores)
{
    int i;
    int cant = 0;
    for(i = 2; n>1 ; i++)
        if((n%i) == 0 )
        {
 
            cant++;
            if(cant>nrofactores)
                return false;
            int factor =i;
            n/=i;
            while((n%i) == 0)
                n/=i ,factor*=i;
            factores->push_back(factor);
        }
    return (cant==nrofactores);
}
int main()
{
    int ini = 1;
    vector<int> a,b,c,d;
    bool swa,swb,swc,swd;
    swa =swb=swc=swd = false;
    while(true)
    {
        swa = swb;
        swb = swc;
        swc = swd;
        a.swap(b);
        b.swap(c);
        c.swap(d);
        d.clear();
        swd = Factorizar(ini,4,&d);
        //cout <<ini<<" = " << swa <<" "<< swb <<" "<< swc <<" "<< swd <<endl;
        if(swa && swb && swc && swd)
        {
            set<int> miset(a.begin(),a.end());
            miset.insert(b.begin(),b.end());
            miset.insert(c.begin(),c.end());
            miset.insert(d.begin(),d.end());
            if(miset.size()==16)
            {
                cout << ini<<endl;
                return 0;
            }
        }
        ini++;
    }
    return 0;
}

Project Euler 46

#include <iostream>
#include <cmath>
#define LIM 10000
using namespace std;
int primos[5000]={0};
bool criba[LIM+1]={false};
int cantPrimos = 1;
void generarCriba(){
    int i,j;
    double raiz = sqrt(LIM);
    for(i = 4 ; i<=LIM ;i+=2)
        criba[i] = true;
    for(i = 3 ; i<=raiz;i+=2)
        if(!criba[i])
            for(j = i+i ; j<=LIM ; j+=i)
                criba[j] = true;
    primos[0] = 2;

    for(i = 3; i<=LIM;i+=2)
        if(!criba[i])
            primos[cantPrimos++] = i;
}
bool sePuedeEscribir(int n){
    if(!criba[n])
        return true;
    int i;
    for(i = 0; i<cantPrimos && primos[i]+2 <= n; i++){
        int p = 1;
        int var;
        while((var=(primos[i]+(2*p*p)))<=n){
            if(var==n)
                return true;
            p++;
        }
    }
    return false;
}
int main()
{
    generarCriba();
    int n = 33;
    while(true){
        if(!sePuedeEscribir(n)){
            cout << n<< endl ; return 0;
        }
            n+=2;
    }
    return 0;
}

Project Euler 45

#include <iostream>
#include <cmath>
using namespace std;
int incr = 286;
int s = 40755;
bool esTriangular(int n)
{
    while(s<n)
        s+=incr, incr++;
    return s == n;
}
bool esPentagonal(int x)
{
    double n = (sqrt(24.0*x + 1)+1)/6.0;
    return n==floor(n);
}
int main()
{
    int hexa;
    int id=144 ;
    while(true)
    {
        hexa = id*(2*id -1 );
        if(esPentagonal(hexa) && esTriangular(hexa))
        {
            cout << hexa<<endl;
            return 0;
        }
        id++;
    }
    return 0;
}

Project Euler 44

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
bool esPentagonal(int x)
{
    double n = (sqrt(24.0*x + 1)+1)/6.0;
    return n==floor(n);
}
int obtPent(int n)
{
    return (n*(3*n-1))/2;
}
int main()
{
    vector<int> pentagonals;
    pentagonals.push_back(1);
    bool sw = true;
    int pent,resta;
    int k = 2;
    while(sw)
    {
        pent = obtPent(k);
        vector<int>::iterator it = pentagonals.begin();
        while(it != pentagonals.end())
        {
            resta = pent - (*it);
            if(esPentagonal(resta))
                if(esPentagonal(pent+(*it)))
                {
                    cout<<resta<<endl;
                    return 0;
                }
            it++;
        }
        pentagonals.push_back(pent);
        k++;
    }
    return 0;
}

Project Euler 43

#include <iostream>
#include <algorithm>
#include <stdlib.h>
using namespace std;
int primos[8] = {2,3,5,7,11,13,17};
int main()
{
    string ini = "0123456789";
    string fin = "9876543210";
    unsigned long long int suma = 0 ;
    while(ini.compare(fin)!=0)
    {
        bool sw = true;
        for(int i = 7; i >= 1 && sw; i--)
            sw = ((((ini[i]-'0')*100+(ini[i+1]-'0')*10+(ini[i+2]-'0'))%primos[i-1])==0);
        if(sw)
            suma += atof(ini.data());

        next_permutation(ini.begin(),ini.end());
    }
    cout <<suma << endl;
    return 0;
}

Project Euler 42

#include <iostream>
#include <fstream>
using namespace std;
bool esT[200];
void generarTrian()
{
    for(int i = 0 ; i<200; i++)esT[i] = false;
    int s = 1;
    for(int c = 2; s<200; c++)
    {
        esT[s] = true;
        s += c;
    }
}
int main()
{
    generarTrian();
    ifstream fin("words.txt");
    string cad ;
    fin >> cad;
    cad += ",";
    int maxi = 0;
    int a,b;
    a = 0;
    b = -1;
    for(int i = 1 ; i<cad.size(); i++)
    {
        while(i<cad.size() and cad[i]!=',')
            i++;
        a = b+1;
        b = i;
        int tmp = 0 ;
        for(int j = a+1; j<b-1; j++)
            tmp += (cad[j]-'A'+1);

        if(esT[tmp])
            maxi++;
    }
    cout << maxi << endl;
    return 0;
}

Project Euler 41

#include <iostream>
#include <algorithm>
using namespace std;
const int n= 7654322;
bool esPrimo[n+1];
void generarCriba()
{
    for(int i = 3 ; i <= n; i+=2)
        esPrimo[i] = true;
    for(int i = 4 ; i <= n; i+=2)
        esPrimo[i] = false;
    esPrimo[2] = true;
    for(int i = 3; i*i <= n; i+=2)
        if(esPrimo[i])
            for(int j = i+i ; j <= n; j+=i)
                esPrimo[j] = false;
}
int main()
{
    generarCriba();
    string ini = "7654321";
    string fin = "1234567";
    int i = 0 ;
    while(ini.compare(fin)!=0)
    {
        if(((ini[6]-'0')&1)!=0)
            if(esPrimo[atoi(ini.data())])
            {
                cout << ini << endl;
                break;
            }
        prev_permutation(ini.begin(),ini.end());
    }
    return 0;
}

Project Euler 37

#include <iostream>
#include <bitset>
#include <math.h>
using namespace std;
bool esPrimo(int n)
{
    if(n==1)
        return false;
    for(int i = 2; i*i<=n; i++)
        if(n%i==0)
            return false;
    return true;
}

bool esCPI(int n)
{
    int nc = 10;
    while(nc<n)
    {
        if(!esPrimo(n%nc))
            return false;
        nc *= 10;
    }
    return true;
}
int main()
{

    int ini=0,fin=0;
    int term[] = {1,3,7,9};
    int td[100]= {2,3,5,7};

    int pos=4;
    ini = 0;
    fin = 3;
    for(int cd = 1; cd<=9; cd++)
    {
        for(int i=ini ; i<=fin; i++)
        {
            for(int t = 0 ; t<=3; t++)
            {
                int ope = td[i]*10+term[t];
                if(esPrimo(ope))
                    td[pos++] = ope;
            }
        }
        ini = fin+1;
        fin = pos-1;
    }
    int sum = 0 ,cant = 0;
    for(int i = 4; i<=fin ; i++)
        if(esCPI(td[i]))
        {
            cout << td[i] << endl;
            sum += td[i];
            cant++;
        }
    cout << "cantidad total = "<<cant<<endl;
    cout << "resultado final = "<<sum<<endl;
    return 0;
}

Project Euler 36

#include <iostream>
#include <string>
using namespace std;
bool esPalindrome(string cad)
{
    int i,j;
    i = 0;
    j = cad.size()-1;
    while(i<j)
        if(cad[i++]!=cad[j--])
            return false;
    return true;
}
string abase2(int n)
{
    string sol = "";
    while(n>0)
        sol = (char)((n&1)+'0')+sol , n >>= 1;
    return sol;
}
string aString(int n)
{
    string sol = "";
    while(n>0)
    {
        int d = n%10;
        sol = (char)(d+'0')+sol;
        n /= 10;
    }
 
    return sol;
}
int main()
{
//872187
    int suma = 0 ;
    const int n = 1000000;
    for(int i = 1; i < n; i+=2)
        if(esPalindrome(aString(i)) && esPalindrome(abase2(i)))
            suma += i;
    cout << suma << endl;
    return 0;
}

Project Euler 35

#include <iostream>
#include <bitset>
using namespace std;
const int n = 1000000;
bitset<n+1> criba;
void generarCriba()
{
    criba[0] = criba[1] = true;
    for(int i = 2 ; i*i<=n; i++)
        if(!criba[i])
            for(int j = i+i; j<=n; j +=i )
                criba[j]= true;

}
int main()
{
    generarCriba();
    int cont = 4;//2,3,5,7 ya cuentan como primos circulares
    int cc = 1;
    int sncc= 100;
    int nc = 10;
    for(int i = 10 ; i<n; i++)
    {
        if(i==sncc)
        {
            cc++;
            sncc *=10;
            nc *= 10;
        }
        if(!criba[i])
        {
            int num = i;
            int c = 0;

            for(int u = 1 ; u<=cc; u++)
            {
                int d = num%10;
                num /= 10;
                num = (d*nc+num);
                if(!criba[num])
                    c++;
                else
                    break;
            }

            if(c == cc)
                cont++;
        }
    }
    cout <<"Resultado final = "<< cont<< endl;
    return 0;
}

Project Euler 34

#include <iostream>

using namespace std;

int main()
{
    int sum = 0 ;
    int fac[10] = {1,1,2};
    for(int i = 3; i<=9; i++)
        fac[i] = i*fac[i-1];
    int num = 0;
    int n[5]= {0};
    for(n[0] = 0 ; n[0]<10 ; n[0]++)
        for(n[1] = 0 ; n[1]<10 ; n[1]++)
            for(n[2] = 0 ; n[2]<10 ; n[2]++)
                for(n[3] = 0 ; n[3]<10 ; n[3]++)
                    for(n[4]= 0 ; n[4]<10 ; n[4]++)
                    {
                        int pos = 0 ;
                        while(pos <=4 && n[pos]==0)
                            pos++;
                        if(fac[n[0]]+fac[n[1]]+fac[n[2]]+fac[n[3]]+fac[n[4]]-pos==num)
                        {
                            cout << n[0] << "! + ";
                            cout << n[1] << "! + ";
                            cout << n[2] << "! + ";
                            cout << n[3] << "! + ";
                            cout << n[4] << "! = " << num<< endl;

                            sum += num;
                        }
                        num++;
                    }
    cout << sum-3<< endl;
    /*Le restamos 3 por que en el enunciado
      indica que no hay que sumar 1! = 1 y 2! = 2
        */
    return 0;
}

Project Euler 33

#include <iostream>

using namespace std;

int mcd(int a,int b)
{
    int c;
    if(b>a)
    {
        c = a;
        a = b;
        b = c;
    }
    c = a%b;
    while(c > 0)
    {
        a = b;
        b = c;
        c = a%b;
    }
    return b;
}

int main()
{
    int mcdiv;
    int de,nu;
    int resultadoden  = 1;
    int resultadonum = 1;
    for(int num = 10; num<=50; num++)
        for(int den = 10; den <= 99 ; den++)
        {
            mcdiv = mcd(num,den);
            if(num != den && mcdiv!=1 && mcdiv%10!=0)
            {
                de = den/mcdiv;
                nu = num/mcdiv;
                int dat1[2]= {num/10,num%10};
                int dat2[2]= {den/10,den%10};
                for(int i=0; i<=1; i++)
                    for(int j = 0; j<=1; j++)
                        if(dat1[i]!=0 && dat2[j]!=0 &&
                                dat1[i]%nu==0 &&
                                dat2[j]%de==0 &&
                                (dat1[i]/nu)==(dat2[j]/de) &&
                                (dat1[(i+1)%2]==dat2[(j+1)%2]))
                        {
                            cout << num<<"/"<<den<<" = "<<dat1[i]<<"/"<<dat2[j]<<endl;
                            resultadoden *= den;
                            resultadonum *= num;
                        }
            }
        }
    cout << "Resultado final = "<< resultadoden/mcd(resultadonum,resultadoden) <<endl;

    return 0;
}

Project Euler 32

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <set>
#include <numeric>
using namespace std;
int factorial(int n)
{
    int f  = 1;
    while(n>0)
        f *= n--;
    return f;
}
int main()
{
    set<int> guardar ;
    string cad =  "123456789";
    int tam =  cad.length();
    int n1,n2,n3,i,j;
    int fac = factorial(tam);

    for(int n = 0 ; n < fac; n++)
    {
        for(i = 1 ; i <=(tam-2) ; i++ )
        {
            n1 = atoi(cad.substr(0,i).data());
            for(j = 1 ; j <= (tam-i-1); j++)
            {
                n2 = atoi(cad.substr(i,j).data());
                n3 = atoi(cad.substr(i+j,tam-i+j).data());
                if((n1*n2) == n3)
                {
                    cout << n1 << " x "<<n2 <<" = "<<n3<<endl;
                    guardar.insert(n3);
                }
            }
        }
        next_permutation(cad.begin(),cad.end());
    }
    cout << "Resultado Final = "<<accumulate(guardar.begin(),guardar.end(),0)<<endl;
    return 0;
}

Project Euler 40

#include <iostream>
#include <math.h>
using namespace std;
//metodo para obtener el i-esimo caracter de la concatenacion de 1,2,3,4,5...
int d(int i)
{
    int cd = 0; //cantidad de digitos
    int cda = 0; //cantidad de digitos acumulados
    int scd = 0; //siguiente cantidad de dtitos
    while( cda + scd < i)
    {
        cda += scd;
        cd++;
        scd =  (pow(10,cd)-pow(10,cd-1))*cd;
    }
    int numactual = pow(10,cd-1)-1;//numero actual hasta el cual se sumo
    while(cda < i)
    {
        cda += cd;
        numactual++;
    }
    int csp = (cda-i);
    while(csp--) numactual /= 10;
    return numactual%10;
}
int main()
{
    cout << d(1)*d(10)*d(100)*d(1000)*d(10000)*d(100000)*d(1000000)<<endl;
    return 0;
}

Project Euler 39

#include <iostream>
using namespace std;
int main()
{
    int v[1001], a, b, c;
    for( a = 1000 ; a >= 0 ; a--) v[a] = 0 ;
    for ( c = 1; c <= 1000; c++)
        for ( b = 1; b < c; b++)
            for ( a = 0; a <= b; a++)
                if(a+b>c && b-a<c && a+b+c <= 1000 && c*c == a*a+b*b)
                    v[a+b+c]++;
    b = 0 ;
    for ( a = 0; a <= 1000; a++)
        if(v[a]>v[b])
            b = a;
    cout << b << endl;
    return 0;
}

Project Euler 38

public class Problema38 {
 static boolean isPandigital(String num){
  if(num.length()!=9)
   return false;
  for (int i = 1; i < 10; i++) 
   if(!num.contains(""+i))
    return false;
  return true;
 }
 public static void main(String[] args) {
  String max = "123456789";
  for (int i = 9; i < 10000; i++) {
   int m = 1;
   String sol = "";
   while(sol.length()<9){
    sol += (i*m);
    m++;
   }
   if(sol.length()==9)
    if(isPandigital(sol))
     if(sol.compareTo(max)>0)
      max = sol;
  }
  System.out.println(max);
 }
}

Problem Euler 18 y 67

Empezando con DP

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class problem18 
{
 public static void main(String[] args) throws FileNotFoundException {
  int m[][]=readArch();
  for (int i = m.length-2; i >=0; i--) 
  { 
   for (int j = 0; j <=i; j++) {
    
    m[i][j]+=Math.max(m[i+1][j+1], m[i+1][j]);
   }
  }
  System.out.println(m[0][0]);
 }

 private static int[][] readArch() throws FileNotFoundException 
 {
  int triangulo[][]= new int [150][150];
  Scanner sc = new Scanner (new File("C:\\triangle1.txt"));
  int co=0,fi=0;
  while(sc.hasNextLine())
  {
   String linea = sc.nextLine();
   String v[]= linea.split(" ");
   for (int i = 0; i < v.length; i++) 
   { 
    co=i;
    triangulo[fi][co]=Integer.parseInt(v[i]);  
   } 
   fi++;
  }
  return triangulo;
 }
}

project euler # 41

una variacion del problema 32

import java.util.Arrays;
import java.util.BitSet;
import java.util.Scanner;


public class problem41 
{
 public static void main(String[] args) 
 {


  long tiempo= System.currentTimeMillis();
  BitSet a = new BitSet(987654321);
  int i =2,j=0;
  for(i=2;(i*i)<=10000000;i=i+1)
  {
   if(!a.get(i))
   {
    for(j=i+i;j<=10000000;j=j+i)
    {
     a.set(j);
    } 
   }
  }
  for (int j2 =7654321; j2 >=1 ;j2--) 
  {
   String x=Integer.toString(j2);
   char v[]= x.toCharArray();
   Arrays.sort(v);
   if(!a.get(j2))
   {
    if(ispandigital(x, v[v.length-1]-48))
    {System.out.println(x);
    break;
    }
   }
  }
  System.out.println(System.currentTimeMillis()-tiempo);
 }
 public static boolean ispandigital(String x,int n)
 {
  boolean v[]= new boolean[n+1];
  for (int i = 0; i < x.length(); i++) 
  {
   v[x.charAt(i)-48]=true;
  }
  for (int i = 1; i < n+1; i++) 
  {
   if(!v[i])
    return false;
  }

  return true;
 }
}