package Ġmat ht ools . numbers . pri mes Ċ Ċ import Ġmat ht ools . numbers . factors . Bit Factor ing . is Product Of 2 Ċ import Ġmat ht ools . numbers . factors . Number Factors . divide Out Factor Ċ Ċ /** ĠContainer Ġfor ĠPrime Number Ġfunctions Ċ Ġ* Ġ@ author ĠD K 9 6 - OS Ġ: Ġ 2 0 1 8 Ġ- Ġ 2 0 2 1 Ġ*/ Ċ object ĠPrime Number Tools Ġ{ ĊĊ ĉ /** ĠThis Ġmaster Ġprime Ġcache Ġprovides Ġa Ġreference Ġfor Ġother Ġsets Ġ*/ Ċ ĉ private Ġval Ġshort Pri mes Ġ= ĠShort Prime Cache () ĊĊ ĉ /** ĠObtain Ġa Ġprime Ġnumber Ġby Ġit 's Ġindex , Ġstarting Ġat Ġindex Ġ 0 Ġ-> Ġ 2 Ġ*/ Ċ ĉ fun Ġget Prime ( idx : ĠInt ): ĠInt Ġ= Ġwhen Ġ( idx ) Ġ{ Ċĉ ĉ in Ġshort Pri mes . index Range Ġ-> Ġtry Ġ{ Ċĉĉ ĉ short Pri mes . get Prime ( idx ) Ċĉ ĉ } Ġcatch Ġ( e : ĠOut Of Memory Error ) Ġ{ Ċĉĉ ĉ short Pri mes . clear () Ċĉĉ ĉ - 1 Ċĉ ĉ } Ċĉ ĉ else Ġ-> Ġthrow ĠIllegalArgumentException ( Ċĉĉ ĉ " Prime ĠNumber Ġtoo Ġhigh Ġfor Ġgiven Ġcache .") Ċ ĉ } ĊĊ ĉ /** ĠClear Ġall Ġcached Ġprime Ġnumbers Ġ*/ Ċ ĉ fun Ġclear Cache () Ġ{ Ġshort Pri mes . clear ()} ĊĊĠĠĠ Ġ/** ĠWhether Ġthis ĠProduct / Prime Ġcontains Ġa Ġprime Ġnumber Ġgreater Ġthan Ġthe Ġlimit ĊĠĠĠĠ Ġ* Ġ@ param Ġproduct ĠThe Ġproduct Ġto Ġtest ĊĠĠĠĠ Ġ* Ġ@ param Ġlimit ĠThe Ġmaximum Ġprime Ġnumber Ġallowed Ġ*/ Ċ ĉ fun Ġcheck For Prime Factor Above Limit ( ĊĉĠĠĠ Ġproduct : ĠLong , ĊĉĠĠĠ Ġlimit : ĠLong , ĊĠĠĠ Ġ) Ġ: ĠBoolean Ġ= Ġif Ġ( limit Ġ< Ġproduct ) Ġ{ Ċĉ ĉ var Ġprime Idx Ġ= Ġ 0 Ċĉ ĉ var Ġcheck Prime Ġ= Ġget Prime ( prime Idx ) Ċĉ ĉ var Ġcomposite Ġ= Ġproduct Ċĉ ĉ while Ġ( limit Ġin Ġcheck Prime Ġuntil Ġcomposite ) Ġ{ Ċĉĉ ĉ composite Ġ= Ġdivide Out Factor ( check Prime , Ġcomposite ) Ċĉĉ ĉ check Prime Ġ= Ġget Prime ( ++ prime Idx ) Ċĉ ĉ } Ċĉ ĉ composite Ġ> Ġlimit ĊĠĠĠ Ġ} Ġelse Ġfalse ĊĊĠĠĠ Ġ/** ĠObtain Ġlowest ĠPrime ĠNumber ĠFactor Ġthat Ġis Ġgreater Ġthan Ġthe Ġlimit ĊĠĠĠĠ Ġ* Ġ@ param Ġproduct ĠThe Ġproduct Ġto Ġsearch Ġin ĊĠĠĠĠ Ġ* Ġ@ param Ġlimit ĠThe Ġmaximum Ġprime Ġfactor Ġthat Ġis Ġallowed ĊĠĠĠĠ Ġ* Ġ@ return ĠThe Ġsmallest Ġprime Ġfactor Ġabove Ġthe Ġlimit , Ġor Ġnull Ġ Ġ*/ ĊĠĠĠ Ġfun Ġget First Prime Above Limit ( ĊĉĠĠĠ Ġproduct : ĠLong , ĊĉĠĠĠ Ġlimit : ĠLong , ĊĠĠĠ Ġ) Ġ: ĠLong ? Ġ{ ĊĉĠĠĠ Ġ// Ġcheck Ġarguments ĊĉĠĠĠ Ġwhen Ġ{ Ċĉĉ ĉ limit Ġ< Ġ 2 Ġ-> Ġreturn Ġnull ĊĉĉĠĠĠ Ġproduct Ġin Ġ- 1 .. 1 Ġ-> Ġreturn Ġnull ĊĉĉĠĠĠ Ġproduct Ġ< Ġ 0 Ġ-> Ġreturn Ġget First Prime Above Limit (- product , Ġlimit ) Ċĉ ĉ } ĊĠĠĠĠĠĠĠ Ġvar Ġprime Idx Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġvar Ġtest Prime Ġ= Ġget Prime ( prime Idx ) ĊĠĠĠĠĠĠĠ Ġvar Ġcomposite Ġ= Ġproduct ĊĠĠĠĠĠĠĠ Ġwhile Ġ( limit Ġin Ġtest Prime Ġuntil Ġcomposite ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcomposite Ġ= Ġdivide Out Factor ( test Prime , Ġcomposite ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġtest Prime Ġ= Ġget Prime ( ++ prime Idx ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġwhile Ġ( test Prime Ġin Ġ( limit Ġ+ Ġ 1 ) Ġ.. Ġcomposite ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( composite Ġ% Ġtest Prime Ġ== Ġ 0 L ) Ġreturn Ġtest Prime . to Long () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġtest Prime Ġ+= Ġ 2 ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġnull ĊĠĠĠ Ġ} ĊĊ ĉ /** ĠTry Ġto Ġdivide Ġthe Ġproduct Ġby Ġall Ġpri mes Ġin Ġthe Ġindex Ġrange . Ċĉ Ġ* Ġ@ param Ġprime Index Range ĠThe Ġrange Ġof Ġprime Ġnumber Ġindices Ġto Ġtry Ċĉ Ġ* Ġ@ param Ġproduct ĠAss umed Ġto Ġbe Ġa Ġproduct Ġof Ġprime Ġnumbers Ċĉ Ġ* Ġ@ return ĠRem aining Ġproduct Ġafter Ġall Ġdiv isions Ġattempted , Ġor Ġnull Ġif Ġ 1 Ġ*/ Ċ ĉ fun Ġreduce By Prime Range ( Ċĉ ĉ prime Index Range : ĠInt Range , Ċĉ ĉ product : ĠLong Ċ ĉ ) Ġ: ĠLong ? Ġ{ Ċĉ ĉ // Ġcheck Ġarguments Ċĉ ĉ when Ġ{ Ċĉĉ ĉ // Ġrange Ġis Ġreversed Ċĉĉ ĉ prime Index Range . last Ġ< Ġprime Index Range . first Ġ-> Ċĉĉĉ ĉ return Ġreduce By Prime Range ( Ċĉĉĉĉ ĉ prime Index Range . last Ġ.. Ġprime Index Range . first , Ċĉĉĉĉ ĉ product Ċĉĉĉ ĉ ) Ċĉĉ ĉ // Ġrange Ġstarts Ġbelow Ġ 0 Ċĉĉ ĉ prime Index Range . first Ġ< Ġ 0 Ġ-> Ġ{ Ċĉĉĉ ĉ if Ġ( prime Index Range . last Ġ< Ġ 0 ) Ġreturn Ġnull Ċĉĉĉ ĉ // ĠIf Ġrange Ġends Ġin Ġvalid Ġregion , Ġreduce Ġin Ġvalid Ġregion Ċĉĉĉ ĉ return Ġreduce By Prime Range ( Ċĉĉĉĉĉ 0 Ġ.. Ġprime Index Range . last , Ċĉĉĉĉ ĉ product Ċĉĉĉ ĉ ) Ċĉĉ ĉ } Ċĉĉ ĉ // ĠProduct Ġis Ġin div isible Ċĉĉ ĉ product Ġin Ġ- 1 Ġ.. Ġ 1 Ġ-> Ġreturn Ġnull Ċĉĉ ĉ // ĠProduct Ġis Ġnegative Ċĉĉ ĉ product Ġ< Ġ 0 Ġ-> Ġ{ Ċĉĉĉ ĉ val Ġresult Ġ= Ġreduce By Prime Range ( prime Index Range , Ġ- product ) Ċĉĉĉ ĉ return Ġif Ġ( result Ġ!= Ġnull ) Ġ- result Ġelse Ġnull Ċĉĉ ĉ } Ċĉ ĉ } Ċĉ ĉ // ĠDo Ġreduction Ċĉ ĉ var Ġcomposite : ĠLong Ġ= Ġproduct Ċĉ ĉ for Ġ( prime Idx Ġin Ġprime Index Range ) Ġ{ Ċĉĉ ĉ val Ġtest Prime Ġ= Ġget Prime ( prime Idx ) Ċĉĉ ĉ composite Ġ= Ġdivide Out Factor ( test Prime , Ġcomposite ) Ċĉĉ ĉ // ĠIf Ġthe Ġcomposite Ġis Ġless Ġthan Ġthe Ġtest Ġfactor , Ġdone Ċĉĉ ĉ if Ġ( composite Ġ< Ġtest Prime ) Ġbreak Ċĉ ĉ } Ċĉ ĉ return Ġif Ġ( composite Ġ<= Ġ 1 L ) Ċĉĉ ĉ null Ġelse Ġcomposite Ċ ĉ } ĊĉĊĠĠĠ Ġ/** ĠRemove Ġany Ġprime Ġfactors Ġless Ġthan Ġor Ġequal Ġto Ġthe Ġmaximum Ċĉ Ġ* Ġ@ param Ġproduct ĠAss umed Ġproduct Ġof Ġa Ġset Ġof Ġprime Ġnumbers Ċĉ Ġ* Ġ@ param Ġmax Prime ĠThe Ġmaximum Ġprime Ġfactor Ġto Ġbe Ġremoved ĊĠĠĠĠ Ġ* Ġ@ return ĠA Ġnumber Ġcontaining Ġonly Ġpri mes Ġgreater Ġthan Ġmax Prime , Ġor Ġnull Ġ*/ Ċ ĉ fun Ġdivide Out Small Pri mes ( ĊĉĠĠĠ Ġproduct : ĠLong , ĊĉĠĠĠ Ġmax Prime : ĠLong ĊĠĠĠ Ġ) Ġ: ĠLong ? Ġ{ ĊĉĠĠĠ Ġ// Ġcheck Ġarguments ĊĉĠĠĠ Ġwhen Ġ{ Ċĉĉ ĉ max Prime Ġ< Ġ 2 Ġ-> Ġreturn Ġnull Ċĉĉ ĉ product Ġin Ġ- 1 Ġ.. Ġ 1 Ġ-> Ġreturn Ġnull ĊĉĉĠĠĠ Ġproduct Ġ< Ġ 0 Ġ-> Ġreturn Ġdivide Out Small Pri mes (- product , Ġmax Prime ) ĊĉĉĠĠĠ Ġproduct Ġ<= Ġmax Prime Ġ-> Ġreturn Ġnull Ċĉ ĉ } ĊĉĠĠĠ Ġ// Ġcheck Ġefficiently Ġfor Ġfactors Ġof Ġ 2 Ċĉ ĉ var Ġcomposite : ĠLong Ġ= Ġif Ġ( is Product Of 2 ( product )) Ċĉĉ ĉ divide Out Factor ( 2 , Ġproduct ) Ġelse Ġproduct ĊĉĠĠĠ Ġ// Ġcheck Ġnext Ġprime Ġfactor Ċĉ ĉ var Ġprime Idx Ġ= Ġ 1 Ċĉ ĉ var Ġtest Prime Ġ= Ġ 3 ĉ // Ġget Prime ( idx ) Ġcurrently Ġreturns ĠInt ĊĉĠĠĠ Ġwhile Ġ( Ċĉĉ ĉ test Prime Ġ<= Ġcomposite Ċĉĉ ĉ && Ġtest Prime Ġ<= Ġmax Prime Ċĉĉ ĉ && Ġprime Idx Ġ< Ġshort Pri mes . max Index Ċĉ ĉ ) Ġ{ Ċĉĉ ĉ composite Ġ= Ġdivide Out Factor ( test Prime , Ġcomposite ) ĊĉĉĠĠĠ Ġ// ĠValidate Ġthe Ġnext Ġprime Ġbefore Ġover writing ĊĉĉĠĠĠ Ġval Ġnext Prime Ġ= Ġget Prime ( ++ prime Idx ) ĊĉĉĠĠĠ Ġif Ġ( next Prime Ġ>= Ġcomposite ) Ġbreak ĊĉĉĠĠĠ Ġtest Prime Ġ= Ġnext Prime Ċĉ ĉ } Ċĉ ĉ // ĠIf Ġcomposite Ġbecame Ġ 1 , Ġit Ġwas Ġcompletely Ġdivided ĊĉĠĠĠ Ġreturn Ġif Ġ( composite Ġ<= Ġ 1 L Ġ|| Ġcomposite Ġ<= Ġtest Prime ) Ċĉĉ ĉ null Ġelse Ġcomposite Ċ ĉ } Ċĉ Ċ }