pm_mathFactoring::getFactoring Interface Reference

Generate and return the factoring of the input positive integer. More...

Detailed Description

Generate and return the factoring of the input positive integer.

The factoring of an integer number \(n\) is defined such that,

\begin{equation} \large n = \prod_{i=1}^{m} f_i ~, \end{equation}

where \(m\) is the number of factors of \(n\) and \(f_i\) are the factors.

Parameters

[in]

posint

: The input scalar of type integer of kind any supported by the processor (e.g., IK, IK8, IK16, IK32, or IK64) containing the positive integer (larger than 1) whose factoring is to be computed on return.

Returns

Factoring : The output allocatable vector of the same type and kind as the input posint, containing the prime factors of the input integer posint.

Possible calling interfaces ⛓

use pm_mathFactoring, only: getFactoring
 
Factoring = getFactoring(posint)

Warning

The condition 1 < posint must hold for the corresponding input arguments.
This condition is verified only if the library is built with the preprocessor macro CHECK_ENABLED=1.

The input argument posint has the value attribute.

The pure procedure(s) documented herein become impure when the ParaMonte library is compiled with preprocessor macro CHECK_ENABLED=1.
By default, these procedures are pure in release build and impure in debug and testing builds.

See also

getFactorial

Example usage ⛓

program example
 
    use pm_kind, only: IKS, IKD
    use pm_kind, only: SK, IK, LK
    use pm_io, only: display_type
    use pm_mathFactoring, only: getFactoring
    use pm_distLogUnif, only: getLogUnifRand
 
    implicit none
 
    integer(IK) :: i, n
    integer(IK), allocatable :: Factoring(:)
 
    type(display_type) :: disp
    disp = display_type(file = "main.out.F90")
 
    call disp%skip()
    call disp%show("!%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%")
    call disp%show("! Compute the factoring of a scalar or array of integers.")
    call disp%show("!%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%")
    call disp%skip()
 
    do i = 1, 10
        call disp%skip()
        call disp%show("n = getLogUnifRand(2, huge(1))")
                        n = getLogUnifRand(2, huge(1))
        call disp%show("n")
        call disp%show( n )
        call disp%show("Factoring = getFactoring(n)")
                        Factoring = getFactoring(n)
        call disp%show("Factoring")
        call disp%show( Factoring )
        call disp%show("n - product(Factoring) ! By definition, it must be zero.")
        call disp%show( n - product(Factoring) )
        call disp%skip()
    end do
 
end program example

Example Unix compile command via Intel ifort compiler ⛓

#!/usr/bin/env sh
rm main.exe
ifort -fpp -standard-semantics -O3 -Wl,-rpath,../../../lib -I../../../inc main.F90 ../../../lib/libparamonte* -o main.exe
./main.exe

Example Windows Batch compile command via Intel ifort compiler ⛓

del main.exe
set PATH=..\..\..\lib;%PATH%
ifort /fpp /standard-semantics /O3 /I:..\..\..\include main.F90 ..\..\..\lib\libparamonte*.lib /exe:main.exe
main.exe

Example Unix / MinGW compile command via GNU gfortran compiler ⛓

#!/usr/bin/env sh
rm main.exe
gfortran -cpp -ffree-line-length-none -O3 -Wl,-rpath,../../../lib -I../../../inc main.F90 ../../../lib/libparamonte* -o main.exe
./main.exe

Example output ⛓

 
!%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
! Compute the factoring of a scalar or array of integers.
!%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
 
n = getLogUnifRand(2, huge(1))
n
+19
Factoring = getFactoring(n)
Factoring
+19
n - product(Factoring) ! By definition, it must be zero.
+0
 
 
n = getLogUnifRand(2, huge(1))
n
+41871
Factoring = getFactoring(n)
Factoring
+3, +17, +821
n - product(Factoring) ! By definition, it must be zero.
+0
 
 
n = getLogUnifRand(2, huge(1))
n
+213077
Factoring = getFactoring(n)
Factoring
+41, +5197
n - product(Factoring) ! By definition, it must be zero.
+0
 
 
n = getLogUnifRand(2, huge(1))
n
+126474096
Factoring = getFactoring(n)
Factoring
+2, +2, +2, +2, +3, +7, +7, +53773
n - product(Factoring) ! By definition, it must be zero.
+0
 
 
n = getLogUnifRand(2, huge(1))
n
+223261
Factoring = getFactoring(n)
Factoring
+17, +23, +571
n - product(Factoring) ! By definition, it must be zero.
+0
 
 
n = getLogUnifRand(2, huge(1))
n
+372
Factoring = getFactoring(n)
Factoring
+2, +2, +3, +31
n - product(Factoring) ! By definition, it must be zero.
+0
 
 
n = getLogUnifRand(2, huge(1))
n
+262857
Factoring = getFactoring(n)
Factoring
+3, +7, +12517
n - product(Factoring) ! By definition, it must be zero.
+0
 
 
n = getLogUnifRand(2, huge(1))
n
+2243
Factoring = getFactoring(n)
Factoring
+2243
n - product(Factoring) ! By definition, it must be zero.
+0
 
 
n = getLogUnifRand(2, huge(1))
n
+10467961
Factoring = getFactoring(n)
Factoring
+7, +239, +6257
n - product(Factoring) ! By definition, it must be zero.
+0
 
 
n = getLogUnifRand(2, huge(1))
n
+2555
Factoring = getFactoring(n)
Factoring
+5, +7, +73
n - product(Factoring) ! By definition, it must be zero.
+0
 
 

Test:

test_pm_mathFactoring

Todo:

High Priority: The performance of the procedures under this generic interface can be improved by using more efficient algorithms and lookup tables for various ranges of input values. The following schemes could be implemented,

• \(posint \leq 2^{16}\): Lookup table.
  
• \(posint \leq 2^{70}\): Richard Brent modification of Pollard rho algorithm.
• \(posint \leq 10^{50}\): Lenstra elliptic curve factorization.
• \(posint \leq 10^{100}\): Quadratic Sieve.
• \(posint \leq 10^{100}\): General Number Field Sieve.

Final Remarks ⛓

---

If you believe this algorithm or its documentation can be improved, we appreciate your contribution and help to edit this page's documentation and source file on GitHub.
For details on the naming abbreviations, see this page.
For details on the naming conventions, see this page.
This software is distributed under the MIT license with additional terms outlined below.

1. If you use any parts or concepts from this library to any extent, please acknowledge the usage by citing the relevant publications of the ParaMonte library.
   
2. If you regenerate any parts/ideas from this library in a programming environment other than those currently supported by this ParaMonte library (i.e., other than C, C++, Fortran, MATLAB, Python, R), please also ask the end users to cite this original ParaMonte library.
   

This software is available to the public under a highly permissive license.
Help us justify its continued development and maintenance by acknowledging its benefit to society, distributing it, and contributing to it.

Copyright

Computational Data Science Lab

Author:

Amir Shahmoradi, April 23, 2017, 1:36 AM, Institute for Computational Engineering and Sciences (ICES), University of Texas at Austin

Definition at line 127 of file pm_mathFactoring.F90.

---

The documentation for this interface was generated from the following file:

• src/fortran/main/pm_mathFactoring.F90