Project Euler Problem#12 solution in C++

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …

Let us list the factors of the first seven triangle numbers:

 1: 1
 3: 1,3
 6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

Solution:


#include <cstdio>
#include <cmath>

int numDivisors(int num)
{
int divisors = 1, exp;

//handle 2 and 3 as special case
exp = 0;
while (num % 2 == 0) {
num /= 2;
exp++;
}
divisors *= (exp+1);

exp = 0;
while (num % 3 == 0) {
num /= 3;
exp++;
}
divisors *= (exp+1);

//the other primes are 6k +/- 1
int i = 5;
int root = floor(sqrt(num));
while (i <= root) {
exp = 0;
while (num % i == 0) {
num /= i;
exp++;
}
divisors *= (exp+1);

if (i % 6 == 1)
i += 4;
else
i += 2;
root = floor(sqrt(num));
}

//a single largest prime factor
if (num != 1)
divisors *= 2;

return divisors;
}

int main(void)
{
int n = 0;
int divisors = 0;

while (divisors <= 500) {
//while (n <= 10) {
n++;

//since t = n*(n+1)/2 and gcd(n,n+1)=1
if (n % 2 == 0)
divisors = numDivisors(n/2) * numDivisors(n+1);
else
divisors = numDivisors(n) * numDivisors((n+1)/2);
}

printf("%d - %ld: %d\n", n, (long)n*(n+1)/2, divisors);
}
Advertisements

About Khuram Ali

Programming... Programming and Programming...!!!

Posted on May 23, 2013, in Project Euler and tagged , , , , , , , , , . Bookmark the permalink. 5 Comments.

  1. #include
    #include
    using namespace std;
    int main()
    {
    int i=1,j,sum=0,count;
    while(i)
    {
    sum+=i;
    for(j=1;j5)
    {
    cout<<sum;
    exit(1);
    }
    }
    count=0;
    i++;
    }
    return 0;
    }
    I tried out working with this one but it is giving wrong output bt i nt able to figure out the mistake..please help me out..

  2. #include
    #include
    these are first two lines

  3. sorry..i dont know why it is not getting posted correct..
    first is iostream second line stdlib.h
    contion of for loop is:j=1;jless than =sum;j++

  1. Pingback: Project Euler Problem#13 solution in C++ | Khuram Ali

  2. Pingback: Project Euler Problem#14 solution in C++ | Khuram Ali

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: