cp's OEIS Frontend

A189172 Largest prime number tried when factoring n using trial division.

%I A189172 #15 Jun 23 2022 20:30:28
%S A189172 1,1,1,2,2,2,2,2,3,2,3,2,3,2,3,2,3,3,3,2,3,3,3,2,5,3,3,2,5,3,5,2,3,3,
%T A189172 5,3,5,3,3,2,5,3,5,3,3,3,5,2,7,5,3,3,7,3,5,2,3,5,7,3,7,5,3,2,5,3,7,3,
%U A189172 3,5,7,3,7,5,5,3,7,3,7,2,3,5,7,3,5,5,5,3,7,3,7,3,5,5,5,2,7,7,3,5
%N A189172 Largest prime number tried when factoring n using trial division.
%C A189172 When factoring a number via trial division, one generally continues trying primes until it is certain that the remaining portion of n is prime.  Sometimes, it is already clear that the remaining portion is prime before that portion is found; in this case, the last prime tried is the second to last prime factor.
%H A189172 T. D. Noe, <a href="/A189172/b189172.txt">Table of n, a(n) for n = 1..10000</a>
%F A189172 a(n) = max(A087039(n), A007917(A000196(A006530(n)))).
%e A189172 A(22) is 3, because after 3 is tried, it is clear that 11 is prime and no more factorization can be done.
%e A189172 A(18) is 3, because despite the largest prime factor (3) being obviously prime, it is not obviously the last factor until the first 3 is factored out.
%t A189172 a[n_] := Module[{m = n, k = 1, p = 1, q}, While[q = Prime[k]; q^2 <= m, p = q; m = m/p^IntegerExponent[m, p]; k++]; p]; Array[a,100] (* _T. D. Noe_, May 04 2011 *)
%o A189172 (JavaScript) prime(k), not shown, gives A000040[k].
%o A189172 function a(n) {
%o A189172   var k = 1;
%o A189172   while (Math.pow(prime(k),2) <= n) {
%o A189172     var p = prime(k);
%o A189172     if (n % p == 0) {
%o A189172       n /= p;
%o A189172     } else {
%o A189172       k += 1;
%o A189172     }
%o A189172   }
%o A189172   return p;
%o A189172 }
%Y A189172 Like A059396 but also works on composites; uses A006530, A087039, A000040.
%K A189172 nonn
%O A189172 1,4
%A A189172 _Dan Uznanski_, May 02 2011