Fast prime factorisation/factorization calculator. Minimum on scripts, maximum on speed and efficiency. Fastest trial division implementation on Scratch. Use Turbowarp to speedup factorisation by more than tenfold: https://turbowarp.org/414793532?turbo
Do not enter any number less than 2, or greater than 9007199254740992(floating point limitation, there will be inaccuracies in division for numbers above 2^53). Floating point numbers will be treated as prime. Update: Optimized the algorithm further by fixing a logic error I oversaw that prevented the optimization. The algorithm now only calculates sqrt(x) divisors, instead of x/2. At a rate of 990,000 divisors per second(330,000 calculations/sec.), the program can now calculate the prime factors of any 12-digit number in less than 1 second. In an earlier version the same computation would take ~10^5 seconds, or 1.75 days. Shortly after this optimization, another one was made that increased the rate of checking useful divisors, by ignoring those that are divisible by 2. Surprisingly, instead of a 2x optimization as predicted, the algorithm was ~2.8x faster. However, ignoring divisors that were also divisible by 3 did not speed it up. In fact, the extra computations made to ignore fewer divisors incurred a slight slowdown in its speed. (Update: A very slight increase in speed is now observed, due to bypassing the division operations previously done. The program now uses modulus logic to skip divisors divisible by 2 or 3. Attempts to apply similar logic to ignore divisors also divisible by 5 significantly slowed down the program.) Using Turbowarp will speed up computation by 12 to 15 times. This figure was measured by calculating ~11,950,000 divisors, by attempting to factorise the prime number 2733944327177339. Update: Changed the divisor-checking subroutine to an older version, because that version was found to be faster. The other version of the subroutine, which can be found inside the project, uses an additional counter to alternately skip between 1 and 3 divisors (to ignore divisors divisible by 2 and 3) Update: Changed the entire factorization routine and output pipeline. The divisor-checking subroutine has been updated to a 2,3,5,7-wheel skipping 77.14% of divisors, overall a speedup of ~1.5x compared to the last iteration. Output is now more user-friendly and copyable. Additionally, the speedup factor in TurboWarp is now ~15 times, instead of 5-10 times earlier. The calculation time is now measured using 'days since 2000' module instead of the built-in timer. This is the current fastest iteration and from here there is not much more room for improvement.
