# Project Euler – Problem 3

The solution down there is wrong, I will update this post as soon as I got my math right.

Update:The right solution is list at the very end of the post.

## Wrong Solution

I have been trying to solve puzzles of Project Euler, they are quite interesting. So I am thinking of writing down some solutions to these puzzles.

The first one I want to discuss is Problem 3, which asks the following question:

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

And the first version of my solution is quite naive, and it takes a long time to compute the result. Here is the code( I just found that crayon do not support Scala, so I used the python highlight):

The problem of the previous algorithm is that the _LPF function searches for the largest prime factor from the number itself down to 2, which is correct, but not efficient if the largest prime factor is far smaller than the number. So I modified the _LPF function to be like this:

This time the program runs for less 1 second to give the first 4 prime factors, but I still have to wait a freaking long time for the program to terminate to see if this 4 factors are all prime factors of that big number, which is still not quite efficient for this problem. So more improvement has to be made.

So the trick is line 6, I changed it to the following code, I will explain why later:

So as you can see we shrink the size of the number by b if we ever find a prime factor b of that number, in another work, the the largest prime factor of number n is also the largest prime factor of n/(k1k2…) where k1, k2… is smaller prime factors. So why this is true? I will provide a formal proof to this later.

## Right solution

First I got the definition of prime factors wrong, according to Wikipedia , a number n’s prime factor is a series of prime numbers $P_0,P_1,P_2...$ where $n = {P_0}{P_1}{P_2}...$, so I overcomplicated this problem before, and the right solution is quite simple in Scala. The code is list below:

# Introduction

Before I begin this long (I assume it will be long since computer science is quite a broad topic), I would first introduce myself a little bit to give you a rough feeling of the position where I stand to discuss computer science.

I am a second year BEng Computer Science and Electronics student at University of Bristol, UK. The course is a combined one of computer science and electronics engineering. So it consists of a wide range units from low-level digital circuits and system all the way up to high-level languages like Java and Haskell. Before I attended my uni I learned how to program in C in China. I am fluent in C, Java and Python, also I have tried Haskell, Scala and ARM assembly. For hardware side, I am familiar with digital design with VHDL.

Besides these languages, I was also taught with some traditional engineering knowledge, like calculus, statistics, signals and systems, and control theory. I also learned something about communications, linear circuits and amplifiers, although I am not sure how and why these knowledge may benefit my later work. But I guess giving a comprehensive tour around the electronics computer industry is good since it will enable us to choose the right path for our career.

The first thing got me interested in computer science is programming. For some unknown reasons, I feel good about myself when I am programming. I guess it is the cheapest way for a person to create/build up something that is both fun and useful, basically you just need a working computer. But after two years’ study in this field. I found myself more curious about theoretical computer science. I like theory of computation (turing machine and lamda calculus), data structures and algorithms. Another question get my attention is about parallel computing. Since the Moore’s law has reached its peak, I believe, as many others, that the future of computation is paralleled. And programming a multicore computer is hard. So we need to get a new programming model to deal with this. I will discuss this in detail later.

This blog is a summary of my knowledge of computer science. Like many other articles up on the internet, I will constantly update this as I gain deeper understanding about computer science along my study in this field. The main audience of this article should be high school students thinking about taking computer science as major in college or other computer science students who can point out where I got my understanding wrong, and willing to share their own computer science experience with me.