Formula for finding the prime structure of a number

Question

Consider a positive integer $N$, it can be written in form of prime numbers as;

$$N=2^{a_{2}}3^{a_{3}}5^{a_{5}}....p_{i}^{a_{i}}$$

Thus that number $2520$, for instance,can be written as:

$$2520=2^{3}3^{2}5^{1}7^{1}$$

In this case we see that 2520 is composite of prime numbers $2$, $3$, $5$ and $7$, we also know that $a_2=3$, $a_3=2$ and $a_5=a_7=1$.

Is there is a formula, that given the number $N$ can tell the prime structure of $N$ as I showed above?

I was searching on this for a long time already, but I could reach any useful steps, can anyone help me please, even tell me any useful information about what I'm trying to do. Thank you guys!

Answer 1

This is not an answer.

This is a long-winded comment.

Personally, I got tired of having to deal with math problems, where I had to stop and determine the prime factorization of a fairly large integer. So, the following approach details how I resolved the problem on my (vanilla) PC (i.e. no special capabilities).

I don't think that MathSE is the proper forum to discuss computer code. However, I think that it is reasonable to discuss pseudo-code, at a somewhat high level. I developed private software that computes the prime factorization of any positive integer less that $(10)^{(10)}$. It runs in less than $5$ seconds.

---

You need to be reasonably adept at programming in some PC language, like C, Python, or Java.

You also need to understand that if the positive integer $n$ has no prime factor that is $~\leq \sqrt{n},~$ then $n$ must be prime. For example, to conclude that $23$ is a prime number, it is sufficient to verify that $23$ is not a multiple of either $2$ or $3$.

First, I wrote a program that writes to a (text) file, every prime number, in ascending order, less than $(10)^5.$ With the size of the integers so limited, the resulting file is not too big, and the program runs fairly quickly.

In effect, the program looped through the integers $2$ through $10^5.$ Each time that the program encountered a prime number, it added the number to the list.

Then, in the loop, I simply checked each integer $n$ against the (dynamic) list, stopping when the entry in the dynamic list exceeded $\sqrt{n}$.

---

Then, I wrote a 2nd program that first counts the number of entries in prime_numbers.txt (et al), uses that count to format an Array (rather than an ArrayList), and then loops through prime_numbers.txt a second time.

This approach allows all prime numbers less than $(10)^5$ to be fed into a (relatively high-speed access) Array, rather than (for example) an ArrayList.

This second program requires a single command line parameter $n$, which is required to be a positive integer $~<~ (10)^{(10)}.$

The program loops through the array until it encounters a prime number $~> \sqrt{n}.~$ If no prime is encountered that is a factor of $n$, then $n$ must be prime.

Assume that the prime $p_1$ is a factor of $n$. Then the program does the following:

• Computes $~\displaystyle n_1 = \frac{n}{p_1}.$
• Computes $~\sqrt{n_1}.$
• Repeats the initial search process, except that, instead of re-starting the search for prime factors with $p = 2$, the search begins at $p = p_1$.