A little of coordination for Rosettacode

[ixid]

On Tuesday, 19 March 2013 at 16:47:43 UTC, Andrea Fontana wrote:
>
> On Tuesday, 19 March 2013 at 15:55:19 UTC, ixid wrote:
>> I was just looking at the Rosetta code for prime decomposition 
>> and it seems bugged to me, wanted to make sure as you seem to 
>> be the one coordinating these things:
>>
>> http://rosettacode.org/wiki/Prime_decomposition#D
>>
>> This will potentially return a 1 in the list of primes which 
>> is a bug as 1 isn't prime.
>
> You're right. I think the right code for decompose is this:
>
> T[] decompose(T)(T n) /*pure nothrow*/ {
> 	T[] res;
> 	for (T i = 2; n % i == 0;) {
> 		res ~= i;
> 		n /= i;
> 	}
> 	for (T i = 3; n != 1; i += 2) { // ----- Changed condition
> 		while (n % i == 0) {
> 			res ~= i;
> 			n /= i;
> 		}
> 	}
>         // ----- Removed concat here
> 	return res;
> }

T[] primeDecomposition2(T)(T n) /*pure nothrow*/ {
     T[] res;
     for (T i = 2; n % i == 0;) {
         res ~= i;
         n /= i;
     }
     for (T i = 3; n >= i * i; i += 2) {
         while (n % i == 0) {
             res ~= i;
             n /= i;
         }
     }

	if(n != 1)
		res ~= n;

     return res;
}

I think this is quite a lot faster, otherwise for numbers that 
are the products of a small and larger prime it will waste a lot 
of time reaching the larger prime's value.