Thursday, March 5, 2020

Problem-solving in programming #1 - Factoring a large number.

Classroom, Math, Chalkboard, School, Education

A simple problem seen in many programming challenges talks about factorization of a large number.

Why heavens do people insist on prime numbers and factorization? Will it be ever used or it is just to torture students?

I will not dive too deep into these questions (especially the one about the irresistible pleasure some teachers obtain from torturing students). Some applications for large numbers, prime numbers and factorization (there are MANY applications in real life) are cryptography, hashing, calculating random numbers. Even your microwave at home is only made possible because of prime numbers research.

If you are into cryptography, or if you are planning into entering this very interesting and profitable market, this will become a huge part of your life.

Anyway, how do we use programming to assist in factoring numbers?

Let's begin with the simple step-by-step process of factorization for the number 426:

Oh, factorization in prime numbers. Assume I was talking about this. Also, prime numbers are the cool numbers that can only be divided by 1 or by themselves.

So, in order to factor 426, we should start dividing it by the smallest prime number after 1, because dividing it by one would result in 426, that is not a prime number. So, we start with 2, and 3, and so on:

426 / 2 = 213
213 / 3 = 71
71 / 71 = 1

Wow, that was fast. If you didn't know 71 is a prime number, this article is already useful for you! But we need to start talking Java here, right? So, the process basically consists in having the computer compute for you!

It comes to having repeated iterations of the same process. We could do it like this:

(please don't mind the random black mark in the middle of the code - I am doing this from a Mac and I am struggling with the screenshot tool.)

And we have the computer do the process of iterating through numbers and checking to see if the remainder of their division by the number/resulting number is zero. If it is, it adds to the factors list.

It works, right?

Well, partially. Let's try factoring the number 1385012925728371650682372927611246185812.

No. You try.

Go ahead and try finding some solutions, and in three days I'll expand this discussion a little more!

Spoiler: Math stuff will increase in the next post, so if you don't like Number Theory, you should start liking it now :D
Author Image

About Ricardo Prins
Ricardo Prins is a Software Engineer who thinks that technology is not the answer to all our problems.

No comments:

Post a Comment