以下算法检查数字是否为素数:
Given a number n,loop over all numbers smaller than n and check whether they divide n.
If one of them divides n, answer no. Otherwise, answer yes.
现在,我必须在以下两种情况下分析算法执行的除法运算次数与其输入长度的函数关系:
1)数字以一元编码(即4为1111)。如何证明除数是多项式的?
2)数字以二进制编码(即4为100)。我如何证明划分的数量是指数的?