Friday, June 28, 2013

[Project Euler] Problem 12 in C

Problem: Project Euler Problem 12

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:

1 comment:

  1. hey can anyone help me reduce the runtime of the following peice?
    #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++;

    }
    }

    ReplyDelete