Journey creating the Lightning Fast Prime Factorizer App
Hi!
My name is Kedar Prasad and this is the story of how my very first Android app came to be.
As summer events were canceled due to COVID, I was bored and decided to learn how to create an Android app on my own. For the app, I decided to pursue a simple idea - a prime factorization calculator. There were many prime factorization calculators available in the app store, so I knew I had to do something different to make my factorizer unique.
My name is Kedar Prasad and this is the story of how my very first Android app came to be.
As summer events were canceled due to COVID, I was bored and decided to learn how to create an Android app on my own. For the app, I decided to pursue a simple idea - a prime factorization calculator. There were many prime factorization calculators available in the app store, so I knew I had to do something different to make my factorizer unique.
First, the algorithm to factorize needed development. I used Python (Spyder) and initially, iterated over every number less than the input number to identify factors. Over time, I improved this algorithm as it was not very efficient. After a lot of thinking and a few trials, the algorithm I landed on takes √n/4 (n = input number...square root of n / 4). This fast factorization approach reduces the number of iterations performed to identify factors and is therefore optimized.
In my quest for improvement, I started to look for a data store to record calculated prime factors of a number. I hoped this would improve the response time as a number already factored could be returned from the data store (rather than being factored again). My mom suggested I try Cloud services from AWS as a data store. This started my journey exploring AWS.
I decided to use AWS ElastiCache Redis to store the prime factors of numbers after they have been factorized. I also decided to move my algorithm to an AWS Lambda function. In my Python code, I included the Redis library, Boto3 library, packaged the code, upload to AWS S3 for access from Lambda ( this is because the package size was > 10 MB). Later I realized Boto3 was not required and when this library was removed, the package size was small enough that I could use the AWS Management Console Lambda Editor. Next, was the question - how to call this Lambda function from my app. I explored AWS API Gateway and created an API endpoint for my Lambda function. Now, I had an API endpoint that would call the Lambda with a parameter (input number), the Lambda function would factorize, store factors in Redis and finally, return result. I coded the Lambda to first check if the input number was already in Redis. If yes, I queried Redis and returned the factors. Else, I calculated the factors and stored them for reuse in Redis. Finally it felt like the flow was optimized.
The flow is depicted below.
Finally, I started the packaging and publishing process for the app on Google Play Store. This was challenging as I had to learn about the various steps involved, including Build and Packaging process, creating keys for submission, uploading package and waiting for review to complete. I lost the private key early in the process and had to work with Google Support to create a new app and keyset.
Link to app:
FAQs
What challenges did you face while making the app?First, it was very challenging to learn enough about Android Studio and AWS. I had to research many concepts, and encountered many dead ends. For example, I had to learn about how to call an API on AWS using AWS gateway. It was not easy to link the Lambda function to an API gateway, and to call the API from an external source.
What was your inspiration to make the app?
I have always loved math, and love exploring concepts like prime factorization. I downloaded many apps from the play store relating to prime factorization, but noticed that the apps would not remember the prime factorization of numbers after I factorized them. Because of this, I knew I wanted to make a smart prime factorizer; one that would store the factors of prime numbers someone so that the prime factors of a number could instantly be retrieved after only being factored once.
What will you do next?
The next update will contain UI changes to make the layout clearer. Future updates will probably increase the length of numbers that can be factorized by using BigInteger, and may include a way to find out Mersenne primes. I may also explore building the app for iOS (so my dad can install the app on his phone 😀 ).
However, my knowledge of the future is the same as yours, so nothing is certain yet.
