Finding Prime Factors
=====================
:author: Aaron Ball
:email: nullspoon@iohq.net



I have been working in my spare time on the https://projecteueler.net[Euler
project] problems. Now, for most languages, these problems aren't too big of a
deal, because most modern languages do much of the work for you (at least on
the early problems).  I'm working on learning c++ though, and it doesn't do a
lot of the work for you, which is great in my opnion. One thing it's really
helping me with is number theory (or whatever it would actually be called). I
never went to school for computer science, so I lack much of the math that many
developers have. That said, nealry every problem that Euler has, is a really
great test, not only of programming ability, but of number knowledge.

My most recent problem I've been working on is refactoring my code to solve
https://projecteuler.net/problem=3[problem 3]. Now, this problem isn't that
difficult. Where the difficulty lies is in the calculation speed. My original
program solved this one in about ten minutes I think (again, if you're sporting
something like ruby, php, perl, etc, you have probably solved this faster
because they built good calculation methods into the language). In going bad to
refactor though, I've been focusing more on wasy to more efficiently calculate
these things via brute force (I'm sure there's an equation for this out there,
but I'm using a for loop). Here is the list of things that I found to speed up
the calculation process.


[[calculating-factors]]
== Calculating Factors

A factor is a number that an original number is divisible by (eg: the factors
of 10 are 1, 2, 5, and 10).


[[dont-go-above-half]]
=== Don't go above half

When you are finding factors, you are not finding them one at a time.  Each
time you find a factor, you find its counterpart. For example, the factors of
20 are 1, 2, 4, 5 , 10, 20. When you are looping through starting at 1 and you
find that the number 20 is divisible by 2, you also know that its counterpart
is 10 (20/2). When you find the next factor, 4, you have also found the factor
5 (20/4 = 5), and so on. This means that your calculation time should be cut in
half becuase you only have to calculate up to half of the original number (20
in our example).  One more example to help visualize this, a table. Everyone
loves tables!

Factors of 20

[cols=",",options="header",]
|===================
|Factor |Counterpart
|1      |20
|2      |10
|4      |5
|5      |4
|10     |2
|20     |1
|===================

See the overlap at 4 and 5?


[[only-calculate-evens-or-odds]]
==== Only Calculate Evens or Odds


[[calculating-primes]]
=== Calculating Primes

Category:Drafts


// vim: set syntax=asciidoc:
