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++;
}
}