Category: Project Euler


Project Euler :: Problem 15

Problem 15
Starting in the top left corner of a 2×2 grid, there are 6 routes (without backtracking) to the bottom right corner.

grid
How many routes are there through a 20×20 grid?

Recursion is the first thing which comes into mind in such cases

c++ implementation ::

#include <iostream>
using namespace std;
#define limit 20
long long grid[21][21];
long long walk(int x, int y) {
        if (x > limit || y > limit) return 0;
        if (x == limit && y == limit) return (1);
        if (grid[x][y] != 0) return grid[x][y];
        long long result = 0;
        result += walk(x, y+1);
        result += walk(x+1, y);
        grid[x][y] = result;
        return grid[x][y];
}


int main() {
//      memset(grid, 0, sizeof(grid));
        cout << 2 * walk(1, 0) << endl;
//      system("PAUSE");
        return (0);
}

But if you think from point of view of high school mathematics student, you still can solve it

#include<iostream>
#include <inttypes.h>
using namespace std;

int main()
{
        //additionally,for a generalized solution of gridsize a*b routes=[(a+b)!]/[a!* b!]
        int64_t x=1; //just trying this data type here
        long long int y=1;
        x=37*7*11*31*29*3*4;
        y=115*39;
        cout<<x*y<<endl;

        return 0;
}

This is my last post in this section, this section was just to help get c and c++ fellows started with project euler…try other problems yourself now…gl hf !! 🙂

Advertisements

Problem 10

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

one of my fav problems, learned a lot of stuff from it.

Implementation using sieve of Eratosthenes ::

#include <iostream>
#include <vector>

using namespace std;

int main()
{
        unsigned const n = 10000000;  //value of n as per requirement
        vector<bool> p(n, true);
        long long int sum = 0;

        // sieve of Eratosthenes
        for(unsigned i = 2; i*i <= n; ++i)
                for(unsigned j = 2*i; j < n; j += i)
                        p[j] = false;

        // find m-th prime
        unsigned i = 2;
        for(unsigned c = 0; i !=2000000 ; ++i){
                if(p[i]) sum+=i;
        }

        cout<<sum<<endl;

        return 0;
}

Implementation using Sieve of Atkins::

/*
 *  Adaptation of the Sieve of Atkin (faster than the Sieve of Eratosthenes), but using modulo-thirty.
 *  The idea is:
 *  - 30 is the lcm of 2, 3 and 5 (the first 3 primes);
 *  - get the list of 30 next numbers (1..30, 31..60, etc) and discard all multiples of 2, 3 and 5;
 *  - it will remain 1, 7, 11, 13, 17, 19, 23 and 29
 *  - so, you only have to test the numbers in this groups.
 *
 *   good ref. --> http://www.codeproject.com/KB/recipes/PrimeSuspect.aspx
 *      
 */


#include <iostream>
#include <stdbool.h>
#include <math.h>
#include<cstdio>
#include<vector>
#define ulli unsigned long long int

using namespace std;

bool prime(ulli n, vector<unsigned long long int> &vec) {
    int i;
    ulli max = (ulli)sqrt((ulli)n);
    for (i = 0; vec[i] <= max; i++)
        if (n % vec[i] == 0)
            return (false);
    return (true);
}

#define prime_test if (prime(num,primes)) primes[++i] = num
int main()
{
    int i = 9;
    ulli num = 31;
    vector<ulli> primes(200001);
    primes[0]=2;primes[1]=3;primes[2]=5;primes[3]=7;primes[4]=11;primes[5]=13;primes[6]=17;primes[7]=19;primes[8]=23;primes[9]=29;
    while (i < 200000) {
        prime_test; // 1
        num+=6;
        prime_test; // 7
        num+=4;
        prime_test; // 11
        num+=2;
        prime_test; // 13
        num+=4;
        prime_test; // 17

        num+=2;
        prime_test; // 19
        num+=4;
        prime_test; // 23
        num+=6;
        prime_test; // 29
        num+=2;
    }
    long long int sum=0;
    int k=0;
    while(primes[k]<2000000){
        sum+=primes[k];
        k++;
    }
    printf("%llu\n",sum);
    return 0;
}
#undef prime_test
#undef ulli