Projecteuler.net: Problem3: Matlab: Find the largest prime factor

Problem 3 - projecteuler.net

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

Solution: 

To solve this problem we will be using two loops namely for loop and the while loop. We will also use the rem( ) function. This program takes a very little time to generate the solution. The program is as follows:

Find the explanation below the program

Program

function prime_factor(n)

%this function will find the largest prime factor of a given number

for i = 2:1000000
    while rem(n,i) == 0
        n = n/i;
        fprintf('Yay, %d is a factor, now we should test %d  \n',i, n);
        if n == 1 || n == i
            fprintf('%d\n',i);
            break;
        end
    end
end

Explanation:

First of all the function takes the number as argument. Now a for loop is generated in the range of values 2 to 1000000 (why have I used numbers only till 1000000? Find it after this section). A while loop is iterated to check whether the given number is divisible by the iterator(i) if yes then the number is divided by the given number and then the remaining number is again checked for the same. It should be noted that while checking the iterator generated for satisfying while loop condition is a prime number and for each iteration the number is greater than or equal to the previous iterator. Thus in-directly we will iterate through the prime numbers and check if the number n is divisible by the prime number iterator. Let us take an example to clearly understand this function.

We have to find the largest prime factor for the number 13195. we will pass this number through the prime_factor function. Now in the prime factor function

A for loop is created from numbers 2:1000000

For the first iteration, number 2 is created and will check for the while loop condition and fails to start the while loop. Similarly this continues till the iterator is 5 and  this time the condition is satisfied and will enter the while loop and will divide the number 13195 with 5, the result is 2639. After execution of this iteration in the while loop once again the condition is checked whether the number 2639 is divisible by 5, it is not and so the for loop iteration is executed and the iterator is increased and the while loop condition is not satisfied until the number is 7. At 7 the number becomes 377, after that the while loop condition is satisfied at 13 and the number becomes 29, next the while loop condition gets satisfied at 29 while is equal to the number(n). In the while loop the there is a if statement whose condition is that if the number is equal to the iterator or if the number is equal to 1 then break the loop. After breaking the loop, the iterator generates number from 29 to 1000000 and all the numbers thus generated will not satisfy the while loop condition and thus the output is 29.

Why have I used numbers only till 1000000?

We can also use the numbers upto n-1, i.e. numbers excluding 1 and itself, but as for our present problem the number 600851475143 is a very large number and the for loop iterates for these many times and will take time for execution. So I have used numbers only till 1000000, you can also use 100000 which will give more faster output rather than 1000000.

The idea of the solution has been taken from here:  Project Euler 3 - Why does this method work?

Find the pdf version of this program here: problem3_matlab_projecteuler.pdf

You can download a copy of the matlab file of the above function here: prime_factor.m

This problem has been derived from projecteuler.net and can be found here: problem 3

Run the program and comment below the output you are getting for a given input.

Keywords: matlab function, projecteuler.net, problem3, largest prime factor