A program to find all the factors of a number(II)

Last time when I was writing to complete my childhood wish to write a (BASIC) program to find all the factors of a number using heuristic learn from Primary School. However, when I was doing so I has forgotten the true difficult of the program: To shorten the test time, the program would limit to test only the prime factors of the number without knowing which factor are prime. In order to do so, the program will have to test the factor recursively, but I fail to find a way to such write a recursive loop.

Now, I just thought of another method to shorten the search of all factors of a number.

Given a number N,

Define the lower limit of √N as K,

Make an array of K item,

Starting from K,

Check if the K-th element of the Array is zero, otherwise reduce K by 1.

Test if N is divisible by K,

If not reduce K by 1, otherwise:

1.Mark the K as divisible by making the value of K-th item of the array to be 1

2. start the Test for Prime Factor with K as the input.

Test For Prime Factor:

(Define the lower limit of √N as K,

Make an array of K item,

Starting from K,

Test if N is divisible by K,

If not reduce K by 1, otherwise Mark the K as divisible by making the value of K-th item of the array to be 1.)

So, in according to this procedure, if it discover a factor of the N, for instance, 40 is a factor for 1600. Then it would proceed to look up for the factor of 40, which it would arrive at the results: 1,2,4,5,8,10,20. Since 40 is a factor of 1600, and we can logically conclude that the factor of the factor 40 is also a factor of 1600, i.e. 1,2,4,5,8,10,20 are also factors for 1600, which will be skipped for checking in the bigger loop.

Notice the similarity between checking for factor of the number and the checking for factor of the factor. A usual way to save time when writing program is to re-use what is already developed, therefore my first intention is to re-use the same algorithm for checking for factor of the number to check for factor of the factor. Now, wouldn’t we able to apply the same logic so we should also checking for factor of the factor of the number to further shorten the process? Should we should also checking for factor of the factor of the factor of the number to further shorten the process?

So in my mind there is no built it mechanism to prevent me from infinite recursion, but when programming in whatever programming language, I need to explicitly state when I need to re-use a sub-procedure. That is the difference between computer and human mind.

廣告

~ 由 newnewhkcc1976 於 四月 22, 2009.

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com 標誌

您的留言將使用 WordPress.com 帳號。 登出 /  變更 )

Google photo

您的留言將使用 Google 帳號。 登出 /  變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 /  變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 /  變更 )

連結到 %s

 
%d 位部落客按了讚: