js使用递归函数计算n以内的素数（质数）和？

来源：蜘蛛抓取(WebSpider) 时间：2022-07-14 07:52 标签： python 递归函数

  • 云安全隐私计算(TCSPC)以联邦学习、MPC（安全多方计算）、TEE（可信执行环境）等隐私数据保护技术为基础的隐私计算平台，TCSPC针对机器学习算法进行订制化的隐私保护改造，保证数据不出本地即可完成联合建模，同时支持安全多方PSI、安全隐私查询统计分析，提供基于硬件的TEE可信计算。通过TCSPC最大化各个合作企业在数据安全的基础上的数据价值，很好地解决了业界数据孤岛的难题。

直接遍历，判断每个数字是否能整除 2 一直到自身，如果都不能被整除，那么就是素数。

接着是一个细微的改进版本：

不知道你有没有发现，在判断整除的时候其实做了很多无用功，每个数字都不能整除大于自己一半以上的数字。那么我们直接把第二个循环的 num 替换成 num/2+1（+1 的原因是 range 的后半部分是开区间，在遍历时只会输出 num/2）。

如果你刷 LeetCode 做到 Count Prime 这题的话，会发现这个改进的方法还是无法 AC ！！！

好了，厄氏大法该你上场了！

西元前250年，希腊数学家厄拉多塞(Eeatosthese)想到了一个非常美妙的质数筛法，减少了逐一检查每个数的的步骤，可以比较简单的从一大堆数字之中，筛选出质数来，这方法被称作厄拉多塞筛法(Sieve of Eeatosthese)。

具体操作：先将 2~n 的各个数放入表中，然后在2的上面画一个圆圈，然后划去2的其他倍数；第一个既未画圈又没有被划去的数是3，将它画圈，再划去3的其他倍数；现在既未画圈又没有被划去的第一个数 是5，将它画圈，并划去5的其他倍数……依次类推，一直到所有小于或等于 n 的各数都画了圈或划去为止。这时，表中画了圈的以及未划去的那些数正好就是小于 n 的素数。

最后回答题目图片里的问题：「return True 为什么要放在 for 循环的外面？」

由上文可知，显然当所有 n % i 等于 0 的都不成立时，才能判断 n 是素数。

如果直接放循环体内，那么相当于只判断了一次就 return 了，不能判断 n 是否为素数。

Q：你将如何验证一个素数？

A：一个素数只能被它自己和1整除。所以，我将运行一个while循环并加1。（看代码示例，如果你无法理解，那这不是你的菜。先回去学习javaScript基础知识然后再回来吧。）

A：可以。除数一次增加1个。 在3之后我可以增加2.如果一个数可以被任何偶数整除，它将被2整除。

补充：如果你不需要把除数增加到这个数。你可以更早停止。让我在下面的步骤中解释一下（如果需要可以多读几遍）

第一步，任何数字都不能被大于它的一半的数字整除。 例如，13将永远不能被7,8,9整除……它甚至可以是偶数的一半。 例如，16将被8整除，但永远不会被9,10,11,12 ……
结论：一个数字将永远不能被一个大于其一半数值的数字整除。 所以，我们可以少循环50％。

第二步，现在，如果一个数字不能被3整除。（如果它可被3整除，那么它就不是质数）。然后，它不可以被大于其值1/3的任何数整除。例如，35不能被3整除。因此，它永远不会被大于35/3的数整除，永远不能被12, 13, 14整除…如果你取一个像36一样的偶数，它将永远不能被13, 14, 15整除。

结论： 一个数字可以被其数值的三分之一整除。

第三步，例如，你有一个数字127。127不能被2整除，因此你最多应该检查63.5。其次，127不能被3整除。因此，您将检查到127/3大约42。它不能被5整除，除数应该小于127/5大约25，而不是7。那么，我们该在哪里停下来？

如果你不能理解也不用担心，别管它。如果那你不是一个研究人员就没关系。

Q：如何求出一个数的所有素数因子？
A：执行一个while循环。开始除以2，如果不能整除，记录这个除数，直到完成。

Q：运行时间复杂度是多少？ 你能做得更好吗？

A：O(n)。可以将除数从3开始，累加2。因为，如果一个数被任何偶数整除，它将被2整除。因此，你不需要除以偶数。此外，你不会有一个大于其价值一半的因素。如果你想让它变得复杂，那就用第一题的补充概念吧。

Q：如何获得第n个斐波纳契数字？
A： 我创建一个数组并从迭代开始。

斐波那契系列是面向初学者的最受欢迎的面试问题之一。 所以，你必须学习这一个。

Q： 运行时间复杂度是多少？

Q： 你能让它递归吗？

Q： 运行时间复杂度是多少？
A： O(2n)；关于时间复杂度的细节

Q: 你会如何找到两个数字的最大公约数？

很抱歉。我也无法解释它。 因为我自己80％的情况下都不能理解它。 我的算法分析教练告诉我这个，又从课堂笔记偷走（我是一个好学生，顺便说一句！）

注意：用你的大脑来理解它。

Q：你将如何从数组中删除重复的成员？
A： 执行一个循环，并保存一个对象/关联数组。如果我第一次找到一个元素，我会设置它的值为真（这将告诉我元素添加一次）。如果我在对象中找到这个元素，我不会将它插入到返回数组中。

Q： 怎样合并两个已排序数组？
A： 我将为每个数组保留一个指针（看代码，并注意这个）。

不通过临时变量交换两个数的值

Q：如何在不使用临时变量的情况下交换两个数字？ 

 
 

 
 

 Q：如何在JavaScript中反转字符串？
A：可以遍历字符串并将字母连接到新字符串。
 
 

 
 
 
 

 Q：你知道在现代浏览器中串联效果很好，但在像IE8这样的旧浏览器中会变慢。 还有什么不同的方法，可以扭转一个字符串？

 

 A：当然.我可以使用数组，也可以添加一些检查。如果字符串是NULL或其他字符串，这将失败。让我也做一些类型检查。使用此数组类似于在某些服务器端语言中使用字符串缓冲区。
 
 

 
 
 
 

 Q： 运行时间复杂度是多少？
A： O(n)；
Q：可以做得更好？
A：我可以遍历索引的一半，它会节省一点点。 （这是没用的，可能不会打动面试官）
 
 

 
 
 
 

 Q：这有效，但你可以做递归的方式吗？
A：可以。
 
 

 
 
 

 
 

 Q：你可以在方法中使用任何构建，使它更清洁吗？
 
 
 
 

 
 

 Q：你可以做反向函数作为字符串扩展吗？
A：我需要将这个函数添加到String.prototype，而不是使用str作为参数，我需要使用this
 
 
 

 
 

 Q：你如何在句子中颠倒单词？
A：您必须检查整个字符串的空白区域。确定是否可能有多个空格。
 
 
 
 

 内置方法的快速解决方案：
 
 
 

 
 

 

 A: 要做到这一点，我必须做字符串反向和字反转。
 
 
 

 Q: ok。好的，你能不使用内置反向函数做到吗？
A: (内心独白)有没有搞错！！
 
 
 
 

 
 

 Q: 怎么在字符串中找到第一个非重复字符？
A: 有什么条件吗？
A: 比如是否区分大小写？
面试官可能会说No。
A: 是长字符串还是短字符串？
Q: 这些有什么关系吗？

 

 A:例如，如果它是一个非常长的字符串，说一百万个字符，我想检查是否有26个英文字符正在重复。 我可能会检查是否所有字符都在每200个字母中重复（例如），而不是循环遍历整个字符串。 这将节省计算时间。
Q: 简单起见， 这个字符串是 “the quick brown fox jumps then quickly blow air”。
 
 
 
 

 这有一个问题，不能再循环中及时退出。
 
 

 
 

 Q: 怎样删除字符串中的重复字符？
 
 

 A: 这与第一个非重复字符非常相似。你应该问一些类似的问题。它是区分大小写的吗？。
 
 

 如果面试官说，这是区分大小写的，那么你就很轻松了。 如果他说不。你可以使用string.toLowercase（）来把字符串。面试官可能不喜欢这个方法。 因为返回字符串不会拥有相同的大小写。 所以
 
 
 
 

 
 

 Q: 如何检查一个字符串是否是回文？
 
 

 A: 把字符串反转，如果反转前后相等，那么它就是回文。
 
 
 
 

 
 
 
 

 类似的：在 O(n)时间复杂度内判断一个字符串是否包含在回文字符串内。你能在O（1）时间解决问题吗？
 
 

 
 

 Q: 在一个1到100的未排序数组中找到缺失的数，你怎么做？
 
 

 说明：数组中的数字为1到100。 数组中只有一个数字缺失。数组未排序。找到缺少的数字。
 
 

 A: 你必须表现得像是在想很多。然后讨论n＝n（n＋1）／2的线性级数之和
 
 
 
 

 注意： 这个会返回任意长度数组中缺失的那个
 
 

 
 

 Q: 在一个未排序的数组中找出是否有任意两数之和等于给定的数？
A: 简单！双重循环。
 
 
 
 

 Q: 时间复杂度？
A: O(n2)。
Q: 有更优解？
A: 我想想。我可以用一个对象来存储当前元素和和值的差值。当我拿到一个新元素，如果这个元素的差值在对象中存在，那么我就能判断出是否存在。
 
 
 
 

 
 

 Q: 找到任意两个元素的最大总和？
 
 

 A: 这实际上非常简单直接。 找到两个最大的数字并返回它们的总和
 
 
 
 

 
 

 Q: 统计从1到n的零总数？
 
 

 
 

 说明：所以这里的重点是。 如果你有一个1到50的数字，那么这个数值就是5，就是50除以10.然而，如果这个数值是100，这个数值是11，你将得到100/10 = 10和 10/10 = 1。 那就是你将如何在一个数字中得到更多的零，如（100，200，1000）；
 
 
 
 

 
 

 Q: 在字符串中匹配子字符串？
 
 

 A: 在迭代字符串时将使用指针（一个用于字符串，另一个用于子字符串）。 然后用另一个变量来保存初始匹配的起始索引。
 
 
 
 

 
 

 Q: 如何获取字符串中的所有排列？
 
 

 A: 根据您对算法的了解程度，这可能会很困难。、
 
 
 
 

 
 

 以上所述是小编给大家介绍的Js面试算法详解，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对脚本之家网站的支持！

我要回帖

更多关于 python 递归函数 的文章

 

随机推荐