So, this problem asked us to find the first triangular number that has over 500 divisors.
When I was solving this, I totally forgot about the triangular part so I tried to find the first instance of number that had over 500 divisors. (It was 14414400)
When I ran that code, it took almost 2 minutes to arrive at an answer! Other than that, the answer was wrong too! (duh..)
After carefully reading the problem again, I fixed "n++" to "n += i++" to only check for triangular numbers.
The problem was solved using Trial Division method.
#include <stdio.h> #include <stdlib.h> #include <math.h> int main() { long int n = 0; long int i = 1; while (findNumberOfDivisors(n) < 500){ n += i++; //Used n++ when I understood the problem wrong. } printf("%ld\n", n); return 0; } int findNumberOfDivisors(long n){ int number = 2; int squareRoot = (int) sqrt(n); long int i; for (i = 2; i <= squareRoot; i++){ if (n % i == 0){ number += 2; } } if (squareRoot * squareRoot == n) number--; return number; }
Best Execution Time: 0.205s
Answer:
hey can anyone help me reduce the runtime of the following peice?
ReplyDelete#include
main()
{
int n=1,m,c,i;
while(1)
{
c=0;
m=(n*(n+1))/2;//triangular no.
for(i=1;i<=m;i++)
{
if(m%i==0)
c++;
}
if(c>500)
{
printf("triangular no. with over 500 divisors is\t%d\t",m);
break;
}
n++;
}
}