1. project Euler

im getting back to learning c so doing some project euler questions. Are they all such huge numbers why go for an answer in the 10's of millions if not bigger. The last one i have just done was work out which triangular number had over 500 multiples. it took 8 min 50 seconds to compute because i had to count from 100 to 12375 dividing each triangular number calculated by its self down to 1.

My point is why not calculate the number with 20 multiples or better yet 10 why 500!!

is there a better source of simple problems to practice with

many thanks
coop

2. > My point is why not calculate the number with 20 multiples or better yet 10 why 500!!
Because sites like that are as much about thinking as they are about coding.

> it took 8 min 50 seconds to compute because i had to count from 100 to 12375 dividing each triangular number calculated by its self down to 1.
In particular, there's usually a quick and simple way to code the problem, which takes way too long.

Or there is another way which involves doing some research on the problem.
In the end, you implement a much smarter answer that takes say 30 seconds rather than 10 minutes.

For sites which allow you to upload your code for an online score, your initial solution would have been rejected with "time limit exceeded".
Depending on the nature of the problem, you're given memory and time constraints in which a solution must run.

It's like sorting.
Most people come up with some variation of bubble sort the first time they try it.
Sure it works fine for an array of 10 numbers, but give it a few million and watch the run time explode.
Then you do research and implement quick-sort instead.

The large numbers are there to expose flaws in your thinking, because the simple approaches just take way too long.

> is there a better source of simple problems to practice with
Maybe - The 10 Most Popular Coding Challenge Websites [Updated for 2021]
But most are not going to remain simple for very long.

3. thanks for the response. It occurred to me this morning after reading your reply that maybe finding the factors of a number could be done recursively.

after several hours reading up on recursion and trying different things all i have achieved is a dent in the wall and a flat spot on my skull.

i found this code on the internet
Code:
```int factors(int n, int i)
{
int count = 0;
// Checking if the number is less than N
if (i <= n)
{
if (n % i == 0)
{
count += 1;
}

// Calling the function recursively
// for the next number
return count + factors(n, i + 1);
}
return count;
}```
but playing with it and stepping through the code line by line all it does is count from 1 to n+1 where the for loop beaks and then back down again to 1. I don't understand how that saves time infact as i was counting from n down to 1 and trying each individual number the above function does twice the work surly

many thanks
ben

4. Recursion doesn't solve the problem any quicker than the equivalent loop.

You need a fundamentally better algorithm if you want to get 10 minutes down to 1 minute (or less).

A URL to the actual problem on PE might be better, so we know what you're actually trying to solve.

5. here is the link #12 Highly divisible triangular number - Project Euler

this is the code i have so far however it causes a seg fault when base hits 591

Code:
```#include <stdio.h>
#include <stdlib.h>

long long int factors( long long int, long long int );

int main()
{
long long int iFactor = 0, iBase = 590;
long long int iTrinum = 174345;

//loop untill ifactor is greater than 140
while ( iFactor <= 140 )
{
//increment base by 1
iBase += 1;
//add the value of ibase to the running total of itrinum
iTrinum += iBase;
//calculate the number of factors of trinum
iFactor = factors( iTrinum, 1 );
printf("triangular number = %lld and no. of factors is %lld\n\n", iTrinum, iFactor);
}
//print the triangular number that has over 500 factors
printf(" triangular number %lld has %lld factors\n", iTrinum, iFactor);

return 0;
}

long long int factors( long long int n, long long int i )
{
long long int count = 0;
// Checking if the number is less than N
if (i <= n)
{
if (n % i == 0)
{
count += 1;
}

// Calling the function recursively
// for the next number
return count + factors(n, i + 1);
}
return count;
}```
the function i wrote last night that took nearly 10 mins was
Code:
```int NumofDivisors( int x )
{
//declare function variables
int i, iDivisorCount = 0;

//loop counting down from x to 1
for ( i = x; i >= 1; i-- )
{
//test if x is divisable by i
if ( x % i == 0 )
{
//i is a multiple of x so increment idivisorcount by 1
iDivisorCount += 1;
}
}

//return the number of multiples found
return iDivisorCount;
}```

6. > this is the code i have so far however it causes a seg fault when base hits 591
Highly recursive functions eat a lot of stack space.

7. i take it i'm barking up the wrong tree then with recursion.

8. ok now i am completely confused.

to recap some fundamentals....

Code:
`x *= y  /*same as*/ x = x * y`
order of operations is * / + -

so how the hell can....
Code:
```int x = 2, y = 2;

x *= y + 1 == 6 /*not*/ 5!!!```

9. Originally Posted by cooper1200
ok now i am completely confused.

to recap some fundamentals....

Code:
`x *= y  /*same as*/ x = x * y`
order of operations is * / + -

so how the hell can....
Code:
```int x = 2, y = 2;

x *= y + 1 == 6 /*not*/ 5!!!```
Calc right hand side, (y+1) then multiply the left hand side by that value.

I am going to give that puzzle a try... long time sicne I did any project Euler.

10. Originally Posted by hamster_nz
Calc right hand side, (y+1) then multiply the left hand side by that value.
Is that the rule or the way it works some times?????
i saw on one of the videos i watched about recursion he ended up with
Code:
`return somefunc( x + 1, x + 2)`
and said the function will work on the right hand first.

Originally Posted by hamster_nz
I am going to give that puzzle a try... long time since I did any project Euler.
They are kinda fun in a strange way. but i have learnt a couple of things like the middle part of a for loop doesn't have to be the same as the first part ie
Code:
`for ( i = 0; some_other_variable <= 500; i++ )`
however looking through the coded solutions rather than just checking my final answer was correct some bits are a little cleaver for the sake of being so or so it appears for example
Code:
```iTotal += a3 * !(a3 % 2);
//Rather than
if (a3 % 2 == 0 )
{
iTotal += a3;
}```

11. Code:
`x *= y  /*same as*/ x = x * y`
Nope
Code:
`x *= y /*is the same as*/ x = x * (y)`
So
Code:
`x *= y + 1 /*is the same as*/ x = x * (y + 1)`
The number of factors can be calculated by finding only the prime factors then multiplying the exponents of the prime factors (i.e., how many times they occur) plus one together. E.g., if the number is 360 = 2*2*2*3*3*5 then the number of factors is 4 * 3 * 2 = 24.
Code:
```#include <stdio.h>

int main() {
// Loop through triangular numbers
for (int i = 1, n = 1; ; n += ++i) {
int m = n, nfacts = 1, cnt = 0;

// Calculate number of factors
for (int d = 2; m > 1; ) {
if (m % d == 0) {
++cnt;
m /= d;
}
else {
nfacts *= cnt + 1;
cnt = 0;
++d;
}
}
nfacts *= cnt + 1;

if (nfacts >= 500) {
printf("%5d %8d %5d\n", i, n, nfacts);
break;
}
}

return 0;
}```
Result: the 12375th triangular number, 76576500, has 576 factors.

12. Originally Posted by john.c
Code:
`x *= y  /*same as*/ x = x * y`
Nope
Code:
`x *= y /*is the same as*/ x = x * (y)`
So
Code:
`x *= y + 1 /*is the same as*/ x = x * (y + 1)`
The number of factors can be calculated by finding only the prime factors then multiplying the exponents of the prime factors (i.e., how many times they occur) plus one together. E.g., if the number is 360 = 2*2*2*3*3*5 then the number of factors is 4 * 3 * 2 = 24.
Code:
```#include <stdio.h>

int main() {
// Loop through triangular numbers
for (int i = 1, n = 1; ; n += ++i) {
int m = n, nfacts = 1, cnt = 0;

// Calculate number of factors
for (int d = 2; m > 1; ) {
if (m % d == 0) {
++cnt;
m /= d;
}
else {
nfacts *= cnt + 1;
cnt = 0;
++d;
}
}
nfacts *= cnt + 1;

if (nfacts >= 500) {
printf("%5d %8d %5d\n", i, n, nfacts);
break;
}
}

return 0;
}```
You are double-counting some 'degenerate' solutions.

Result: the 12375th triangular number, 76576500, has 576 factors.
The 'x'th triangular numbers have the formula (x)(x+1)/2. You want both (x+1) and x to have lots of unique prime factors as this will give x(x+1)/2 to have lots of factors.

Using this knowledge you can filter candidates, and you only need to work with numbers less than x+1.

Pick a hopeful value for x,
factorize x and x-1,
remove a factor of '2' from one of those,
see how many unique combinations of the factors are left.

Then also test x and x+1.

13. Actually I'm overthinking it...

Code:
```#include <stdio.h>

int main(int argc, char *argv[])
{
int j = 1;
int x = 1;

while(1) {
int n = 2;   // Start with two known factors - itself and 1
for(int i = 2; i*i <= x; i++) {
if(x % i == 0) {
if(x == i*i)
n+=1;
else
n+=2;
}
}
printf("The %dth triangular number, %d has %d factors\n",j,x,n);
j++;
x+=j;
if(n>=500)
break;
}
return 0;
}```
Runtime is under a second on my laptop.

14. Mine is quite a bit faster.
Code:
```/*
First with F or more factors:
F       Number     Index  Factors
500     76576500   12375th      576
1000    842161320   41040th     1024
1200   3090906000   78624th     1280
1500   7589181600  123200th     1512
2000  49172323200  313599th     2304
(The over 1500 and 2000 factors need 64 bits.)
*/
#include <stdio.h>
#include <inttypes.h>

#define NFACTS_GOAL 500

#if NFACTS_GOAL <= 1280     // over 1280 requires 64 bits
#define TYPE      uint32_t
#define TYPE_PRN  PRIu32
#else
#define TYPE      uint64_t
#define TYPE_PRN  PRIu64
#endif

int main() {
// Loop through triangular numbers (up to limit of data type)
for (TYPE i = 1, n = 1, prev = 0; n > prev; n += ++i) {
TYPE m = n, nfacts = 1, cnt = 0;

// Count factors of 2
while (m % 2 == 0) {
++cnt;
m /= 2;
}
nfacts *= cnt + 1;
cnt = 0;

// Count odd prime factors
for (TYPE d = 3; m > 1; ) {
if (m % d == 0) {
++cnt;
m /= d;
}
else {
nfacts *= cnt + 1;
cnt = 0;
d += 2;
}
}
nfacts *= cnt + 1;

if (nfacts >= NFACTS_GOAL) {
printf("%5" TYPE_PRN " %10" TYPE_PRN " %4" TYPE_PRN "\n",
i, n, nfacts);
break;
}

prev = n;
}

return 0;
}```

15. Originally Posted by john.c
Mine is quite a bit faster.

Code:
```\$ time ./a
The 560th triangular number 157080 has 128 factors
The 2079th triangular number 2162160 has 320 factors
The 12375th triangular number 76576500 has 576 factors
The 41040th triangular number 842161320 has 1024 factors
The 313599th triangular number 49172323200 has 2304 factors
gcc -o bThe 1890944th triangular number 1787835551040 has 4480 factors

real    0m9.750s
user    0m9.751s
sys     0m0.000s

\$ time ./john-c
1890944 1787835551040 4480

real    15m21.553s
user    15m21.543s
sys     0m0.010s```
It's a little bit more code, but works pretty well:

Code:
```The 560th triangular number 157080 has 128 factors
The 2079th triangular number 2162160 has 320 factors
The 12375th triangular number 76576500 has 576 factors
The 41040th triangular number 842161320 has 1024 factors
The 313599th triangular number 49172323200 has 2304 factors
The 1890944th triangular number 1787835551040 has 4480 factors
The 10497024th triangular number 55093761676800 has 8640 factors
The 37425024th triangular number 700316229412800 has 16128 factors
The 302464799th triangular number 45742477468287600 has 34560 factors```