Thread: project Euler

I didn't realize we were going beyond simple brute force.
20 minutes of coding later calculates up to the 4480 factor value in less than 2 seconds (on a slow machine).
This takes less than 45 seconds.

Code:

  Limit    Index          Number Factors
>= 1000    41040       842161320    1024
>= 2000   313599     49172323200    2304
>= 3000   453375    102774672000    3072
>= 4000  1890944   1787835551040    4480
>= 5000  2203200   2427046221600    5760
>= 6000  2756159   3798207594720    6144
>= 7000  7289919  26571463158240    7680
>= 8000 10497024  55093761676800    8640
>= 9000 11851839  70233049766880    9216
>=10000 14753024 108825865948800   13824

But I guess code is secret now.

Originally Posted by john.c

But I guess code is secret now.

Still brute force, and the code isn't secret, just not that well written or interesting. Here's the most interesting bit:

Code:

struct Factor {
   uint64_t factor;
   uint64_t power;
};


struct Factor_List {
   uint32_t used;
   struct Factor factors[64];  // Any more than 64 unique factors means the number is way more than 2^64

};


int main(int argc, char *argv[])
{
   find_primes(1000000000);
   struct Factor_List fl1,fl2;
   int limit = 125;
   uint64_t a = 2;
   uint64_t b = 3;
   find_factors(a/2, &fl1);  // Remove the factor of 2 from 'a'
   while(a < 1000000000) {
      int factors;
      find_factors(b, &fl2);
      factors = count_factors(&fl1,&fl2);
      if(factors > limit) {
          printf("The %ldth triangular number %ld has %d factors\n", a, a*(a+1)/2, factors);
          while(limit < factors)
             limit *= 2;
      }
      a+= 2;


      find_factors(a/2, &fl1);  // Remove the factor of 2 from 'a'
      factors = count_factors(&fl1,&fl2);
      if(factors > limit) {
          printf("The %ldth triangular number %ld has %d factors\n", b, b*(b+1)/2, factors);
          while(limit < factors)
             limit *= 2;
      }
      b+= 2;
   }
}