The basic algorithm A traditional method for the factorization is the trial divison with the primes , or with the numbers , which is easier to programize, but we get the result slower. Analysing this algorithm (e.g. its simplified Maple-form below) we conclude, that it works usable in our PC's if the order of is maximum , or if the order of the divisor is maximum . For larger numbers the algorithm usually slows down hopelessly, because of the lot of divisions. In a faster computer we can make this situation better, but the improvement will not be spectacular. In the following example we search for the prime divisors of an odd number with trial divison. We can get the same result using the
> basic:=proc(n,limit) > local i,s,a; > s:=NULL; a:=n; > for i from 3 by 2 to limit do > if a mod i = 0 then a:=a/i; s:=s,i; > while a mod i = 0 do a:=a/i; s:=s,i od > fi > od; print(s,a) > end: > b:=1234567890123456789: > basic(b, 4001);
Let us assume, that the number is very large, it contains e.g. decimal digits. In this case we apply the basic algorithm to separate the "small" factors up to the order of approximately . After this we examine the remaining part further with additional methods, discussed in the following subsections.