For two integers with n and m digits, respectively, in the decimal system, let us assume...

Transcribed Image Text:

For two integers with n and m digits, respectively, in the decimal system, let us assume that multiplication, as well as division with remainder, requires O(nm) time, although theoretically faster algorithms are possible. Given an integer p with n digits, we want to test whether p is a prime number. A rather simple algorithm proceeds as follows: Compute p/i for all integers i with 2 ≤ i ≤ [√p]. If some of the p/i is integer then p is not prime, otherwise p is prime. (We remark that this is by far not the smartest algorithm for the problem.) 1.1. Why is this algorithm correct? That is, why is it enough to test factors i up to [p] only? 1.2. How much time does this algorithm need? Express the time in two ways: once as a function of n, and once as a function of p. Give your derivations of the time bounds, not only your final answers. 1.3. How much time do we save compared to the most naive algorithm that tests all factors i = 2, ..., p? Give a clear quantitative statement. 1.4. Is the time of the proposed algorithm polynomial in the input length? Why, or why not? For two integers with n and m digits, respectively, in the decimal system, let us assume that multiplication, as well as division with remainder, requires O(nm) time, although theoretically faster algorithms are possible. Given an integer p with n digits, we want to test whether p is a prime number. A rather simple algorithm proceeds as follows: Compute p/i for all integers i with 2 ≤ i ≤ [√p]. If some of the p/i is integer then p is not prime, otherwise p is prime. (We remark that this is by far not the smartest algorithm for the problem.) 1.1. Why is this algorithm correct? That is, why is it enough to test factors i up to [p] only? 1.2. How much time does this algorithm need? Express the time in two ways: once as a function of n, and once as a function of p. Give your derivations of the time bounds, not only your final answers. 1.3. How much time do we save compared to the most naive algorithm that tests all factors i = 2, ..., p? Give a clear quantitative statement. 1.4. Is the time of the proposed algorithm polynomial in the input length? Why, or why not?

Answer rating: 100% (QA)

11 The algorithm is correct because it exhaustively tests potential factors i up to p ensuring t... View the full answer