Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
branch: master
Fetching contributors…

Cannot retrieve contributors at this time

66 lines (49 sloc) 1.312 kb
/*
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?
Ans: Find no of factors for all numbers till we get a triangular
number with over 500 divisors.
We can safely assume that max prime factor in that triangular numbers < 20
If F(n) = no of factors in n
then F(n) = (c+1)*F(l) where n = p^(c+1) * l // p is smallest prime in n
*/
#include<stdio.h>
#define MAX 10000
int main()
{
int primes[]={2,3,5,7,11,13,17,19,0};
int factors[MAX]={0};
int i,j,c,n;
factors[0]=factors[1]=1;
factors[2]=factors[3]=2;
for(i=4;i<MAX;++i){
n=i;
for(j=0;primes[j];++j){
c=0;
while(n%primes[j] == 0){
c++;
n/=primes[j];
}
if(c){
factors[i]=(c+1)*factors[n];
break;
}
}
if(factors[i]==0)
factors[i]=2;
}
for(i=0;i<MAX;i++)
printf("%d ",factors[i]);
return 0;
}
Jump to Line
Something went wrong with that request. Please try again.