A Prime Factorization Algorithm that Uses a Text File

A post that is at least within two week of the last one? This will hopefully be the new norm. I was about to get this out two days prior, but Github had some issues when I was about to upload it on the first day. I got this uploaded to Github the yesterday, but it was late, so I didn't make a post. Nevertheless, it's time to talk about this code.

I have created a python program that shall do prime factorization when given an integer. You can find it here on Github. 

The Background

So this is another program requested by my computer science teacher. He demanded a program that would be given a number and return the prime factors of it along with how many times each was used (and specifically in the order you see in the program's output).

Initially, I though this was an easy program. There's a rule I've known since middle school on how to prime factorize:

1. Start by dividing the number by 2 for as many times possible
2. When you can no longer divide by 2, divide by 3 for as many times as possible
3. When you can no longer divide by 3, divide by the next prime number for as many times as possible
4. Repeat until the number is a prime itself or is 1

I wrote up some pseudocode to demonstrate these steps, however I came upon a problem. The prior rule was useful in middle school as I was dealing with numbers such as 70 or 432, nothing big nor anything that requires a prime larger than 13, I only needed the first few prime numbers. When it comes large numbers such as 1234, which conveniently uses the primes 2 and 617, I need to know of prime numbers as large as 1234. For that number, over a hundred would have to be known.

The solution intrigued me. One solution was to simply have another function run with the program to find all the primes before the inputted number. I decided against doing that as I had no idea how to do such a task off the top of my head. I did a search on Google and noticed a page on GeeksforGeeks with a successful program that mostly followed the rule I previously mention and resembled most of what I had planned to code, except instead of dividing by every prime, their program divided by 2, then 3, then every odd number after that. It did work, but I wanted to use only the primes, so I did not use their method.

I then came across the list of primes on Wikipedia. I then came to this conclusion: I may not be able to calculate the primes without having to do some complicated calculations, but I can still create a function that only uses primes. I just need to get a them from a list.

The Code

Thus I have coded up program. The process is explained step-by-step on the repository's ReadME file, but I'll give a very brief explanation here:

1. The function will check if the input is an integer and if it is a special case such as 1 or 0
2. The function will compare the number to the list of primes to see how many are smaller than it
3. The function will then divide number as many times as possible by each prime smaller than it
4. The function will output the primes it was divisible by along with how much each it used
5. If the input was a prime, the function will state the number is prime

The first few lines of the text of the list of primes file. The file is need for the program to work

The list of primes is taken from a text file with an ordered list of the first 1000 primes. The list could've had way more than the first, but I felt it would be unnecessary. As the list is limited, so is the certainty. The last prime in the list is 7919. The next prime after that is 7927, so the first number that would have a wrong result is 15,854 (which is 2 * 7927). If the input is larger than the last prime on the list, the function will also output a message saying the results may not be correct.

This is my first time in python with file handling. I think I did an alright job at doing this. There are of course some problems with this code. If the text file has something other than a prime at a line, the output will likely be wrong. For now, this seemed to be a fun experience in trying out file handling.



I will attempt to get something other than coding out soon. I have some graphing calculator art and equations I want to show, but that is still being worked on. Hopefully I will get something out in the next ten days. Until then, see ya.