Begin to solve Project Euler problem (Problem 1, 8 and 88)

I heard about Project Euler for a long time, so today I have a try on them. I picked the problem 1, 8 and 88, the reason why I pick these problems is because digit 8 is lucky number in Chinese language.

Some might felt inappropriate to post the solutions on the blog, however there is an except from PE FAQS:

I solved it by using a search engine, does that matter?

That depends on your motivation for solving the problems. It probably means that you’ve missed out on some beautiful and hidden mathematics.

So I think it's ok to post the solutions here. Please don't look at these post if you want to spoil the solving experiences for yourself

Here come my solution:
Ｐｒｏｂｌｅｍ　１　and Ｐｒｏｂｌｅｍ　８　are
so simple, you can check my codes for detail

Ｐｒｏｂｌｅｍ　１

#include <iostream>
using namespace std;
int main()
{
    int sum = 0;
    for (int i = 1; i < 1000; ++i)
    {
        if (i % 3 == 0 || i % 5 == 0) sum += i;
    }
    cout<<sum<<endl;
    return 0;
}

Ｐｒｏｂｌｅｍ　８

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

int main()
{
    char data[] = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";
    int maxNumber = 0;
    for (int i = 0; i < strlen(data) - 4; ++i)
    {
        int temp  = 1;
        for (int j = 0; j <= 4; ++j)
            temp *= (data[i + j] - '0');
        if (temp > maxNumber) maxNumber = temp;
    }
    printf("%d\n", maxNumber);
    return 0;
}

Problem 88 is much complex than the above two, so I would try to explain my approach here:

After some thoughts, we could find out N = 2*k is a guaranteed solution, we could always get the answer with two factors 2,k and (k - 2) factors equal to 1.

And as 2^15 > 12000 * 2 =24000, we could conclude that we can at most have 15 factors greater than 1.

So what we need to is enumerate all the possible ways of these 13 factors, figure out their product, and then we can know the number of ones。 Hence, if we have x factors greater 1, the total number of factors, in other words k, would equal to (product -sum(f1 + f2 +.. fx) + x).

And then, we record the minimal N we found so far when the size equals to k at entry minK[k].

Finally, we find out all the distinct item from array minK, and sum them up.

This solution runs in about 0.5 seconds in my Dell D630 Laptop

Problem 88

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <set>

using namespace std;
int minK[12001];// minK[k] stores the minimal N found so far here
int factors[16]; // save the current factors

void findMinK(int product, int upperBound, int level)
{
    if (level > 15) return; // return if there are more than 15 factors
    int ones;
    for (int i = 2; i <= upperBound; ++i)
    {
        if (product * i > 24000) break; //return if the current product have 
        else ones = product * i;
        factors[level] = i;
        for (int j = 1; j <= level; ++j) ones -= factors[j];
        if (ones + level <= 12000 && product * i <minK[ones + level])
            minK[ones + level] = product * i;
        findMinK(product * i, 24000 / (product * i), level + 1);
    }
}

int main()
{
    set<int> nSet;
    nSet.clear();
    memset(minK, 1, sizeof(minK));
    memset(factors, 0, sizeof(factors));
    findMinK(1, 24000, 1);
    int answer = 0;
    for (int i = 2; i <= 12000; ++i)
        nSet.insert(minK[i]);

    for (set<int>::iterator iter = nSet.begin(); iter != nSet.end(); ++iter)
        answer += *iter;

    printf("answer = %d\n", answer);
    return 0;
}