素数算法的复杂度是多少？
What is the complexity of a prime algorithm?
我想知道这个算法的复杂度是多少。 N>=3 一个整数作为输入。谢谢！
initialisation : i=2
LOOP:
if N%i==0
return 1;
if i == [sqrt(N)]
return 0;
i= i + 1;
initialisation : i=2
LOOP:
if N%i==0
return 1; # 1 <-----
if i == [sqrt(N)]
return 0; # 2 <-----
i= i + 1;
情况一：N为偶数。然后我们在 O(1) 中完成 - 参见行 (# 1)。或者 N 是奇数且非素数。然后当我们达到 N 的某个除数时我们就完成了（这可能发生在平方根之前，或者同时发生）。
情况2：N是素数。然后我们将在完成之前点击 [ n^0.5 ] 个数字（参见第 # 2 行）。
然而，正如@Lutzl 在他们的评论中指出的那样，精确的计算可能会考虑 runtime of the division involved。这有点不适定，因为我们不知道使用了什么乘法和除法算法。但总运行时间为 O(max{a * sqrt(N), sqrt(N)})，其中 O(a) 是 N % i == 0 检查的运行时间。我在这里假设实际的平方根计算实际上是常数时间并且只完成一次，所以 O(n^0.5) 是因为这是在算法结束之前你得到的迭代次数对于质数输入。
我想知道这个算法的复杂度是多少。 N>=3 一个整数作为输入。谢谢！
initialisation : i=2
LOOP:
if N%i==0
return 1;
if i == [sqrt(N)]
return 0;
i= i + 1;
initialisation : i=2
LOOP:
if N%i==0
return 1; # 1 <-----
if i == [sqrt(N)]
return 0; # 2 <-----
i= i + 1;
情况一：N为偶数。然后我们在 O(1) 中完成 - 参见行 (# 1)。或者 N 是奇数且非素数。然后当我们达到 N 的某个除数时我们就完成了（这可能发生在平方根之前，或者同时发生）。
情况2：N是素数。然后我们将在完成之前点击 [ n^0.5 ] 个数字（参见第 # 2 行）。
然而，正如@Lutzl 在他们的评论中指出的那样，精确的计算可能会考虑 runtime of the division involved。这有点不适定，因为我们不知道使用了什么乘法和除法算法。但总运行时间为 O(max{a * sqrt(N), sqrt(N)})，其中 O(a) 是 N % i == 0 检查的运行时间。我在这里假设实际的平方根计算实际上是常数时间并且只完成一次，所以 O(n^0.5) 是因为这是在算法结束之前你得到的迭代次数对于质数输入。