Most popular web site - 368 ARITHMETIC Fig. 11. Probability distribution functions for
368 ARITHMETIC Fig. 11. Probability distribution functions for the two largest prime factors of a random integer 2 x. Dickman s (see exercise 18), we can show that the second-largest prime factor of a random integer z will be 2 Z? with approximate probability G(P), where Clearly G(P) = 1 for p 2 a. (See Fig. 11.) Numerical evaluation of (6) and (7) yields the following percentage points : F(a), G(P) = .Ol .05 .lO .20 .35 .50 .65 .80 .90 .95 .99 a = .2697 .3348 .3785 .4430 .5220 .6065 .704i .8187 .9048 .9512 .9900 B = .0056 .0273 .0531 .1003 .1611 .2117 .2582 .3104 .3590 .3967 .4517 Thus, the second-largest prime factor will be 5 x.2117 about half the time, etc. The total number of prime factors, t, has also been intensively analyzed. Obviously 1 5 t2 lg N, but these lower and upper bounds are seldom achieved. It is possible to prove that if N is chosen at random between 1 and 2, the probability that t5 In In x + cd= approaches 1 c -u=/2 (8) -Ifi –ooe du as z + co, for any fixed c. In other words, the distribution of tis essentially normal, with mean and variance lnlnz; about 99.73 percent of all the large integers 5 z have It-lnln ~1 5 3dm. Furthermore the average value of t-In In x for 1 5 N < 2 is known to approach 7 + c (ln(1 -l/p) + l/(p -1)) = LO3465 38818 9 7438. p prime