Problem 007 : 10001st Prime

10001st prime

Problem 7

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10 001st prime number?

                                                                                                           https://projecteuler.net/problem=7
Problem 7 is about prime generation.

The efficiency of this problem can differ based on which algorithm we take.

We might want to use sieve for this problem, yet since we don't know the exact limit, we cannot use it (unless it will become more inefficient algorithm).

We will look at the algorithm that determines whether a number is a prime.

public static boolean isPrime(int n)
{
     if (n <= 3) return n > 1;
     else if (n % 2 == 0 || n % 3 == 0) return false;
     else
     {
      for (int i = 5, end = (int)Math.sqrt(n); i <= end; i += 6)
      {
       if (n % i == 0 || n % (i + 2) == 0) return false;
      }
     }
     return true;
}

This is by far the most efficient algorithm for checking primality of an integer.

We will use while loop until we reach our target, 10001st prime number.

Quick trick would be an increment of the integer by 2, since all even numbers cannot be prime.

Answer is 104743
Execution time is 8 ms, or 0.008 seconds
Source code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem007.java

Problem 006 : Sum Square Difference

Sum square difference

Problem 6

The sum of the squares of the first ten natural numbers is,

1² + 2² + ... + 10² = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + ... + 10)² = 55² = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640.
Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

                                                                                                           https://projecteuler.net/problem=6

Problem 6 is a really simple problem if you know how to use for loop.

However, just like problem 1, I used formula to solve this problem, instead of for loop.

The formula for the sum of first n integers is:

n * (n + 1) / 2

The formula for the sum of first n squares is:

n * (n + 1) * (2n + 1) / 6

Therefore, the sum of the squares is:

int sumsquare = (NUM*(NUM+1)*(2*NUM+1))/6; //sum of the squares

and the square of the sum is:

int squaresum = (int)Math.pow((NUM)*(NUM+1)/2, 2);  //square of the sum

Answer is 25164150

Execution time is 0.8 ms, or 0.0008 seconds

Source code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem006.java

Problem 005 : Smallest Multiple

Smallest multiple

Problem 5

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

                                                                                                           https://projecteuler.net/problem=5

Problem 5 is about GCD and LCM.

GCD : greatest common divisor

LCM : least common multiple

The problem already told us that 2520 is smallest number that is divisible by numbers from 1 to 10, or it is the LCM of numbers from 1 to 10.

Now we need to find LCM for 1 to 20.

Here is a simple math.

Let's say we have two integer, A and B.

And we know that G is the greatest common divisor of A and B.

Then we can write them in this way:

A = Ga

B = Gb

where a and b are relatively prime to each other.

Also, least common multiple must be divisible by both A and B but need to be as small as possible.

LCM = Gab

How do we get LCM directly from A and B?

LCM = Gab

Gab = G² ab / G = Ga * Gb / G = A * B / G

Therefore,

LCM = A * B / G

Here is recursive solution to find GCD for long a and long b:

public static long gcd(long a, long b)
{
    if (b == 0) return a;
    else return gcd(b, a%b);
}

The solution uses the Euclidean Algorithm for finding GCD:

Let's say there are two positive integer A, B A > B > 0

A = qB + R₀
B = qR₀ + R₁
R0 = qR₁ + R₂
…
R_N-1 = qR_N + 0

∴ GCD = R_N

and here is solution for LCM for integer for long a and long b:

public static long lcm(long a, long b)
{
    return a*b/gcd(a,b);
}

Answer is 232792560
Execution time is 2 ms, or 0.002 seconds
Source code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem005.java

Problem 004 : Largest palindrome product

Largest palindrome product

Problem 4

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.

                                                                                                           https://projecteuler.net/problem=4

Problem 4 is about palindrome number.

The term "palindrome" is applicable for words, numbers, and any phrases.

(i.e. "race car" can be reversed to "rac ecar" which reads "race car")

(i.e. "1234321" can be reversed to "1234321" which is same as before)

(i.e. the longest palindromic phrase known starts with "a man, a plan, a cameo, .."

       and ends with "...., a canal, Panama!")

When we reverse number, we can manually divide each digit and recreate a reversed number, but that way will take a long time to compute and therefore inefficient.

Instead, we can convert number into string and reverse string using StringBuffer.

The source code is right here below:

public static boolean isPalin(String n)
{
    return (new StringBuffer(n).reverse().toString().equals(n));
}

We now need to think about finding the largest product.

Our approach will take from the largest 3-digit integers, since that way we can reduce execution time a lot. Starting with i = 999, we will automatically stop when the next i is less than square root of the largest product found so far, since smaller i from that point will never produce larger product.

In the nested for loop, we will stop the loop when the product is less than the product found. Because we are reducing the value of j, further calculation is unnecessary for it will produce smaller product.

int ans = 0;
for (int i = 999; i >= Math.sqrt(ans); i--)
{
    for (int j = i; j >= 100; j--)
    {
        int temp = i*j;
        if (temp < ans) break;
        else if (isPalin(String.valueOf(temp))) ans = temp;
    }
}

Answer is 906609
Execution time is 6 ms, or 0.006 seconds
Source code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem004.java