Yesterday and today, I was trying to do problem 3 from Project Euler. If you don't know what Project Euler is, it is a neat site where there are math/programming questions that can only be solved if you write a computer program that will output the right mathematical number/answer. From there, you can just input the answer for the particular question on the site, and it will tell you if you got the right number/answer or not. If you did, then you will gain access to community discussions and even a pdf on how to properly code a program to solve that question you answered. The questions are all ranked based on how many people solved it, so you can start on the easiest questions and work your way down to the ones where less than a hundred people even solved it worldwide.

I already answered first two questions, which are the two that people answered the most (and thus, the easiest two questions). But then came question 3. The question was to find the largest prime factor of a number. The hard part is to actually determine the primality of a factor of the number. If you don't know what primality is, it's basically "whether or not the number is a prime number". Now the thing is, you could answer question 3 easily if you used certain pre-defined methods in standard libraries for a variety of programming languages. For example, I know that in Java, there is a function called isProbablePrime. (You might be wondering why it's called isProbablePrime instead of isPrime. I will explain that later). And of course, with Python and Ruby, you can write a couple lines of code and just be done with it as they have a lot of those mathematical/scientific functions. I can't really go into detail about them though, as I am not familiar with either programming languages.

As for me, I used C++ to answer all my questions, including question 3, and did not use any sort of already existing function that is similar to isProbablePrime like in Java. At most, for question 3, I used the rand function. to generate a random number.

Below is my short story of how I learned how to test the primality of a number.

**1. Use trial division.**
What is trial division? Well, you can read more about it here:

http://www.counton.org/explorer/primes/checking-if-a-number-is-prime/
It's basically an efficient way to test all numbers between 1 and n-1, where n is the number that we want to know if it's prime or not, and see if any of the numbers between 1 and n-1 divide into n evenly. If any one of them does, then n is not a prime number. Obviously, 1 to n-1 is O(n). If you don't know what O(n) is, go take an Intro to Data Structures and Algorithms course in your university.

So, trial division makes it from 1 to n-1, to 1 to sqrt(n). Why sqrt(n)? If you read the link, you would find out that:

Suppose one number *is* a factor of N and that it is **smaller** than the **square-root** of the number N. Then the second factor must be **larger** than the square-root.

Think of all the factors of 20. 1x20, 2x10, 4x5. 1 and 20 are on opposite sides of the spectrum, if the spectrum was a number line from 1 to 20. So are 2 and 10, and 4 and 5. So, all you really need to do is to look at the smaller numbers and not care about their larger counterparts. What I mean by this is, if you already tested if 20 mod 2 == 0, then you don't need to test if 20 mod 10 == 0. Thus, you only check the ranges of numbers from >1 and <sqrt(n).

Also, considering that n should be an odd number (because if it was an even number you would automatically know it's NOT a prime), then that means you also don't need to check if any even numbers are factors of n, so you only need to iterate sqrt(n)/2.

So, an implementation of trial division is:

You have an ODD NUMBER, n, and you want to check its primality.

//start at 3 because you don't need to check if even numbers, e.g. 2, are a factor of the odd number.
//go up until rounded up sqrt(n) (you should round it up)
//iterate by i+=2 because you don't need to check any of the even numbers
*for (int i = 3; i < ceil(sqrt(n)); i+=2)*
*{*
* if (n % i == 0)*
* {*
* return false; //it's not a prime*
* }*
*}*
/*after you check all of the numbers and you know none of them are factors of n then n must be prime.*/
*return true;*
If you try to answer question 3 of project euler using this implementation, I guarantee that the program runtime will be over an hour. I'm on a Macbook Pro that I bought in August 2014. And it took over an hour pretty much.

I think this frustration improved me for the better though. Project Euler, it is certainly frustrating, challenging, but still a lot of fun. When you get the right solution to a problem, you definitely want to come back to that question and see if you can improve your algorithm to be more efficient (a.k.a. not run for over an hour just to get the answer). It certainly makes me realize how I take for granted the power of modern computers computing powers.

I have since improved my trial division implementation, and am using the miller rabin algorithm. The Java method, isProbablePrime, actually uses this algorithm. It is not a deterministic algorithm though, and recently in 2006, there was a deterministic and polynomial time algorithm for primality called AKS primality algorithm. Perhaps I will read more into AKS later.