MYTUTOR SUBJECT ANSWERS

86 views

Project Euler Question 3: What is the largest prime factor of the number 600851475143?

To answer this question you must first fully understand what prime factors are. Any positive integer number can be 'split' down into a product of its prime factors, that is, the number can only be made by multiplying a collection of primes together. For example, 42 = 2*3*7, therefore the set of prime factors of 42 are [2, 3, 7]

Okay, now that that is sorted we can begin to answer the question. 

Note: This question requires the use of conditional statements (if, else if, and else) and while loops. If you are struggling with these concepts please get in touch, I would be glad to help.

I used several functions in my answer to this question, those are 'isPrime(number)' and then the main 'primeFactorization(number)' function.

'isPrime(number)' returns a boolean 'True' if the inputted number is prime, and 'False' otherwise. 

Note: the implementation of 'isPrime()' is a whole other question in itself, I will try to upload a question/answer shortly.

The overview of the primeFactorization(number) method is as follows:

Note: if a number is prime, then its only prime factor is itself

Note: This problem requires the knowledge of modulo division. The result of A mod B will be the remainder if A were to be evenly devised by B. For example, 17 mod 5 = 2, as 17 = (5*3) + 2. (If A mod B = 0, then A is an exact multiple of B - this is the way in which we will be using mods)

To start, we need a variable to hold a copy of the number that we are trying to factorise, note that this is not the original input number, just a copy, so we are okay to edit it as the calculation progresses, I called mine factorMe

We also need an empty container to store the factors as we find them, I used a simple list called 'factors'

We also need a variable to keep track of the prime that we are currently using, this should be equal to 2 to begin with, and we will change it as the while loop progresses. I called this variable 'factorizingPrime'

Finally we need a boolean value that tells us whether or not our number has been completely factorised, and hence when we can break out of the while loop. I called this variable 'factored', and it is set to False to begin

primeFactorization(number)

factorMe = number

factorizingPrime = 2

factors = [ ]

factored = False

while ( not factored )      {   

if factorMe isPrime()       (ie It is its own only prime factor)

add factorMe to the list of factors, we are all done!

break the while loop here (set factored to True)

else, if factorMe mod factorizingPrime == 0 (see above note)

update factorMe = factorMe / factorizingPrime

add factorizingPrime to the list of factors

 else

the current factorisingPrime does not evenly divide

the factorMe variable, so is not a prime factor,

update the factorisingPrime with the nextPrime()

and the while loop will continue to run

}

Nearly there! 

When that while loop exits, stored in the list factored will be all of the prime factors of the number you inputted!

Now it is as simple as finding the largest element in the list, and you've answered Project Euler Question 3, congratulations

Project Euler is a great free bank of complex programming problems, and I would strongly recommend you have a look.

If you want to talk about this solution, or have any other questions, do not hesitate to get in touch.                 

Happy coding, 

Tom

Tom E. A Level Computing tutor, IB Computing tutor, GCSE Computing tu...

2 months ago

Answered by Tom, who has applied to tutor A Level Computing with MyTutor

Still stuck? Get one-to-one help from a personally interviewed subject specialist

4 SUBJECT SPECIALISTS

£20 /hr

Michael T.

Degree: MMath (Masters) - Durham University

Subjects offered: Computing, Physics+ 1 more

Computing
Physics
Maths

“About Me: I am currently studying Mathematics at Durham University. Maths can sometimes be intimidating, but it's that which makes it so rewarding when it all starts to make sense. I have been teaching in one form or another since 13...”

£20 /hr

Kyle C.

Degree: Computer Science With Electronics (Bachelors) - Edinburgh University

Subjects offered: Computing, Physics+ 1 more

Computing
Physics
Maths

“Who am I?I am a student pursuing a Computer Science degree at the University of Edinburgh. I enjoy working on theatre lighting and am also a keen fencer which is where I initially started teaching by coaching younger fencers.Sessio...”

£20 /hr

Kerr M.

Degree: Computational Physics (Bachelors) - Glasgow University

Subjects offered: Computing, Physics+ 1 more

Computing
Physics
Maths

“The name's Maxwell, Kerr maxwell. I'm a student studying for a degree in Computational Physics at the Univerity of Glasgow. I have a passion for all things science and maths and I look foreward to sharing that with you during our tuto...”

MyTutor guarantee

About the author

£20 /hr

Tom E.

Degree: Computer Science (Masters) - Bristol University

Subjects offered: Computing, Science+ 4 more

Computing
Science
Physics
Maths
ICT
Further Mathematics

“Hey! My name is Tom, and I am very glad you're reading this! I am currently studying for a Masters in Computer Science at the University of Bristol, whose Computer Science department is consistently in the top 5 in the UK. In universi...”

MyTutor guarantee

You may also like...

Other A Level Computing questions

What is the denary equivalent of the hexadecimal number A7?

Project Euler Question 3: What is the largest prime factor of the number 600851475143?

What is the difference between a variable and an identifier?

How do you convert from binary to decimal?

View A Level Computing tutors

Cookies:

We use cookies to improve our service. By continuing to use this website, we'll assume that you're OK with this. Dismiss

mtw:mercury1:status:ok