1

I am studying cryptography algorithms. Here we have following algorithm to check primarality test.

def is_prime(x):
  for i in range(2,x):
    if x % i == 0: return False
  return True

On above following is quiz asked Would above approach work
A. Yes
B. No, its running time is exponential in the value of x
C. No, its running time is exponential in the size of x
D. No, there is a silly bug in python code

Answer is given as C.

My question and require help what is difference between value of 'x' and size of 'x'.

Thanks for your time and help

venkysmarty
  • 11,099
  • 25
  • 101
  • 184
  • 3
    Because the size refers to the numbers of bits used to represent the input: https://stackoverflow.com/questions/53042838/why-naive-primality-test-algorithm-is-not-polynomial see the second answer in the link – Dani Mesejo Oct 15 '21 at 09:14

0 Answers0