A simple algorithm to prime factorization

56 Views Asked by At

Here a proff:

We know that:

$n!=\prod_{P_{i} \leq n}p_{i}^{ \alpha_{i}(n)}$; where:

$\alpha_{i}(n)=\sum_{t=1}^{r}[\frac{n}{p_{i}^{t}}]$ and $p^{r} \leq n < p^{r+1}$.

Then:

$n=\frac {n!}{(n-1)!}=\prod_{P_{i} \leq n}p_{i}^{ \beta_{i}(n)}$ (Eq. 1)

Where:

$\beta_{i}(n)= \alpha_{i}(n)-\alpha_{i}(n-1)$

In other words, this method can be used also to found a relation between the prime factirization of n+1 from n, lets see:

$n+1=\prod_{P_{i} \leq n+1}p_{i}^{ \beta_{i}(n+1)}$; where:

$\beta_{i}(n+1)= \alpha_{i}(n+1)-\alpha_{i}(n)$.

Finally, this is the relation:

$\beta_{i}(n+1)= \alpha_{i}(n+1)-\alpha_{i}(n-1)-\beta_{i}(n)$.

Example of prime factorization whit this method:

$n=60$

$\beta_{i}(60)=\sum_{t}^{r} \{[\frac {60}{p_{i}^{t}}]-[\frac {59}{p_{i}^{t}}]\}$

Then:

$\beta_{1}(60)=\sum_{t}^{r} \{[\frac {60}{2^{t}}]-[\frac {59}{2^{t}}]\}=2$

$\beta_{2}(60)=\sum_{t}^{r} \{[\frac {60}{3^{t}}]-[\frac {59}{3^{t}}]\}=1$

$\beta_{1}(60)=\sum_{t}^{r} \{[\frac {60}{5^{t}}]-[\frac {59}{5^{t}}]\}=1$

Finally:

$60=2^{2}3^{1}5^{1}$