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.
