检查一个数是否为素数的算法的时间复杂度是多少？
检查一个数是否为素数的算法的时间复杂度可以通过以下方式进行分析。
一种常见的素数检查算法是试除法。该算法从2开始，依次将待检查的数与2至其平方根之间的每个数进行取余操作，若余数为0，则说明存在能整除该数的因子，即不是素数；若余数不为0，则继续检查下一个数。若未找到任何能整除该数的因子，则说明是素数。
假设待检查的数为n，算法的时间复杂度为O(sqrt(n))。这是因为算法需要从2至sqrt(n)之间的每个数进行取余操作。具体来说，算法的时间复杂度为O(sqrt(n)/2)，进一步简化为O(sqrt(n))。
这种算法的时间复杂度是相对较低的，特别适用于小范围内的素数检查。若需要对大数进行素数检查，可能需要使用更高效的算法，如Miller-Rabin素性测试。
关于腾讯云相关产品，由于不允许提及具体品牌商，因此无法给出相关推荐和链接地址。
相关·内容
1回答
我在三个参数集上运行并计时了Weil配对的实现。一个数量级为512位，一个为256位，最后一个为161位。
我采用Miller的算法来计算Weil配对。我用于两点乘法的算法是双加加算法.如果我正确理解，这两种算法的时间复杂度都为$O(log (n))$。
我得到的时间是512位的10秒，256位的2，5秒，161位的1秒。当我看到我得到的时间时，似乎更像是$O(n^2)$或$O(n \cdot log (n))$的复杂性。
有人能告诉我基于我的结果的时间复杂度是多少吗？
浏览 0提问于2018-08-15得票数 1
回答已采纳
1回答
堆算法时间复杂度
、、、、
有人能告诉我维基百科，中这个堆算法的时间复杂度到底是多少吗？
我搜索了几个网站，答案都很模糊，有些人说时间复杂度是O(N!)有些人说这是O(NlogN)。哪一个是正确的答案？为什么？
谢谢。
浏览 3提问于2017-03-18得票数 5
回答已采纳
检查一个数字是否为素数的算法的时间复杂度是多少？
这就是算法：
bool isPrime (int number) {
if (number < 2) return false;
if (number == 2) return true;
if (number % 2 == 0) return false;
for (int i=3; (i*i) <= number; i+=2) {
if (number % i == 0 ) return false;
}
return true;
}
浏览 0提问于2013-05-08得票数 8
回答已采纳
1回答
我对big-o还很陌生，我想弄清楚这一小段代码的大o运行时间是多少。我知道通常情况下，如果有，但是整个数组的事情会改变什么吗？我很困惑，所以任何一点的输入都是很好的。提前感谢！
public apple(int n)
{
int n = 0;
int apple = 0;
a = apple + n;
}
浏览 0提问于2017-09-07得票数 0
5回答
以下片段的时间复杂度是多少？你能解释一下吗？
for(int i=0;i<n;i++){
for(int j=0;j<=i;j++){
//print something
}
}
浏览 1提问于2017-05-22得票数 0
回答已采纳
2回答
在我一直在使用的两个算法中，我使用了两个函数：
素数：=number的pi(N) <= n，以及
R(n):=r，其中prod( p_i，i=1，r)<=n而n< prod(p_i，i=1，r+1)，其中p_i是第I素数.
基本上pi(n)是著名的素计数函数，R(n)只是计算连续素数的乘积，直到到达界n并返回所用素数的数量，例如：
R(12)=2，因为2*3<=12但是2*3*5>12，例如
R(100)=3，因为2*3*5<=100但是2*3*5*7>100。
我们一直在和我的教授讨论计算这些函数的运行时间。我知道随着时间的推移，π(
浏览 2提问于2016-06-29得票数 0
回答已采纳
我有两个埃拉托斯提尼筛子的实现。这是第一个：
public class SieveOfEratosthenes extends PrimeGenerator {
private boolean[] sieve;
private List<Integer> primes;
public SieveOfEratosthenes(int depth) {
super(depth);
sieve = new boolean[depth + 1];
primes = new ArrayList<>();
浏览 2提问于2015-03-09得票数 2
回答已采纳
2回答
这个算法的时间复杂度是多少：
public int[] createTargetArray(int[] nums, int[] index) {
int[] target = new int[nums.length];
int i = 0, k = 0;
while (i < index.length) {
for (k = target.length - 1; k > index[i]; k--)
target[k] = target[k - 1];
target[index[i]] = nums[i
浏览 3提问于2021-02-27得票数 1
回答已采纳
2回答
__gcd(m，n)函数的时间复杂度是多少？另外，它是否使用欧几里德方法来计算gcd？
例如，代码
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
cout << "gcd(10, 25) : " << __gcd(6, 20) << endl;
}
浏览 0提问于2019-06-11得票数 3
给定一个矩阵和一些规则，设置二进制矩阵规则的所有位数所需的最少天数是多少：
只有值'1‘的细胞，才能在1天内设置距离为1单位的相邻细胞。单元格可以水平或垂直设置。对角线不应被视为邻居。
given a matrix(A) of rows(N), and columns(M)
A=[
0 1 0 0 0
0 0 0 0 1
0 0 0 1 0
0 0 1 0 0
]
after 1 day
A=[
1 1 1 0 1
0 1 0 1 1
0 0 1 1 1
0 1 1 1 0
]
after
浏览 4提问于2019-10-29得票数 1
回答已采纳
我知道时间复杂度是O(n)。但是这段代码的空间复杂度是多少？的意思是在最坏的情况下，需要的最大空间是多少？我猜是O(1)，因为数组已经有固定的空间，因此空间不会增加。
代码：
public int[] countBits(int num) {
int[] res = new int[num+1];
for (int i = 0; i<num+1; i++){
res[i] = Integer.bitCount(i);
}
return res;
}
浏览 2提问于2017-07-02得票数 1
回答已采纳
给定一个列表列表，即[1,2,3,4,5,6,7,8,9]：，使用嵌套For循环来查看每一个1-9的数字是否只使用一次和仅使用一次的时间复杂度是多少？此外，如果输入现在是一个单数组合列表，即1,2,3,4,5,6,7,8,9，那么时间复杂度是多少？
浏览 3提问于2021-01-01得票数 0
问:分析以下算法的运行时间？T(n)=Cop * C(n)
flag=false;
count=0;
for(i=0;i<=n;i++)
{
if (A[i]==1)
count++;
flag=true;
}
else
flag=false;
return(count);
总时间是多少？假设n= 50。
浏览 3提问于2017-01-31得票数 0
回答已采纳
1回答
多输入神经网络的运行时间
、、、、
假设我有一个固定架构的神经网络。如果我输入一个数据点，运行时间是1秒。那么如果输入是N个数据点，那么运行时间是多少？
是O(1)还是O(N)？换句话说，运行时间是以线性方式还是常量依赖于输入的数量？我听说过术语""，它可以减少运行时间，并用于前馈神经网络。但是向量化在大小上是恒定的吗？
浏览 11提问于2020-03-12得票数 0
2回答
以O(log(N))形式表示的Viola-Jones算法复杂度是多少？尽管这是一个非常简单的算法，但没有关于它的具体信息。
浏览 8提问于2017-01-27得票数 2
如果您需要生成从1到N的素数，“愚蠢”的方法是迭代从2到N的所有数字，并检查到目前为止找到的任何小于该数字的平方根的质数是否可除。
在我看来，Eratosthenes的筛子做了同样的事情，除了反过来--当它找到一个素数N时，它会标记出所有N的倍数。
但无论你是在找到N的时候划掉X，还是检查X是否可被N整除，基本的复杂性，大O保持不变。对于一个数字-质数对，您仍然需要执行一次恒定时间操作。事实上，愚蠢的算法一旦找到一个素数就会中断，但埃拉托斯尼的筛子会多次标记每个数字-每一个素数可除一次。这是除素数以外的每个数的最少两倍的运算。
我是不是误解了什么？
浏览 1提问于2011-04-13得票数 17
回答已采纳
1回答
这是MergeSort吗？
、、、、
我试着编码MergeSort。但是我的代码看起来与著名的MergeSort实现非常不同。所以我想知道，我的实现是否正确。我的算法采用两个int数组(每个数组都是排序的)，并将它们放入一个排序的大数组中。我的算法的渐近复杂度是多少？非常感谢！！
public static int[] myMergeSort(int[] array, int[] array2) {
int[] giveback = new int[array.length + array2.length];
int i = 0;
int j = 0;
for (int x = 0; x &l
浏览 4提问于2016-11-29得票数 0
回答已采纳
3回答
查找数组中的最大值和代码效率
、、、、
我想知道我对代码的概念和理解是否正确！在这里，首先，我将最后一个数字设置为最大值，然后使用另一个for循环将每个值与所有其他值进行比较，以找到最大值，对吗？另外，这是O(n^2)的运行时，因为这里使用了两个for循环？我知道有一个更好的线性解决方案(O(N))，但我想手动查看并检查执行它需要多长时间，并尝试比较两者之间的效率。我也不知道这段代码的空间复杂度是多少。任何进一步的解释都将不胜感激。 /*The following code will return the largest value in an array of non-negative integers */
int Comp
浏览 50提问于2020-07-10得票数 2
1回答
我希望这是适合这个问题的地方。
多项式时间算法！多项式时间算法(PTAs)实际上与计算机的处理能力、内存大小(RAM)和存储有什么关系？
我们认为PTA是有效的。我们知道，即使对于PTA，时间复杂度也随着输入大小n的增加而增加。例如，已经存在一个PTA来确定一个数字是否是素数。但是，如果我想检查一个这么大的数字，会发生什么呢？质检PTA是否仍被认为是有效的？有没有一台计算机能计算出这样大的一个数字是否是质数？
不管是或否(也许不是，idk)，多项式时间算法的概念在现实世界中是如何实际应用的？它们是一些计算界，还是所谓的多项式时间算法？
我尝试过谷歌搜索，但我发现所有的数学大O相关的解释。我没有
浏览 12提问于2022-07-04得票数 2
1回答
中位快速排序中值的最坏情况时间复杂度是多少(枢轴是由需要O(n)时间查找的中间值的中位数决定的)？
浏览 1提问于2014-11-22得票数 0
回答已采纳
2回答
我需要打印所有小于给定数字n的素数。我可以使用Eratothenes筛子，但该算法的运行时间不是O(n)。这个问题有O(n)时间的解吗？
浏览 2提问于2012-03-15得票数 0
回答已采纳
2回答
大O得到最大数
、、
最近问到了这个问题：
编写一个包含数组(每个数组包含从最大到最小排序的数字)和一个数字(n)的函数。返回n个最大数字。
例如：
findLargest([ 10，5，3，1，9，8，7，6，11，2，1，0 ]，5) => 11，10，9，8，7
findLargest([ 15，5，3，1，10，8，7，6]，3) => 15，10，8
这样做无需复制或修改数组(只需从数组中读取)。优化时间复杂度。
我想出了这个问题，但对我的解决方案并不满意：
function findLargest(numberArrays, n ) {
var results = [];
var p
浏览 1提问于2015-11-19得票数 3
2回答
我有下面的代码来返回两个数字的索引，这些数字加起来就是给定的目标。代码的时间复杂度是多少？我很感激你的解释。谢谢。
int[] result = new int[2];
int i=0, k=i+1;
while (i < nums.length)
{
if(nums[i]+nums[k]==target && i!=k)
{
result[0]=i;
result[1]=k;
break;
}
else
浏览 3提问于2020-06-19得票数 0
回答已采纳
我不确定这个问题是否已经被问过了，但是我遇到了一个时间复杂性的问题，并且找不到答案。
我知道遍历大小为n的链表的时间是O(n)，但是如果链表被分成k个组，并且每个组的头存储在一个列表中，那么使用嵌套的for循环遍历列表中的k个组的时间复杂度是多少。它仍然是O(n)吗？
浏览 3提问于2021-09-13得票数 0
3回答
我正在练习为空间或时间复杂性优化的编写算法。使用主筛，至少您必须存储找到的所有素数的列表。数据与所找到的素数成正比，似乎是这样的算法所能使用的最小空间。
这个理由是否成立呢？
如何评估该算法的空间复杂度？
-我不确定当素数超过这个数时，一个筛子如何使用O(n^1/2)空间。这就是为什么至少空间必须与素数成比例的原因。我是不是把可数数和空间复杂性搞混了？
，他们的算法打印“到N...Here的质数”内存不包括打印机使用的纸张。这似乎是对空间的不公平计算。
我希望澄清应如何客观地衡量这一情况。
def prime_sieve(limit):
factors =
浏览 5提问于2014-10-20得票数 1
回答已采纳
2回答
我正在阅读排序方法，包括冒泡排序、选择排序、合并排序、堆排序、桶排序等。它们还包含时间复杂性，帮助我们知道哪种排序是有效的。所以我有个基本问题。如果我们包含的数据比我们将如何选择排序。时间复杂度是决定排序方法的参数之一。但是，我们是否有另一个参数来选择排序方法？
只是为了更好的理解而找出分类。
查询堆排序：
我们在哪里使用堆排序？
堆排序有什么更大的优势(除了时间复杂度O(n log ))？
堆排序的缺点是什么？
堆的构建时间是多少？(我听说了O(n)，但我不确定。)
任何必须使用堆排序或堆排序的场景都是更好的选择(除了优先级队列)？
在对数据应用堆排序之前，我们将查看
浏览 1提问于2012-03-21得票数 12
回答已采纳
1回答
RSA的安全性取决于一个简单的假设：
给定N，e，y= (x ^e) mod N，确定x是难以计算的。
这一假设很有道理。伊芙怎么可能猜到x？
她可以试验x的所有可能值，每次检查x^e是否等于y mod N，但这需要指数时间。或者，她可以尝试用因子N来检索p和q，然后通过反演e模(p-1)(q-1)求出d，但我们认为因式分解很难。顽固性通常是令人沮丧的根源；RSA的洞察力在于利用它来获得好处。
我对上述案文的提问
在上面的上下文中，我们如何得到x的每个值的指数计算时间？
浏览 1提问于2017-12-22得票数 2
5回答
如何检查是否可以将n划分为连续素数序列的和。
例如，12等于5+7，其中5和7是连续素数，而20等于3+17，后者3和17不是连续的。
注意，重复是不允许的。
我的想法是在n下面查找并列出所有素数，然后使用2个循环来和所有素数。前两个数字，第二个数字，第三个数字等等，然后是前三个数字，第二个数字，到目前为止。但这需要很多时间和记忆。
浏览 6提问于2014-10-30得票数 4
回答已采纳
2回答
我是计算机科学的新手，刚开始接触伪代码，我有一些问题。这是我这学期的第三周，大部分时间都是自学。我有几个问题：
O(n^2)和O(n)算法的区别是什么？-类似地，O( n )和Ω(n^2)是什么？
到目前为止，我已经写了：
horner = 0;
for( i = n; i >= 0; i −− )
horner = x * horner + a[i];
但发现它是O(n)。如何对其进行转换？
运行时间是多少？-我知道第一行的赋值是1个操作
它在实际的，比如说C#算法中是什么样子的？
浏览 3提问于2015-01-03得票数 4
1回答
当我读到有关量子算法的文章时，我遇到了Deutsch-Jozsa算法，我看到如果我们想用非量子算法来解决这个问题，我们的算法将具有指数时间复杂度。现在我想知道Deutsch-Jozsa算法作为量子计算机上的量子算法的时间复杂度是多少？
浏览 1提问于2011-08-20得票数 1
3回答
如何在java中计算算法的空间和时间复杂度。
使用System.nanoTime()执行的总时间是否等于任何算法或函数的时间复杂度？
例子:斐波那契数列中第n个数的空间和时间复杂度估计
浏览 0提问于2010-12-15得票数 3
回答已采纳
我正在尝试创建一个Java程序来查找两个数组之间的公共元素/年龄。然而，我需要该算法必须运行在大O(n log n)或大O(log n)的时间复杂度。这就是我想出来的，对如何改进它有什么想法吗？我是否也正确地计算了手术的步骤？
int [] AgeMale = {21, 19, 24, 22, 20, 23, 18}; //Program is executed 1 time
int [] AgeFemale = {17, 17, 22, 19}; //Program is executed 1 time
System.out.println("Age of m
浏览 2提问于2021-01-20得票数 3
回答已采纳
1回答
我遇到了一个数组排序算法，它看起来很好，但是它使用子数组递归。我听说制作一个子数组的时间复杂度是O(n)，这或多或少会阻止任何有效的排序使用子数组。
算法：
转一转。出于演示的目的，我们每次都将它称为数组中的最后一个数字。
将枢轴放在正确的位置。在这里，你会看到2和6，如果6大于2，就把它放在2之后。然后看1和2，如果它小于，就把它放在左边。如果两个数字相等，我选择将轴心放在左边。
取枢轴左侧和右侧的子数组，并在这些子数组上循环。
当子数组大小为1时停止。
一个有效的例子：
6 1 7 8 6 9 1 2 Pivot would be 2
1 1 2 6 6 7 8 9
浏览 0提问于2015-11-14得票数 1
2回答
如果我有一个数字列表，其中数字增加到一个点，然后在该点之后减少，是否存在与集合大小无关的有限次猜测，以便找到该最大值？
值之间的距离是任意的，并且增加侧的值的数量可以不同于减少侧的值的数量。
最好的方法是什么？检查元素1，然后是最后一个元素，然后是?之间的一半。再重复一遍？或者更复杂的东西？
这种算法的处理时间是多少？
浏览 3提问于2012-11-19得票数 0
1回答
检查给定输入是否为回文的以下代码的时间复杂度是多少？
public boolean isPalindromeRecursion(String input, int first, int last) {
if (input.charAt(first) != input.charAt(last)) {
return false;
} else if (first >= last) {
return true;
}
return isPalindromeRecursion(input, first + 1, last - 1);
浏览 3提问于2020-07-16得票数 1
回答已采纳
在Java中实现math.sqrt的时间复杂度是多少？Java在某种技术中实现了时间复杂度，我正在尝试确定其时间复杂度。
浏览 2提问于2015-03-03得票数 3
1回答
基于我的研究，我得到了关于这个简单算法的相互矛盾的信息。该算法是一个基本的矩阵变换，它是一个n×n矩阵A的换位算法。
我目前的理解是，该算法将在O(n^2)时间运行，空间复杂度为O(1)，因为我们操作的矩阵与我们处理的矩阵相同。
但是-我也被告知它实际上会运行O(n)时间，并且具有O(n)的空间复杂性。这意味着它不会到位，因为它需要额外的空间来操作。
对于下面的转位来说，哪个思维过程是正确的？
Transpose(A)
1. for i = 1 to n -1
2. for j = i + 1 to n
3. exchange A[i, j] with A[j
浏览 4提问于2022-02-15得票数 1
回答已采纳
5回答
我需要帮助。我有一个确定int是否为质数的方法：
public boolean isPrime(int n) {
if (n % 2 == 0) {
return false;
}
for (int i = 3; i < n; i += 2) {
if (n % i == 0) {
return false;
}
}
return true;
}
谁能告诉我如何确定这个程序运行的最坏情况时间？然后
浏览 2提问于2016-05-05得票数 0
for i = 0 to size(arr)
for o = i + 1 to size(arr)
do stuff here
这个问题最糟糕的时间复杂度是多少？它不是N^2，因为第二个循环每i次循环减一。它不是N，它应该更大。N-1 + N-2 + N-3 + ... + N-N+1。
浏览 1提问于2013-01-14得票数 0
回答已采纳
1回答
如果我合并、排序一个数组并对其应用二进制搜索函数，时间复杂度会是多少？会是O(log n)吗？ 因为 o(log n) + o(n log n) = O(log n)
浏览 10提问于2020-07-16得票数 0
2回答
例如，如果我对某个数据结构有一个递归算法
Algo(Tree T)
if T == null
return false
...
当树为空时，该算法的最佳情况会出现吗？时间复杂度为O(1)？
浏览 5提问于2020-06-26得票数 0
用于在排序列表中搜索元素。从索引0开始获取元素，然后从索引1、2、4、8、16开始，直到超出目标，然后在刚刚找到的范围内再次搜索。
这个问题的时间复杂度是多少？对我来说，这似乎是某种对数时间复杂度，但我不知道是什么。
浏览 7提问于2011-03-11得票数 6
回答已采纳
N(总no )的时间复杂度是多少？元素)？
函数将嵌套的整数列表(List[Listint])扁平化为单个列表，并仅保留第一次出现，从而删除重复项。
def f2(list_of_list):
flat_list = []
for inner_list in list_of_list:
flat_list.extend(inner_list)
return [
x for i, x in enumerate(flat_list)
if flat_list.index(x) == i]
浏览 7提问于2022-06-11得票数 -2
我正在尝试设计一种算法来查找数组中两个相同元素的索引。输入是一个数组，输出是两个索引i&j，使得arrayi=arrayj。时间复杂度必须为O(nlogn)。
这是我尝试过的
let i=0 to size_of_array{
let j=i+1 to size_of_array{
if array[j]=array[i]{
print(i, j)
}
}
}
嵌套循环是O(n^2)，但如果我尝试这样设计。时间复杂度是多少？
N是数组的大小，我的实现将运行O(n(n-1)+(n-2)+(n-3)....+1)次。它
浏览 1提问于2019-09-17得票数 0
3回答
从1生成素数到n个Python 3。如何提高效率，复杂度是多少？
输入:一个数字，最大(一个大数目)输出:从1到最大输出的所有素数都是以列表的形式出现的，将是2,3,5,7,11,13，.代码试图以一种有效的方式(最少的时间复杂度)执行此任务。
from math import sqrt
max = (10**6)*3
print("\nThis code prints all primes till: " , max , "\n")
list_primes=[2]
def am_i_prime(num):
"""
浏览 0提问于2018-11-10得票数 0
回答已采纳
3回答
堆排序可以使用链表和数组来实现。
最理想的方法是使用链表还是数组？
使用数组和链表构建堆的时间复杂度是O(nlogn)吗？
删除的时间复杂度是多少？
浏览 2提问于2013-01-29得票数 0
1回答
我有一个名为字母数字的字符串，它包含所有字母和数字。 alphanumeric = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890" 我想遍历单个字符的列表(有些是字母数字的，有些是简单的标点符号)，以找出哪些是字母数字的。这条线的时间复杂度是多少： if character in alphanumeric: 是吗？我不确定字符串是否是时间复杂度的列表，因为在查看Python wiki (https://wiki.python.org/moin/TimeComplexity)时，操作"x
浏览 21提问于2019-10-13得票数 1
例如，如果我有一组数字，我在一维数组中填充一个副本，在二维数组中填充一个副本。所以从本质上讲，我有，并将始终在每个数组中有相等数量的元素。在这种情况下，时间复杂度是否真的不同，记住元素的数量将总是相等的？
浏览 0提问于2018-05-25得票数 1
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
即时通信 IM
实时音视频活动推荐
腾讯云开发者
