Project Euler | Problem 5

Well, it's about time for the next problem! The solution isn't hard to find with pen and paper if you realize that what is asked is the least common multiple of the numbers 1 to 20. Since 20 is quite a small number, we can easily find this through the prime decompositions of all these numbers. Here's how it works for 1 to 10 (which, as given, gives 2520 as a result):

2=2
3=3
4=2*2
5=5
6=2*3
7=7
8=2*2*2
9=3*3
10=2*5

Note that any multiple n needs to be dividable by each of the above. In other words, the multiple n needs to contain the prime decomposition of each of the above numbers. Next, observe that 2 occurs at most 3 times, 3 at most 2 times, and 5 and 7 both at most once in each prime decomposition. Thus, the number we're looking for is 2*2*2*3*3*5*7=5*7*8*9=2520.
Analogously;

11=11
12=2*2*3
13=13
14=2*7
15=3*5
16=2*2*2*2
17=17
18=2*3*3
19=19
20=2*2*5

So the number is 2520*2*11*13*17*19=232792560. Surprisingly big number, isn't it?

The question remains, is this the most efficient method? Probably not, since determining the prime decomposition in the way I did in a previous post less than p/2*(n/2) modular operations and (p-1) divisions, where p is the amount of (non-distinct) primes in the decomposition and n is the value to be decomposed. The actual amount of modular operations is the multiplication of (n/p_i/2) for p_i=1,p_1,p_2..p_y, where p_1..p_y are the primes in the decomposition of n. I'm pretty sure this can be optimized to p/2*sqrt( n) by changing the condition in the while loop from x/2 to sqrt( x). Sounds efficient? I'd say so. You really don't want to use this to reverse an RSA public key, though: we know that in the above, p=2, but also that n=2^(2048) or n=2^(3072), for a reasonably secure key. that still means we need sqrt(2^(2048)) operations with this naive method, which is insanely huge. Nevertheless, it might be fun to try this method, or preferably, the more efficient method called Number Field Sieve, which is mentioned here.
To be continued?