0

A simple program I wrote in C takes upwards of half an hour to run. I am surprised that C would take so long to run, because from what I can find on the internet C ( aside from C++ or Java ) is one of the faster languages. 

// this is a program to find the first triangular number that is divisible by 500 factors int main() { int a; // for triangular num loop int b = 1; // limit for triangular num (1+2+3+......+b) int c; // factor counter int d; // divisor int e = 1; // ends loop long long int t = 0; // triangular number in use while( e != 0 ) { c = 0; // create triangular number t t = t + b; b++; // printf("%lld\n", t); // in case you want to see where it's at // counts factors for( d = 1 ; d != t ; d++ ) { if( t % d == 0 ) { c++; } } // test to see if condition is met if( c > 500 ) { break; } } printf("%lld is the first triangular number with more than 500 factors\n", t); getchar(); return 0; }

Granted the program runs through a lot of data, but none of it is ever saved, just tested and passed over.

I am using the Tiny C Compiler on Windows 8.

Is there a reason this runs so slowly? What would be a faster way of achieving the same result?

Thank you!

Improve this question
13
  • 4
    Why is this tagged java/c++? Commented Aug 17, 2013 at 18:50
  • 7
    Project Euler solutions typically require mathematical insight to optimize the program. PRO_TIP: If you don't know the mathematical insight, at least use a Binary Search technique. Best help I can give without spoiling the solution for you. Commented Aug 17, 2013 at 18:50
  • 1
    e != 0 is unnecessary, although propably optimised away by a clever compiler. Btw: Did you turn compile time optimisation on? Commented Aug 17, 2013 at 18:55
  • 7
    The problem is with your algorithm, not with C; brute force techniques are inherently very slow. You can use the "fastest" programming language out there, but if you have a slow algorithm, your program will still be slow. Commented Aug 17, 2013 at 19:04
  • 3
    "I am surprised that C would take so long to run, because from what I can find on the internet C ( aside from C++ or Java ) is one of the faster languages." The language has near-nothing to do with it in this case. Its how you're using it (and usually most always is). Commented Aug 17, 2013 at 19:12

5 Answers 5

Reset to default
2

You're iterating over a ton of numbers you don't need to. By definition, a positive factor is any whole number that can be multiplied by another to obtain the desired product.

Ex: 12 = 1*12, 2*6, and 3*4

The order of multiplication are NOT considered when deciding factors. In other words,

Ex: 12 = 2*6 = 6*2

The order doesn't matter. 2 and 6 are factors once.

The square root is the one singleton that will come out of a factoring of a product that stands alone. All others are in pairs, and I hope that is clear. Given that, you can significantly speed up your code by doing the following:

#include <stdio.h> #include <stdlib.h> #include <math.h> // this is a program to find the first triangular number that is divisible by 500 factors int main() { int c = 0; // factor counter long long int b = 0; // limit for triangular num (1+2+3+......+b) long long int d; // divisor long long int t = 0; // triangular number in use long long int r = 0; // root of current test number while (c <= 500) { c = 0; // next triangular number t += ++b; // get closest root. r = floor(sqrt(t)); // counts factors for( d = 1 ; d < r; ++d ) { if( t % d == 0 ) c += 2; // add the factor *pair* (there are two) } if (t % r == 0) // add the square root if it is applicable. ++c; } printf("%lld is the first triangular number with more than 500 factors\n", t); return 0; }

Running this on IDEOne.com takes less than two seconds to come up with the following:

Output

76576500 is the first triangular number with more than 500 factors

I hope this helps. (and I think that is the correct answer). There are certainly more efficient ways of doing this (see here for some spoilers if you're interested), but going with your code idea and seeing how far we could take it was the goal of this answer.

Finally, this finds the first number with MORE than 500 factors (i.e. 501 or more) as per your output message. Your comment at the top of the file indicates you're looking for the first number with 500-or-more, which does not match up with your output message.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

Without any math analysis:

 ... do { c = 0; t += b; b++; for (d = 1; d < t; ++d) { if (!(t % d)) { c++; } } } while (c <= 500); ...
Improve this answer

13 Comments

alright that is another way to hold the loop and break it. would it make the code run any faster though?
@Charles: Depends on how clever the compiler is. I doubt a recent gcc would show any differences.
@Charles: However, did you apply any profiling on different approaches to code it?
Profiling? And after changing my while to while(c<=500) and doing away with the unnecessary if statement I now get 0 every time.
and is there a reason that you changed it from a while(test){} to a do{}while(test)? is one better than the other?
|
1

You are implementing an O(n^2) algorithm. It would be surprising if the code took less than a half an hour.

Refer to your computer science textbook for a better method compared to this brute force method of: check 1, 1 + 2, 1 + 2 + 3, etc.

You might be able to shorten the inner for loop. Does it really need to check all the way up to t for factors that divide the triangular number. For example, can 10 be evenly divisible by any number greater than 5? or 100 by any number greater than 50?

Thus, given a number N, what is the largest number that can evenly divide N? Keep reading/researching this problem.

Also, as other people have mentioned, the outer loop could be simply coded as:

 while (1) { // etc. }

So, no need need to declare e, or a? Note, this doesn't affect the length of time, but your coding style indicates you are still learning and thus a reviewer would question everything your code does!!

Improve this answer

Comments

0

You are doing some unnecessary operations, and I think those instructions are not at all required if we can check that simply.

first :

while(e!=0)

as you declared e=1, if you put only 1 in loop it will work. You are not updating value of e anywhere.

Change that and check whether it works fine or not.

Improve this answer

3 Comments

t is not always updated with 1. It's updated b and b is always increasing with 1, so t is increasingly increasing.
the while(e != 0) was just a way to hold the loop until the condition was met. then the loop is broken using break; t does not increase by 1 each time, it moves to the next triangular number.
@TimvanElsloo... Thanks for updating me... I didn`t check that.
0

One of the beautiful things about triangle numbers, is that if you have a triangle number, with a simple addition operation, you can have the next one.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.