Skip to main content

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





Labels:

Popular posts from this blog

Making a quiz web app with python and flask

Edit : When you are creating a web app with h tml templates, then y ou will have to sa ve the html file in templates folder in the Current Wor ki ng Directory( CWD). If you save the file in the C W D directl y you will get a TemplateNotFound error. Thank you Udhay for pointing it out.   In this post we will create a quiz website using python . I will be using the flask framework . After reading this tutorial you will learn form submission , flask templates , python code in flask templates , shuffling the questions and options with the random module and few others.  Please note that this tutorial is not big as it seems to be. Some of the code has been rewritten to maintain consistency and also font size is somewhat big so that your eyes won't get stressed reading this tutorial. Also the content has not occupied the full width of the page. In this tutorial I am assuming that you are having a very basic understanding of the flask framework . Please refer the documentation
Read more

Problem 11 Project Euler Solution with python

Largest product in a grid In the 20×20 grid below, four numbers along a diagonal line have been marked in red. 08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 04 52 08 83 97 35 99 16 07
Read more

Problem 60 Project Euler Solution with python

Prime pair sets The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property. Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime. This problem is j u st a brute force problem. If you have come here because you don't know the limit upto which you will h ave to gener ate the prime numbers t hen go ahe ad and t r y with 10,000 . When I first start ed solving the problem I chose 1 million(beca use most of the problem s on project E uler have this limit ), but it took very long for the computer to fin d the solution. After searching on the internet then I found many people choosing 10, 000 so I have changed my in put f rom 1 million to 10000 and the output was f ast. He
Read more