HACKER RANK Project Euler 12 - Highly Divisible Triangular Number - Solution.'C++'

Project Euler Challenges-12 - Highly Divisible Triangular Number Solution

Problem Statement

This problem is a programming version of Problem 12 from projecteuler.net

The sequence of triangle numbers is generated by adding the natural numbers. So the 7'th 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 N divisors?

Input 
First line T, the number of testcases. Each testcase consists of N in one line.

Output 
For each testcase, print the required answer in one line.

Constraints 
1≤T≤10 
1≤N≤103

Sample input

4
1
2
3
4

Sample output

3
6
6
28

Solution:

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
const int N=1000000;
const int M=100000;
int main()
{
 vector<bool> mark(N+8,false);
 vector<int> prime;
 vector<int> ans(M+10);
 for(int i=2;i<=N;++i)
 {
  if(mark[i]==false)
  {
   int b=i+i;
   while(b<=N)
   {
    mark[b]=true;
    b+=i;
   }
  }
 }
 for(int i=2;i<=N;++i)
  if(!mark[i])
   prime.push_back(i);
 mark[1]=true;
 for(int i=1;i<=M ; ++i)
  {
   int x=i*(i+1);
   int num=1;
   x/=2;
   int to=ceil(sqrt(static_cast<double>(x)));
   for(int j=0;prime[j]<=to ; ++j)
   {
    int y=0;
    while(x%prime[j]==0)
    {
     x/=prime[j];
     ++y;
    }
    if(y!=0)
     num*=y+1;
   }
   if( x!=1)
    num*=2;
   ans[i]=num;
  }
 int t;
 cin>>t;
 for(int k=1;k<=t;++k)
 {
  int n;
  cin>>n;
  for(int i=1;i<=M;++i)
   if(ans[i]>n)
   {
    cout<< (i*(i+1))/2<<endl;
    break;
   }
 }
 
}

Thanks for Visiting, Hope this helps you....