View Single Post
Old 2013-09-24, 11:45   #3
Tribal Bullet
jasonp's Avatar
Oct 2004

DCE16 Posts

Per your blog post, you can certainly prove a number to be prime, without factoring it, but the algorithms for doing that are pretty complex. The search term is 'primality proving'.

It is much easier to think about factorization in algebraic terms, and much easier to find patterns using algebaic relationships than to try to spot colors in a table. For example, your experiments appear to be a graphical rediscovery of Fermat's factorization algorithm, which works especially well when factors are near the square root of the input. Fermat's algorithm is very easy to express algebraically (it's hundreds of years old).

The objective with factorization is always to factor something bigger, and doing it by eye will not scale. At this point you if you want to really accelerate things you should go to wikipedia and read up on integer factorization; the articles on the various methods are quite good there and you'll be amazed how quickly they work.

You also need to get into the habit of doing background reading before coding, especially if you are a professional programmer, because in 2013 it's very difficult to think of something new in the computer field and very easy to leverage the work of others.

Last fiddled with by jasonp on 2013-09-24 at 11:46
jasonp is offline   Reply With Quote