CODEWITHSUNDEEP
matlabprimesfactorization
355durch113
355durch113

Reputation: 201

What happens behind MATLAB's factor() function?

Mainly, why is it so fast (for big numbers)? The documentation only tells me how to use it. For example, it needs at most one second to find the largest prime factor of 1234567890987654, which, to me, seems insane.

>>max(factor(1234567890987654))

ans =

    69444443

Upvotes: 2

Views: 372

Answers (2)

Luis Mendo
Luis Mendo

Reputation: 112749

It's interesting to look at the source code of the factor and primes functions.

factor(N) essentiallty calls primes to find out all primes up to sqrt(N). Once they have been identified, it tests them one by one to see if they divide N.

primes(n) uses Eratosthenes' sieve: for each identified prime, remove all its multiples, exploiting sqrt again to reduce complexity.

Upvotes: 2

Aki Suihkonen
Aki Suihkonen

Reputation: 20037

The largest factor to be tried is sqrt(N), or 35136418 in this case. Also even the most elementary optimizations would skip all even numbers > 2, leaving only 17568209 candidates to be tested. Once the candidate 17777778 (and it's cofactor 69444443) is found, the algorithm would be wise enough to stop.

This can be somewhat easily improved further by a modified sieve to skip multiples of small primes 2,3,5[,7].

Basically even the sqrt(N) optimization is enough for the noted performance, unless you are working on an exceptionally old CPU (8086).

Upvotes: 5

Related Questions