Ronzii's Blog

Just your average geek's blog

Project Euler Problem 18,67

#include <iostream>
using namespace std;
int main ()
{
    int row;
    int array [102] [102];
    cin >> row;
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j <= i; j++)
            cin >> array [i] [j];
    }
    for( int i = row - 2; i >= 0; i--)
    {
        for(int j = 0; j <= i; j++ )
        {
            array[i][j]+=max( array[i + 1][j],array[i + 1][j + 1]);
        }
    }
    cout<<array[0][0];
    return 0;
}

March 26, 2012 Posted by | C++, Dynamic Programming | , , , , | Leave a comment

Project Euler Problem 7

#include <iostream>
#include <bitset>
#define SIZE 1000000
#define MAX (int)(SIZE-3)/2
using namespace std;
unsigned long long primes[MAX+1];    //array that stores the primes up to sqrt(SIZE)
bitset<MAX+1> bset;   //auxiliary bitset used to make the sieve
void setPrimes()
{
    unsigned long long i,j;
    for(i=0; i*i<=SIZE; i++)   //we only have to get primes up to sqrt(SIZE)
        if(!bset.test(i))
            for(j=i+1; (2*j+1)*(2*i+3)<=SIZE; j++)
                bset.set(((2*j+1)*(2*i+3)-3)/2);   //setting all non-primes
    primes[0]=2;                                   //store the first prime (that is 2)
    for(i=1,j=0; j<MAX+1; j++)
        if(!bset.test(j))
            primes[i++]=2*j+3;                     //store the remaining odd primes
}
int main()
{
    setPrimes();
    cout<<primes[10000];
    return 0;
}

March 21, 2012 Posted by | C++ | , , , | Leave a comment

Project Euler Problem 9

#include <iostream>
using namespace std;
int main()
{
    int n=400;
    for(int a=1;a<=n;a++)
    {
        for(int b=1;b<=n;b++)
        {
            int c = 1000-b-a;
            if((a*a+b*b)==c*c)
            {
                cout<<a*b*c<<endl;
            }
        }
    }
    return 0;
}

March 21, 2012 Posted by | C++ | , | Leave a comment

Project Euler Problem 8

#include <iostream>
using namespace std;
int main()
{
    int length = 1000;
    char s[] = {};
    int product,maxProduct=0;
    for(int i=0; i<length; i++)
    {
        product = 1;
        for(int j=0; j<5; j++)
        {
            product*=(s[i+j]-'0');
        }
        maxProduct = max(maxProduct,product);
    }
    cout<<maxProduct;
    return 0;
}

March 21, 2012 Posted by | C++ | , | Leave a comment

Project Euler Problem 5

#include <cstdio>
#include <iostream>
#include <climits>
#include <vector>
using namespace std;
unsigned long long  gcd(unsigned long long  a, unsigned long long  b)
{
    if(b==0) return a;
    return gcd(b,a%b);
}
unsigned long long  lcm(unsigned long long  a, unsigned long long  b)
{
    return a*b/gcd(a,b);
}
int main()
{
    unsigned long long ans=1;
    for(int i=1;i<=21;i++)
    {
        ans = lcm(ans,i);
    }
    cout<<ans;
    return 0;
}

March 21, 2012 Posted by | C++ | , | Leave a comment

Project Euler Problem 6

#include <iostream>
using namespace std;
int main()
{
    unsigned long long sumSquare = 0,sum=0;
    for(int i=1;i<=100;i++)
    {
        sumSquare+= i*i;
        sum+=i;
    }
    sum*=sum;
    cout<<sum-sumSquare;
    return 0;
}

March 21, 2012 Posted by | C++ | , , | Leave a comment

Project Euler Problem 3

#include <iostream>
#include <bitset>
#define SIZE 1000000
#define MAX (int)(SIZE-3)/2
using namespace std;
unsigned long long primes[MAX+1];    //array that stores the primes up to sqrt(SIZE)
bitset<MAX+1> bset;   //auxiliary bitset used to make the sieve
void setPrimes()
{
    unsigned long long i,j;
    for(i=0; i*i<=SIZE; i++)   //we only have to get primes up to sqrt(SIZE)
        if(!bset.test(i))
            for(j=i+1; (2*j+1)*(2*i+3)<=SIZE; j++)
                bset.set(((2*j+1)*(2*i+3)-3)/2);   //setting all non-primes
    primes[0]=2;                                   //store the first prime (that is 2)
    for(i=1,j=0; j<MAX+1; j++)
        if(!bset.test(j))
            primes[i++]=2*j+3;                     //store the remaining odd primes
}
int main()
{
    setPrimes();
    unsigned long long N = 600851475143,i=30000;
    while(1)
    {
        if(N%primes[i]==0)
        {
            cout<<primes[i]<<endl;
            break;
        }
        i--;
    }
    return 0;
}

March 21, 2012 Posted by | C++ | , , , , , | Leave a comment