0
$\begingroup$

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!

$\endgroup$
7
  • 1
    $\begingroup$ Take for example $a_2$. This is OEIS A007814 and there are plenty of formulae listed there, but none are more efficient than simply finding how often $2$ divides $N$. There are plenty of algorithms for find the prime factorisation of $N$, some faster than others $\endgroup$
    – Henry
    Nov 25, 2022 at 21:22
  • $\begingroup$ In general, no. Factoring a number is hard. NP-Hard specifically (which has specific special meaning to mathematicians). It is possible to do, yes... but it will be so time-consuming and resource-consuming to pull off that it is not feasible to attempt to do for sufficiently large numbers. It is thanks to the difficulty of factoring numbers that our current crypto security systems are actually secure. Given a large enough difficult enough number it could take decades to successfully factor it... perhaps even eons... even with the best machines and techniques known. $\endgroup$
    – JMoravitz
    Nov 25, 2022 at 22:00
  • $\begingroup$ Not an answer (there is no such formula). For short enough numbers just put "factor 2520" into the search bar in your browser. For longer numbers do the same in wolfram alpha. $\endgroup$
    – Ethan Bolker
    Nov 25, 2022 at 22:03
  • 1
    $\begingroup$ Actually, it is not known whether factoring is (NP-)hard , but it is conjectured to be it. An efficient (polynomial) factoring algorithm cannot be ruled out. For factoring tasks , I always use the free and easy to program PARI/GP which can factor numbers upto $50$ digits routinely and with some luck even larger numbers , but our current knowledge does not allow efficient factoring , let alone a formula. $\endgroup$
    – Peter
    Nov 26, 2022 at 13:35
  • 1
    $\begingroup$ @Peter factoring is in BQP, so it would be surprising if it were NP-Hard. $\endgroup$
    – Charles
    Nov 27, 2022 at 4:41

1 Answer 1

Reset to default
1
$\begingroup$

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$.
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .