A program for finding the prime factors of a number on the fx-50F was described previously. Once it has been entered into the calculator you can press [Prog] [N] to run the program (N is the number of the program area where the code is stored). A? is displayed on the screen, prompting you to enter a number to be factorised.
Try the number 63 which we looked at before. So enter 63 and press [EXE]. The calculator displays Then X and 3. So, 3 is the first prime factor. Press [EXE] again and the calculator displays Then X and 3 again. So 3 is the second prime factor. Finally, press [EXE] once more and the display shows Then A and 7. The display of Then A rather than Then X indicates that this is the last prime factor to be found. So 63=3x3x7 which is correct. Press [AC] to exit the program.
If you try the number 61, the calculator displays Then A and 61 indicating that 61 is only divisible by itself and 1, so 61 is a prime number and has no other factors.
It is inadvisable to use this program for numbers much bigger than 500 as the processing may take a while to complete.
Wednesday 23 March 2011
Prime Factors - the program
The logic for the prime factors program was presented previously. Here is the logic converted into a program for the fx-50F:-
?→A:2→X:Lbl 1:X→B:While B<A:B+X→B:WhileEnd:If B=A:Then X▲
A÷X→A:Goto 1:IfEnd:X+1→X:If X²>A:Then A▲IfEnd:Goto 1
This is pretty much how the program looks when keyed into the calculator in edit mode except it all appears on one continuous line. Special Program Commands (? → : Lbl While WhileEnd If Then IfEnd = > < ▲ Goto) are input using the [SHIFT] [P-CMD] keys. The cursor key (marked Replay) is used to switch between various screens of commands. Memory variables A, B and X are input using [ALPHA] [A], [B] or [X] keys. The ":" Separator Code command is used frequently and can be alternatively input using the [EXE] key.
This program is 66 steps in length.
?→A:2→X:Lbl 1:X→B:While B<A:B+X→B:WhileEnd:If B=A:Then X▲
A÷X→A:Goto 1:IfEnd:X+1→X:If X²>A:Then A▲IfEnd:Goto 1
This is pretty much how the program looks when keyed into the calculator in edit mode except it all appears on one continuous line. Special Program Commands (? → : Lbl While WhileEnd If Then IfEnd = > < ▲ Goto) are input using the [SHIFT] [P-CMD] keys. The cursor key (marked Replay) is used to switch between various screens of commands. Memory variables A, B and X are input using [ALPHA] [A], [B] or [X] keys. The ":" Separator Code command is used frequently and can be alternatively input using the [EXE] key.
This program is 66 steps in length.
Monday 21 March 2011
Prime Factors - Comment on the logic
There are a few things that need to be mentioned about the logic of my prime factors program.
The first is that for simplicity I have just incremented the prime factor variable X by one each time, so when X is 3, the next prime factor to be tried is 4. Clearly, 4 is not a prime number and so it is ineffecient to be using this number (the same is also true of 6, 8, 9, 10...etc.). However, it does not cause a problem with the logic, it just means that the program takes longer to run. I will address this issue again later.
Secondly, I have stopped the program when the square of the prime factor variable X is larger than the number A that we are testing. Why is this? Well, suppose our number is 63 and we have found the prime factors, 3, 3 and 7. We might try and see if the next prime number 11 is a factor of 63, but 63 divided by 11 is about 5.7. So we would already have found the factor 5 (if it was a factor) when looking for factors between 3 and 7. So in our test to see where to stop searching for prime factors we note that 7 squared is 49 (which is less than 63) and 11 squared is 121 (which is greater than 63), so it is clear that we can stop our prime factor search at 7.
Finally, we note that it would be much more efficient to use division than multiples of prime factors. For example, 63 divided by 2 gives 31 remainder 1. 63 divided by 3 gives 21 remainder zero. So, if we had knew the remainder, we could easily determine whether 2, 3, ... etc were factors or not. Unfortunately, the fx-50F is missing this functionality and so we have had to restort to using multiples of prime factors.
The first is that for simplicity I have just incremented the prime factor variable X by one each time, so when X is 3, the next prime factor to be tried is 4. Clearly, 4 is not a prime number and so it is ineffecient to be using this number (the same is also true of 6, 8, 9, 10...etc.). However, it does not cause a problem with the logic, it just means that the program takes longer to run. I will address this issue again later.
Secondly, I have stopped the program when the square of the prime factor variable X is larger than the number A that we are testing. Why is this? Well, suppose our number is 63 and we have found the prime factors, 3, 3 and 7. We might try and see if the next prime number 11 is a factor of 63, but 63 divided by 11 is about 5.7. So we would already have found the factor 5 (if it was a factor) when looking for factors between 3 and 7. So in our test to see where to stop searching for prime factors we note that 7 squared is 49 (which is less than 63) and 11 squared is 121 (which is greater than 63), so it is clear that we can stop our prime factor search at 7.
Finally, we note that it would be much more efficient to use division than multiples of prime factors. For example, 63 divided by 2 gives 31 remainder 1. 63 divided by 3 gives 21 remainder zero. So, if we had knew the remainder, we could easily determine whether 2, 3, ... etc were factors or not. Unfortunately, the fx-50F is missing this functionality and so we have had to restort to using multiples of prime factors.
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
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
Thursday 17 March 2011
Prime Factors
Let's now consider something more interesting. In mathematics we often want to know whether a number like 63 is divisible by anything other 1 and 63. We know that in this case 63 is divisible by 3, 7, 9, and 21. But what about a number like 61? Well, no whole number will divide into 61 other than 1 and 61, so 61 is what is known as a prime number.
So consider the number 63 again. Using our known factors of 3, 7, 9 and 21 we find that 63=3x21 or 63=7x9 (there is no other combination of two factors). But 9=3x3 and 21=3x7, so in fact 63=3x3x7. This last representation is irreducible, as 3 and 7 are prime numbers themselves and so 3x3x7 represents the prime factors of 63. In fact, composite numbers like 63 are all constructed from a unique set of prime factors.
So consider the number 63 again. Using our known factors of 3, 7, 9 and 21 we find that 63=3x21 or 63=7x9 (there is no other combination of two factors). But 9=3x3 and 21=3x7, so in fact 63=3x3x7. This last representation is irreducible, as 3 and 7 are prime numbers themselves and so 3x3x7 represents the prime factors of 63. In fact, composite numbers like 63 are all constructed from a unique set of prime factors.
Subscribe to:
Posts (Atom)