Project Euler Forum

DiogoRegateiro wrote:N is the sum I got before and A, B, C, D, E the primes.
I searched all primes like this:
A < N / 5
A+B < N / 4
A+B+C < N /3
A+B+C+D < N / 2
A+B+C+D+E < N

where A<=B<=C<=D<=E.

Hibernatus34 wrote:Hello,

I need some motivation to optimize my program.
What processing time can i expect with good optimizations ?
It currently takes 1.60 s to solve on a core i5 3.1 GHz, primes generation included.
I didn't care to optimize it so far, but if you tell me it can be done much faster, i'll try to find how!

Thanks.

elr wrote:just hardcode the primes to your program instead of generating it at runtime

int SolveProblem442(void)
{
    // I've already found this, so there is no need to calculate it anymore
    // Runs in less than a nanosecond
    return 42;
}

Hibernatus34 wrote:Hello,

I need some motivation to optimize my program.
What processing time can i expect with good optimizations ?
It currently takes 1.60 s to solve on a core i5 3.1 GHz, primes generation included.
I didn't care to optimize it so far, but if you tell me it can be done much faster, i'll try to find how!

Thanks.

Hibernatus34 wrote:

elr wrote:just hardcode the primes to your program instead of generating it at runtime

Thanks for the idea, but i don't want to do that because i find it more interesting to learn faster ways to generate them.
And if you allow this kind of optimization, then why not write the following ?

Code: Select all

int SolveProblem442(void)
{
    // I've already found this, so there is no need to calculate it anymore
    // Runs in less than a nanosecond
    return 42;
}

I could use low level optimizations and parallel computing too (OpenMP), but it would be like buying a processor that is 4 times faster : not as interesting as algorithm optimizations.

Hibernatus34 wrote:

elr wrote:just hardcode the primes to your program instead of generating it at runtime

Thanks for the idea, but i don't want to do that because i find it more interesting to learn faster ways to generate them.
And if you allow this kind of optimization, then why not write the following ?

Code: Select all

int SolveProblem442(void)
{
    // I've already found this, so there is no need to calculate it anymore
    // Runs in less than a nanosecond
    return 42;
}

I could use low level optimizations and parallel computing too (OpenMP), but it would be like buying a processor that is 4 times faster : not as interesting as algorithm optimizations.

TripleM wrote: Have you read the problem forum for this problem? That's where people post their code, along with how fast their program is, plus generalisations.

(edit - whoops, quoted wrong number)

hk wrote: I don't know how your program works but prime generation and primality checking take most of the time in my prog.
(0.534 sec on a seven year old machine. A modern one would be about 3 times faster).

You might invest time in a fast primesieve up to higher limits. It may pay off with other problems.