Archive

Posts Tagged ‘prime’

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


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.

Here I’m not finding the divisors of all the numbers instead, using the formula

if your number n = a^x * b^y * c^z (where a, b, and c are n’s prime divisors and x, y, and z are the number of times that divisor is repeated) then the total count for all of the divisors is (x + 1) * (y + 1) * (z + 1)

Algorithm to find the solution is:

package projecteuler;
/**
*
* @author Vasanth Raja Chittampally
*/
public class ProjectEuler {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
long sum=0;
out:for (int i = 45000; ; i++) {
sum=i*(i+1)/2;
boolean isPrime=true;
for(int k=2;k<=Math.sqrt(sum);k++)
{
if(sum%2==0)
{
isPrime=false;
break;
}
else if(sum%k==0) {
isPrime=false;
break;
}
}
if(isPrime) continue out;
long no=sum;
int div=2;
int count=0;
int noOfDiv=1;
long temp=no;
while(no%2==0)
{
no=no/2;
count++;
}
div++;
noOfDiv=noOfDiv*(count+1);
count=0;
while(no!=1) {
count=0;
while(no%div==0)
{
no=no/div;
count++;
}
div+=2;
noOfDiv=noOfDiv*(count+1);
}
if(noOfDiv>=500) {
System.out.println(“”+sum);
break;
}
}

}

}

I tested it with java worked fine and got the answer correct. I don’t want to post the answer here. Try out yourself.

Advertisements

What is the sum of all primes below two millions?


The idea to minimize the amount of time is that, if a number has factors other than 1 and itself must exist between 2 and square root of that number.

The above constraint reduces innumerable number of comparisons and saves a lot of space too.

Here is the code to find the sum of all primes below two millions.

<blockquote>package projecteuler;

/**
*
* @author Vasanth Raja Chittampally
*/
public class ProjectEuler {

public static void main(String[] args) {
long sum=2;
out: for (long i = 3; i &lt; 2000000; i++) {
if(i%2==0)
continue out;
for (int j = 3; j &lt;=Math.sqrt(i); j+=2) {
if(i%j==0) continue out;
}
sum+=i;

}
System.out.println(""+sum);
}</blockquote>