为什么朴素素数测试算法不是多项式 [英] Why naive primality test algorithm is not polynomial

问题描述

我想了解为什么以下朴素素性测试算法不是多项式.

I would like to understand why the following naive primality test algorithm is not polynomial.

IsPrime (n: an integer)
Begin
   For i=2 to n-1 do
     If (n % i == 0) then
        return (no)
     EndIf
   EndFor

   return (yes)
End

据说该算法在输入 n 的大小上是指数的.为什么会这样呢?为什么下面的排序测试算法是多项式而不是指数式的?

This algorithm is said to be exponential in the size of the input n. Why is it true? And why the following sorting test algorithm is said polynomial and not exponential?

IsSorted (T[n]: an array of n integer)
Begin
  For i = 1 to n-1 do
     If (T[i] > T[i+1]) then
        return (no)
     EndIf
  EndFor

  return (yes)
End

推荐答案

输入大小通常以位为单位.为了表示数字n，输入大小将为log2(n).原始素数检验在n中是线性的，但在log2(n)中是指数的.

The input size is typically measured in bits. To represent the number n the input size would be log2(n). The primitive primality test is linear in n, but exponential in log2(n).

这篇关于为什么朴素素数测试算法不是多项式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！