algorithm - What makes this prime factorization so efficient? -

-

i've been doing project euler problems learn/practice lua, , initial quick-and-dirty way of finding largest prime factor of nwas pretty bad, looked code see how others doing (in attempts understand different factoring methodologies).

i ran across following (originally in python - lua):

function main()     local n = 102     local = 2     while i^2 < n         while n%i==0 n = n / end         = i+1     end     print(n) end

this factored huge numbers in very short time - immediately. thing noticed algorithm wouldn't have divined:

  • n = n / i

this seems in of decent algorithms. i've worked out on paper smaller numbers , can see makes numbers converge, don't understand why operation converges on largest prime factor.

can explain?

in case, i prime factor candidate. consider, n composed of following prime numbers:

n = p1^n1 * p2^n2 * p3^n3

when i reaches p1, statement n = n / = n / p1 removes 1 occurrence of p1:

n / p1 = p1^(n-1) * p2^n2 * p3^n3

the inner while iterates long there p1s in n. thus, after iteration complete (when i = + 1 executed), occurrences of p1 have been removed and:

n' =  p2^n2 * p3^n3

let's skip iterations until i reaches p3. remaining n then:

n'' = p3^n3

here, find first mistake in code. if n3 2, outer condition not hold , remain p3^2. should while i^2 <= n.

as before, inner while removes occurences of p3, leaving n'''=1. second mistake. should while n%i==0 , n>i (not sure lua syntax), keeps last occurence.

so above code works numbers n largest prime factor occurrs once successivley removing other factors. other numbers, mentioned corrections should make work, too.


Comments

Post a Comment

Popular posts from this blog

asp.net - 'System.Web.HttpContext' does not contain a definition for 'GetOwinContext' Mystery -

-
i realize question might seem trivial some, it's these types of things find myself fighting quite bit , want make sense of despite seeming losing battle in .net (for me anyway). so, if following: using system.web; ... applicationuser user = system.web.httpcontext.getowincontext().getusermanager<applicationusermanager>().findbyid(system.web.httpcontext.user.identity.getuserid()); that produces error in title , red getowincontext() , error cannot resolve symbol 'getowincontext()' however, if following (remove system.web in front of httpcontext ), works expected (or @ least no errors): using system.web; ... applicationuser user = httpcontext.getowincontext().getusermanager<applicationusermanager>().findbyid(system.web.httpcontext.user.identity.getuserid()); however, if (same line that's working using system.web commented out): //using system.web; ... applicationuser user = httpcontext.getowincontext().getusermana...
Read more

yii2 - Yii 2 Running a Cron in the basic template -

-
i have seen instructions on running cron in advanced template, cant figure out how on basic template. have following controller in basic controllers folder. <?php namespace app\controllers; use yii\console\controller; /** * cron controller */ class croncontroller extends controller { public function actionindex() { echo "cron service runnning"; } public function actionmail($to) { echo "sending mail " . $to; } } i have navigated root of application , tried these comands yii cron php yii cron im getting unknown comand "cron" i know old question failed find actual answer this. if @ code yii exec file you'll notice requires /common/config/aliases.php file console/config/main.php. can naturally change these or copy on these advanced template. hope solves problem wanting same thing.
Read more

android - Crash when clicking button with custom theme -

-
i creating custom theme button , using android:onclick event of button xml handle click of button. due reason crashing below exception java.lang.illegalstateexception: not find method myonclick(view) in activity class android.view.contextthemewrapper onclick handler on view class android.widget.button id 'button1' and working fine if remove theme attribute button, below theme button <style name="buttontheme" parent="@android:style/widget.button"> <item name="android:textcolor">#ff0000</item> <item name="android:shadowcolor">#ff000000</item> </style> and button defined in xml below, <button android:id="@+id/button1" android:layout_width="wrap_content" android:layout_height="wrap_content" android:layout_below="@+id/textview1" android:layout_margin="20dp" android...
Read more