Friday 18 March 2011

Prime Factors - the logic

How could we go about determining the prime factors of a composite number like 63 using the fx-50F? One way to do this is as follows. We begin with the smallest possible prime factor 2 and see if 63 is a multiple of 2. Multiples of 2 are 4, 6, 8, 10, . . . etc, which is just 2+2, 4+2, 6+2, 8+2, . . . etc. For each multiple, we can check to see if it is less than or equal to 63. If (a) it is less than 63, then we need to check the next multiple in the sequence. If (b) it is equal to 63, then 63 is divisible by 2. If (c) it is greater than 63, then 63 is not divisible by 2.

If (b) 2 is or (c) 2 is not a prime factor of 63 we need to continue looking for prime factors. If 2 is a prime factor of 63 we can divide 63 by 2 and obtain a new number with which to start the process all over again. If 2 is not a prime factor of 63 we can move to the next biggest prime factor 3 and start comparing 63 to multiples of 3. This process is repeated until we have found all the prime factors of 63.

The logic for a program to do this would be:-

Input A (the number whose prime factors are sought)
Store 2 in X (the first prime factor to try is 2)
Label 1
Store X in B (B holds the multiple being tested)
While B less than A
   Store B+X in B
While-End
If B=A then
   Display X (the prime factor found)
   Store A/X in A (the next number to be tested)
   Go to Label 1
If-End
Store X+1 in X (try the next prime factor)
If X squared is greater than A then
   Display A (the last prime factor to be found)
If-End
Go to Label 1

No comments:

Post a Comment