package Ġutils . s ie ves Ċ Ċ class ĠFactor ization S ieve ( val Ġmx : ĠInt ) Ġ{ ĊĠĠĠ Ġval Ġsmallest Factors Ġ= ĠInt Array ( mx Ġ+ Ġ 1 ) ĊĊĠĠĠ Ġinit Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġcomposite Ġ= ĠBoolean Array ( mx Ġ+ Ġ 1 ) ĊĊĠĠĠĠĠĠĠ Ġvar Ġi Ġ= Ġ 2 ĊĠĠĠĠĠĠĠ Ġwhile Ġ( i Ġ<= Ġmx ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcomposite [ i ] Ġ= Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġsmallest Factors [ i ] Ġ= Ġ 2 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġi Ġ+= Ġ 2 ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġi Ġ= Ġ 3 ĊĠĠĠĠĠĠĠ Ġwhile Ġ( i Ġ<= Ġmx ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(! composite [ i ]) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġsmallest Factors [ i ] Ġ= Ġi ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( i Ġ<= Ġmx / i ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġj Ġ= Ġi * i ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( j Ġ<= Ġmx ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( sm allest Factors [ j ] Ġ== Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġsmallest Factors [ j ] Ġ= Ġi ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcomposite [ j ] Ġ= Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġj Ġ+= Ġi ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġi Ġ+= Ġ 2 ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġprime Factors ( nn : ĠInt , Ġfactors : ĠLong Array ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġassert ( nn Ġ<= Ġmx ) ĊĊĠĠĠĠĠĠĠ Ġvar Ġn Ġ= Ġnn ; ĊĊĠĠĠĠĠĠĠ Ġvar Ġfactors Count Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġvar Ġlast Factor Ġ= Ġ- 1 ĊĊĠĠĠĠĠĠĠ Ġwhile Ġ( n Ġ> Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġfactor Ġ= Ġsmallest Factors [ n ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( factor Ġ!= Ġlast Factor ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlast Factor Ġ= Ġfactor ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfactors [ factors Count ++] Ġ= Ġfactor . to Long () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġn Ġ/= Ġfactor ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġfactors Count ĊĠĠĠ Ġ} Ċ } Ċ