Chapter 7: Algorithm in Number Theory DIRECTION: Read, understand and perform the following; 1. How many positive intege

[answerhappygod]

Chapter 7 Algorithm In Number Theory Direction Read Understand And Perform The Following 1 How Many Positive Intege 1 (106.74 KiB) Viewed 9 times

Chapter 7: Algorithm in Number Theory DIRECTION: Read, understand and perform the following; 1. How many positive integers are ≤1010 and have an odd number of divisors? Find a simple formula for the number of such integers that are ≤ n. 2. Choose 1000 pairs of integers (n, m), at random between 1 and 1000. For each pair, compute the g.c.d. using a recursive program and a non-recursive program. a. Compare the execution times of the two programs. b. There is a theorem to the effect that the probability that two random integers have g.c.d. = 1 is 6/m2. What, precisely, do you think that this theorem means by 'the probability that ...' ? c. What percentage of the 1000 pairs that you chose had g.c.d. = 1? Compare your observed percentage with 100 (6/T2). .