首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

判断个数是否素数代码(判断10000以内数是不是素数)

素数(也叫质数)数学定义:大于1自然数中除了1和它本身外没有其他因数整数,常见素数有:2,3,5,7,11,13……等,判断个数是不是素数经常作为考试题目。...算法 算法1 算法描述: 令i=2,n需要判断数; 如果n=2,则判断n是否等于2,如果n=2,则输出:n是素数,否则执行第3步骤; 判断i<n是否成立,如果成立则计算...该算法时间复杂度: 最好:O(1),此时走图1中左边两条路径,不进循环 最差:O(n-2),此时进入取模循环体中 算法2 该算法是对算法1改进 算法描述: 令i=2,n需要判断数; 如果n=2,则判断n是否等于2或3,如果n=2 || 3,则输出:n是素数,否则执行下步; 判断i<=sqrt(n)是否成立,如果成立则计算n%i,如果不成立,则输出:n是素数...所以算法2整体时间复杂度算法1底,相比之下,算法2更有优势。

84220
您找到你想要的搜索结果了吗?
是的
没有找到

文搞懂算法时间复杂度与空间复杂度

时间复杂度概念   般情况下,算法基本操作重复执行次数是模块n函数f(n),因此,算法时间复杂度记做 T(n) = O(f(n))。...随着模块n增大,算法执行时间增长率f(n)增长率成正比,所以f(n)越小,算法时间复杂度越低,算法效率越高。   ...时间复杂度常用大O符号表示,这个算法时间复杂度就是O(n)。...二 计算时间复杂度 计算出基本操作执行次数T(n)   基本操作即算法每条语句(以;号作为分割),语句执行次数也叫做语句频度。在做算法分析时,般默认为考虑最坏情况。...比如直接插入排序时间复杂度是O(n^2),空间复杂度是O(1) 。而递归算法就要有O(n)空间复杂度了,因为每次递归都要存储返回信息。

4.8K81

每日问之算法时间复杂度

我们用简单查找的话,需要遍历检查个元素,因此需要执行 n 次操作。使用大 O 表示法,其运行时间 O(n),f(n) = n 操作数。...比如,检查长度 8 列表,用简单查找法时间复杂度是 O(f(n)),f(n) = 8;如果用二分查找的话,时间复杂度是 O(f(n)),f(n) = log2 8 = 3。...O(1):描述了算法不管输入大小是多少,其时间复杂度永远为常数(不变)。比如,下方例子,判断个字符串 list 首个元素是否空。...因为无论输入 list 有多长,都只判断首字符是否空,执行次数 1,所以时间复杂度 O(1)。...比如,下面的代码是两层迭代,按照最坏打算,迭代总次数 ixj,是两个数相乘,可以直接表示 nxn,即 n 平方。所以,时间复杂度可以表示 O(n2)。

63250

Python-排序-有哪些时间复杂度O(n)排序算法

前几篇文章介绍了几个常用排序算法:冒泡、选择、插入、归并、快速,他们时间复杂度从 O(n^2) 到 O(nlogn),其实还有时间复杂度 O(n) 排序算法,他们分别是桶排序,计数排序,基数排序...,因为这些排序算法时间复杂度是线性,所以这类算法也叫线性排序。...这个问题非常好,原因是这样,当桶个数 m 接近与 n 时,log(n/m) 就是个非常小常数,在时间复杂度时常数是可以忽略。...比如极端情况下桶个数和元素个数相等,即 n = m, 此时时间复杂度就可以认为是 O(n)。...除此之外,每数据范围不能太大,要可以用线性排序算法来排序,否则,基数排序时间复杂度就无法做到 O(n) 了。

1.4K20

求解逆序对个数(由归并排序衍生出O(nlogn)时间复杂度算法)

) { if (a[i] > a[j]) res ++; } } return res; } 可以看到,上边算法时间复杂度O(n^2),有没有效率更高算法呢,其实在归并排序中,当进行两个有序数组合并时就会两两元素比较...此时会出现,当第个数某元素a[i]大于第二数组中某元素a[j]时,则个数组处于[i, m]区间所有元素都会大于第二个数组的当前元素a[j]。...这样做好处是不需要将数组中元素依次进行两两比较,次比较就能处理个大区间,因此算法效率得到了提升。..., int r) { if (l>=r) return; int m = (r-l)/2 + l; mergeSort(a, l, m); mergeSort(a, m+1, r); //i个区间起始下标...第个区间[l, m] //j第二个区间起始下标 第二个区间[m+1, r] //k临时数组起始下标 int i = l, r = m+1, k = 0; while (i <=

35220

如何高效判断个数组里是否含特定元素判断个数组里是否含有特定元素四种方法时间复杂度测试小结

如何高效判断个数组里是否含特定元素?...这是我们在实际开发中经常遇到个问题,也是在Stack Overflow上热门问题,解决这个问题有很多不同方法,但是不同方法时间复杂度却差别很大,所以本文会列举常用几种方法,并且对比每个方法耗时...判断个数组里是否含有特定元素四种方法 使用list //Using List public static boolean useList(String[] arr, String targetVal...我们可以用大量数据来重复测试,以放大各个方法之间执行时间差别。...小结 我们发现当数组是无序时候,我们如果要判断个数组中是否含有个元素,应该使用直接循环查找,这样效率是最高,如果数组是有序情况下,我们应该使用二分查找,此外,如果是在hashset或hashmap

1.2K20

个,时间复杂度O(n)排序!

桶排序(Bucket Sort),是时间复杂度O(n)排序。 画外音:百度“桶排序”,很多文章是错误,本文内容与《算法导论》中桶排序保持致。...桶排序适用范围是,待排序元素能够均匀分布在某个范围[MIN, MAX]之间。 画外音:很多业务场景是符合这场景,待排序元素在某范围内,且是均匀分布。...桶排序需要两个辅助空间: (1)第个辅助空间,是桶空间B; (2)第二个辅助空间,是桶内元素链表空间; 总的来说,空间复杂度是O(n)。...上图所示: (1)待排序数组unsorted[16]; (2)桶空间是buket[10]; (3)扫描所有元素之后,元素被放到了自己对应桶里; (4)每个桶内,使用插入排序,保证直是有序; 例如...桶排序(Bucket Sort),总结: (1)桶排序,是复杂度O(n)排序; (2)桶排序,是种稳定排序; (3)桶排序,适用于数据均匀分布在个区间内场景; 希望这分钟,大家有收获。

95230

算法时间与空间复杂度看就懂)

空间维度:是指执行当前算法需要占用多少内存空间,我们通常用「空间复杂度」来描述。 因此,评价算法效率主要是看它时间复杂度和空间复杂度情况。...时间复杂度 我们想要知道算法时间复杂度」,很多人首先想到方法就是把这个算法程序运行遍,那么它所消耗时间就自然而然知道了。 这种方式可以吗?当然可以,不过它也有很多弊端。...,因此,我们可以简化将这个算法时间复杂度表示:T(n) = O(n) 为什么可以这么去简化呢,因为大O符号表示法并不是用于来真实代表算法执行时间,它是用来表示代码执行时间增长变化趋势。...空间复杂度比较常用有:O(1)、O(n)、O(n²),我们下面来看看: 空间复杂度 O(1) 如果算法执行所需要临时空间不随着某个变量n大小而变化,即此算法空间复杂度个常量,可表示 O(1)...,这个数据占用大小n,这段代码2-6行,虽然有循环,但没有再分配新空间,因此,这段代码空间复杂度主要看第行即可,即 S(n) = O(n) 以上,就是对算法时间复杂度与空间复杂度基础分析

79420

些简单例子看算法时间复杂度

些简单例子看算法时间复杂度     在编程中,段代码执行效率实际上很难估算和预测,其主要受到如下几个方面的影响: 1.算法依据数学基础。 2.编译器产生代码质量和语言执行效率。...在理解时间复杂度之前,你应该先了解什么叫做算法时间频度,所谓时间频度即是算法解决问题所消耗时间。...计算算法时间复杂度时,我们可以将算法分解逐条语句,计算每条语句时间复杂度后再进行累加,如下代码作用是对输入进行求累加: let n = 10; let res = 0; //1 for...设算法时间复杂度函数f(n),(3n+5)/f(n)当n趋于无穷大时,上式可以简化为3n/f(n),取f(n)=n,上次结果非零常数,因此此算法时间复杂度f(n)=n,记做O(n)。    ...当算法执行时间频度和n无关时,算法时间复杂度O(1),这是时间复杂度最小函数,但是需要注意,时间复杂度小并不能说明算法执行耗费时间短,比如一万行代码每行只执行算法时间复杂度O(1)。

46310

检查个数据库里表名、字段是否种方法

难道要检查?! 我们可以使用两个视图和几个SQL语句来检查下。 1、建立视图: 这个视图大家不太陌生吧,写过代码生成器兄弟们都很熟悉吧。...他可以看到个数据库里表名、字段名、字段类型、和字段大小信息。 建立两个这样视图,个读取客户数据库,个读取新数据库。这样我们就有了两个数据库表和字段信息列表了。...col INNER JOIN       .sysobjects obj ON col.id = obj.id ORDER BY obj.name 2、执行查询语句 我们可以使用 not in 方式来检查表名是否致...表致了之后,我们开始来检查字段名称。...不过对于视图和存储过程 只能得知名称和字段、参数是否致,如果参数没有变化,只是修改了下内容的话就检查不出来了。 3、如果是修改表名或者是修改字段名、删除字段名就没有检查了。

1.7K80

场面试,带你彻底掌握递归算法时间复杂度

很多同学对递归算法时间复杂度都不甚了解 同道题目,同样使用递归算法,有的同学写出了O(n)代码,有的同学就写出了O(logn)代码 这是为什么呢, 就是因为对递归时间复杂度理解不够深入导致...如果恰巧正在读本文你也对递归算法时间复杂度懵懵懂懂,请认真读完本篇文章,定会有所收获 这里我想通过道简单面试题,来带大家逐步分析递归算法时间复杂度,最后找出最优解。...,问这份代码时间复杂度是多少呢?...时间复杂度是多少 依然还是看他递归了多少次 我们可以看到 这里仅仅有个递归调用,且每次都是 n/2 所以这里我们共调用了 log以2底n对数次 每次递归了做都是次乘法操作,这也是个常数项操作...如果同学们最后写出了这样代码并且时间复杂度分析非常清晰,相信面试官是比较满意。 最后希望通过这么个简单面试题,让大家真正了解了递归算法时间复杂度该如何分析。

59210

个测试类简化排序算法时间复杂度研究

、背景 在学习算法过程中,除了熟练掌握各种算法程序逻辑外,还经常需要用到些测试案例对算法时间复杂度做具体测试。...本文将通过打造个测试类工具包,让我们可以更简便地研究排序算法时间复杂度。...二、概念 2.1、时间复杂度定义 即从序列初始状态到经过排序算法后形成最终排序状态这个过程所花费时间度量 2.2、时间复杂度比较 排序算法 时间复杂度(平均) 时间复杂度(最好) 时间复杂度...三、测试类 3.1、程序结构 便于文章书写,该测试类只实现了插入排序与快速排序,读者可根据接口定义自行加入其他排序算法。 ?...3.2、测试工具类 生成个乱序数组 生成个从0开始近乎顺序整型数组 对整型数组做完全拷贝 判断整型数组是否已经升序排列 遍历打印数组 通过排序接口,调用各种排序算法进行测试 /** * 整数排序测试工具类

48920

面试官:判断个数是否2整数次幂

题目 判断个正整数是否是2整数幂(如4是22次方,返回true;5不是2整数次幂,则返回false)。要求性能尽可能高。...第二种考虑(除法) 2整数次幂都能被2整除,所以进入个循环,让目标对2求余,如果有余数,则目标不是2整数次幂,如果没有余数,然后目标赋值目标除以2,直到目标小于1,当目标小于1时候则说明明目标是...第三种考虑(位运算) 让我们看看2整数次幂转成二进制是什么样 十进制 二进制 是否2整数次幂 8 1000 是 16 10000 是 32 100000 是 64 1000000 是 100 1100100...十进制 二进制 原数值减1 是否2整数次幂 8 1000 111 是 16 10000 1111 是 32 100000 11111 是 64 1000000 111111 是 100 10000000...十进制 二进制 原数值减1 n&n-1 是否2整数次幂 8 1000 111 0 是 16 10000 1111 0 是 32 100000 11111 0 是 64 1000000 111111

1K20
领券