Problem 003 : Largest Prime Factor

Largest prime factor

Problem 3

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

                                                                                                           https://projecteuler.net/problem=3

Problem 3 is about prime factorization.

Before we get into the problem, let's talk briefly about prime numbers and factorization.

(I will talk about prime numbers and primality more specifically in later problems.)

Here are some properties that we need to know:

1. Except for 2, all prime numbers are odd numbers.

2. When we divide a number, there is always a pair of divisors except for perfect squares.

    For example, if we look at divisors of 12 : 1, 2, 3, 4, 6, 12

    we can easily find three pairs (1, 12), (2, 6), (3, 4)

    and each pair will have a product of original number (which is 12 in this case).

    So we can conclude that if 12 is divisible by 1, then it is divisible by 12 for sure.

                                            if 12 is divisible by 2, then it is divisible by 6 for sure.

                                            if 12 is divisible by 3, then it is divisible by 4 for sure.

    We now divide them into two groups: smaller group (1, 2, 3) and larger group (4, 6, 12).

    And we see that the dividing borderline is between 3 and 4.

    This dividing borderline can be calculated by taking square root of 12, which is 3.4641

    Therefore, when we want to test divisibility, we just need to test divisors up to the square root of
    the original number, and we can raise efficiency by removing redundancy of calculation.

    One exception is when we have a perfect square, because the square root of perfect square is an

    integer, which cannot be a clear dividing borderline of divisors.

    For example, if we look at the divisors of 16: 1, 2, 4, 8, 16

    We get an odd number of divisors. Also, 4 can be either smaller or larger group.

    This is the reason that when we make an universal solutions for finding factors, we need to include
    square root of the number: from i = 2 up to i <= sqrt (original number)

In this problem, our number is 600851475143, which is neither an even number nor a perfect square.

Because it is not an even number, we don't need to divide it by 2. As stated above, all prime numbers other than 2 are odd, and we just need to test odd divisors; starting with i = 3, we can increment by 2 so that we can test just odd numbers (3, 5, 7, ...).

If we continue dividing a number by 3 (if it is divisible by 3) until it cannot be divided further, then the remnant is not multiple of 3 anymore. Do the same process for 5 and 7. When we reach divisor 9, it is not a prime factor since 9 is not a prime number. But we don't need to worry about it since we got rid of all the 3's from the number in earlier step. This is how we can do prime factorization without explicitly checking if the divisor itself is a prime number.

When we reach to the point where the number cannot be divided by any divisors smaller than its square root, then that remaining number would be the last number of our prime factorization, which is the answer to the problem.

public static void run()
{
    long d = 600851475143L;
 
    for (int i = 3; i < Math.sqrt(d); i+=2)
    {
         if (d%i == 0)
             while (d%i == 0) d /= i;
    }
    System.out.println(d);
}

Answer is 6857

Execution time is 2 ms, or 0.002 seconds

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

I also made a universal solution for finding largest prime factor of a number in source code, so if you need any help about that, feel free to leave comment and ask questions.

public static int getLargestPrimeFactor(int n)
{

    if (n == 1) return 1; 
    if (n%2 == 0) while (n%2 == 0) n /= 2;
    if (n == 1) return 2;
  
    int i = 3;
    for ( ; i <= (int)Math.sqrt(n); i+=2)
    {
        if (n%i == 0)
             while (n%i == 0) n /= i;
    }
    i -= 2;
    if (n == 1) return i;
    return n;
}

Problem 002 : Even Fibonacci Numbers

Even Fibonacci numbers

Problem 2

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

                                                                                                            https://projecteuler.net/problem=2

Problem 2 is about Fibonacci sequence.
Actual Fibonacci sequence starts with 1 and 1 (or, sometimes 0 and 1), but because the index of each term doesn't matter in this problem, we will not worry about that.

This problem is as simple as the first one, so I just want to briefly explain how I solved it.

I set the upper limit as four million as stated, and used while-loop (current term <= limit).
By using two integer f = 1 and s = 1, I started calculating the next term by adding the previous two terms and checked if it is even integer (current term % 2 == 0)

After adding even term to the sum, I assigned f = s and s = current term so that I can reuse the integers in next calculation until the term is greater than the limit, and we will reach the answer.

private static final int LIMIT = 4000000;
 
public static void run()
{
    int f = 1;
    int s = 1;
    int fibo = 0;
    int sum = 0;
    while (fibo <= LIMIT)
    {
        fibo = f + s;
        if (fibo%2 == 0) sum += fibo;
        f = s;
        s = fibo;
    }
    System.out.println(sum);
}

Answer is 4613732
Execution time is 0.8 ms, or 0.0008 seconds
Source code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem002.java

Problem 001 : Multiples of 3 and 5

Multiples of 3 and 5

Problem 1

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.

                                                                                                            https://projecteuler.net/problem=1

Problem 1 is the first and the easiest problem in the collection.

There are multiple ways of solving this, and I will introduce two main ways.

First way, which I didn't use in my code, is to brute force through the entire 1000 numbers.

You may use for-loop from i = 1 up to i < 1000 and check if i % 3 == 0 || i % 5 == 0

Second way, which I used in my code, is to use formula for consecutive sum.

The formula for adding from 1 to integer n is n (n+1) / 2

Also, using set property,
(multiple of 3) or (multiple of 5) = (multiple of 3) + (multiple of 5) - (multiple of 3 and 5)

Sum of multiples of 3 under 1000 would be
3 + 6 + 9 + 12  + 15 + ... + 999 = 3 * (1 + 2 + 3 + 4 + 5 + ... + 333) = 3 * (sum from 1 to 333)
= 3 * (333 * 334 / 2) = 166833

Using same formula, we will get 166833 + 99500 - 33165 = 233168

public static int sumMultiple(int divisor, int num)
{
    int last = num/divisor;
    int sum = (last*(last + 1))/2;
    return sum*divisor;
}

This was one of few problems that could be solved by hand with basic algebra.

Answer is 233168
Execution time is 0.8 ms, or 0.0008 seconds
Source code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem001.java

Problem 000 : About Project Euler

Named after Leonhard Euler, the Project Euler (https://projecteuler.net/about) is a collection of problems that require skills in both mathematics and computer science. Colin Hughes created the project in 2001, and new problem is updated every week.

The general rule is that you can solve each problem under a minute with an efficient algorithm, but so far I could handle most problem with less than 0.1 seconds, or 100 milliseconds, using Java language on eclipse.

The project requires enough experience in computer programming and algorithms, yet a few problems could be solved solely by hand with sufficient mathematical backgrounds.

In this blog, I will discuss how to solve each problem using Java with some powerful algorithms and useful mathematical theories. Most solution will begin with brief discussion of mathematical concepts followed by Algorithm implementation. All of my source codes are posted in my Github blog (https://github.com/Ainodyne) and all the explanations will be posted on blogger.

The project will offer a great opportunity to learn algorithms since all the problems are based on math. As you solve each problems, you will notice that no object or graphics are required (it depends on each person, but most people including myself only use static declarations and methods throughout the programming). This is the reason that non-object oriented program languages can be used to solve the problems.