This is what I've got as of now, feel free to suggest any improvements or optimizations:
:Input "INTEGER: ",X
:If X=0 or fPart(X:Then //Prevent infinite loops when 0 or a fraction is entered.
:abs(X→X //Because Y will be used in the loop later, and I need the absolute value of the original value in a special case. Also enables referring back to the number the program used by entering X. :)
:startTmr→T //Timer for time optimization purposes.
:If Ans>1.7√(X:Then //If a factor isn't found till now, the entered number is a factor, at least for all numbers I've tested.
I don't think it's perfect - probably far from. The use of Ans could probably be improved here and there - it's my first time working extensively with it. I've also read somewhere that the use of Goto within a loop isn't very good, for some reason. There might be a more elegant way of doing that - ideas?
Anyway, the only real trick in this is the conditional statement within the loops, which determines if the entered number is a prime, essentially. This cuts the required number of iterations off by huge chunks. Furthermore, I can think of a couple of ways to improve it further, although I'm not entirely sure of how to execute them:
- Key idea: There are only one even prime as we all know; 2. Therefore, if two is a factor, one would not have to check for even numbers at all - this will however give the disadvantage of only revealing one 2, I suppose, which would say that the factors of 4 is 1 and 2, instead of 1, 2, 2.
- The same idea could be applied for any other prime: once the algorithm has found a number that has to be a prime, i.e a number that gives me no remainder, the loop should no longer care for any multiple of said prime. This would cut down on the required number of iterations a lot - if I only knew how to implement it in a nice way - feel free to brainstorm.
As a summary, the time needed with this method depends solely on how large the largest prime factor of the number entered is. For example, nine trillions (9,000,000,000,000) took it about one second, since the largest prime factor is 5 - while 987,987,987,987 took it 241 seconds, since the largest prime factor is 9,901.
By the way, note how I have no variable killed, which gives the user the freedom of having a previously discovered number, X, inputed into the program simply as X.