Finding Prime Factors

I have been working in my spare time on the 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 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

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

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

Factor Counterpart

1

20

2

10

4

5

5

4

10

2

20

1

See the overlap at 4 and 5?

Calculating Primes

Category:Drafts