幸运数字 - 它是 m > 1 的最小整数,对于给定的正整数 n,pn# + m 是素数,其中 pn# 是第一个 n 的乘积质数。
例如,要计算第三个幸运数字,首先计算前 3 个素数 (2, 3, 5) 的乘积,即 30。加 2 后得到 32,这是偶数,加 3 得到 33,是 3 的倍数。同样可以排除 6 以内的整数。加上 7 得到 37,这是一个素数。因此,7是第三个幸运数字。
第一个原初数的幸运数字是 -
3, 5, 7, 13, 23, 17, 19, 23, 37, 61, 67, 61, 71, 47, 107, 59, 61, 109 ….
问题陈述
给定一个数字n。找到第 n 个幸运数字。
示例 1
Input: n = 3
Output: 7
解释 - 前 3 个价格数字的乘积 -
2 3 5 = 30 30 + 7 = 37, a prime number.
示例 2
Input: n = 7
Output: 19
解释 - 前 7 个素数的乘积 -
2 3 5 7 11 13 17 = 510510 510510 + 19 = 510529, a prime number.
方法一:原始方法
解决该问题的一个简单方法是首先计算 pn#,即前 n 个素数的乘积,然后找到 pn# 与下一个素数之间的差。获得的差额将是一个幸运的数字。
伪代码
procedure prime (num) if num <= 1 ans = TRUE end if for i = 2 to sqrt(num) if i is a factor of num ans = false end if ans = true end procedure procedure nthFortunate (n) prod = 1 count = 0 for i = 2 to count < n if i is prime prod = prod * i count = count + 1 end if nextPrime = prod + 2 while nextPrime is not prime nextPrime = next Prime + 1 ans = nextPrime - prod end procedure
示例:C++ 实现
在下面的程序中,通过计算前n个素数的本初以及找到本初后的下一个素数来计算幸运数。幸运数是下一个素数与本初数之间的差。
#include <bits/stdc++.h> using namespace std; // Function to find if a number is prime or not bool prime(unsigned long long int num){ if (num <= 1) return true; for (int i = 2; i <= sqrt(num); i++){ if (num % i == 0) return false; } return true; } // Function to find the nth Fortunate number unsigned long long int nthFortunate(int n){ long long int prod = 1, count = 0; // Calculating product/primorial of first n prime numbers for (int i = 2; count < n; i++){ if (prime(i)){ prod *= i; count++; } } // Find the next prime greater than the product of n prime numbers unsigned long long int nextPrime = prod + 2; while (!prime(nextPrime)){ nextPrime++; } // Fortunate number is the difference between prime and primorial unsigned long long int ans = nextPrime - prod; return ans; } int main(){ int n = 15; cout << n << "th Fortunate number : " << nthFortunate(n); return 0; }
输出
15th Fortunate number : 107
时间复杂度 - O(nsqrt(n)),其中 prime() 函数的复杂度为 O(sqrt(n)),nthFortunate() 中的 for 循环的复杂度为 O(nsqrt(n))。
空间复杂度 - O(1)
方法 2:埃拉托斯特尼筛法
埃拉托色尼筛用于将所有质数达到一个极限,我们将给出一个值 MAX。在这种方法中,我们创建一个包含所有 true 条目的布尔数组,并将所有非素数索引标记为 false。然后将数组中的前 n 个素数相乘,得到前 n 个素数的乘积。然后与之前的方法类似,从 2 开始将乘积加 1,以获得下一个素数。下一个素数与乘积之差就是所需的幸运数。
伪代码
procedure nthFortunate (n) MAX is set prime[MAX] = {true} prime[0] = false prime[1] = false for i = 1 to i*i <= MAX if prime[i] for j = i*i to MAX with j = j + i in each iteration prime [j] = false end if prod = 1 count = 0 for i = 2 to count < n if prime[i] prod = prod * i count = count + 1 end if nextPrime = prod + 2 while nextPrime is not prime nextPrime = nextPrime + 1 ans = nextPrime - prod end procedure
示例:C++ 实现
在下面的程序中,大小为 MAX 的布尔素数数组记录了 MAX 之前的所有素数。然后通过将前 n 个素数相乘来找到原初。然后与之前的方法类似,找到nextPrime。 nextPrime 和 Product 的区别在于幸运数字。
#include <bits/stdc++.h> using namespace std; // Function to find the nth Fortunate number unsigned long long int nthFortunate(int n){ // Setting upper limit for Sieve of Eratosthenes const unsigned long long int MAX = 1000000000; vector<bool> prime(MAX, true); prime[0] = prime[1] = false; // Sieve of Eratosthenes to find all primes up to MAX for (unsigned long long int i = 2; i * i <= MAX; i++){ if (prime[i]){ // Setting all the multiples of i to false for (int j = i * i; j <= MAX; j += i){ prime[j] = false; } } } // Find the first n primes and calculate their product unsigned long long int prod = 1, count = 0; for (unsigned long long int i = 2; count < n; i++){ if (prime[i]){ prod *= i; count++; } } // Find next prime greater than product unsigned long long int nextPrime = prod + 2; while (!prime[nextPrime]) nextPrime++; // Fortunate number is difference between prime and product return nextPrime - prod; } int main(){ int n = 25; cout << n << "th Fortunate number : " << nthFortunate(n); return 0; }
输出
15th Fortunate number : 107
时间复杂度 - O(n log(log(n)))
空间复杂度 - O(MAX)
结论
综上所述,第n个幸运数可以通过以下两种方式找到。
初等方法:求前n个素数的乘积,并根据乘积计算下一个素数。质数与乘积之差是第 n 个幸运数。
埃拉托斯特尼筛法:找出所有达到某个极限的素数,然后计算与下一个素数的乘积,从而找到幸运数。
仅由于变量大小的限制,这两种方法对于较小的 n 值都是有效的。对于更大的值,需要更高效和优化的解决方案。
以上是找到第n个幸运数的详细内容。更多信息请关注PHP中文网其他相关文章!

C#和C 在性能上的差异主要体现在执行速度和资源管理上:1)C 在数值计算和字符串操作上通常表现更好,因为它更接近硬件,没有垃圾回收等额外开销;2)C#在多线程编程上更为简洁,但性能略逊于C ;3)选择哪种语言应根据项目需求和团队技术栈决定。

1)c relevantduetoItsAverity and效率和效果临界。2)theLanguageIsconTinuellyUped,withc 20introducingFeaturesFeaturesLikeTuresLikeSlikeModeLeslikeMeSandIntIneStoImproutiMimproutimprouteverusabilityandperformance.3)

C 在现代世界中的应用广泛且重要。1)在游戏开发中,C 因其高性能和多态性被广泛使用,如UnrealEngine和Unity。2)在金融交易系统中,C 的低延迟和高吞吐量使其成为首选,适用于高频交易和实时数据分析。

C 中有四种常用的XML库:TinyXML-2、PugiXML、Xerces-C 和RapidXML。1.TinyXML-2适合资源有限的环境,轻量但功能有限。2.PugiXML快速且支持XPath查询,适用于复杂XML结构。3.Xerces-C 功能强大,支持DOM和SAX解析,适用于复杂处理。4.RapidXML专注于性能,解析速度极快,但不支持XPath查询。

C 通过第三方库(如TinyXML、Pugixml、Xerces-C )与XML交互。1)使用库解析XML文件,将其转换为C 可处理的数据结构。2)生成XML时,将C 数据结构转换为XML格式。3)在实际应用中,XML常用于配置文件和数据交换,提升开发效率。

C#和C 的主要区别在于语法、性能和应用场景。1)C#语法更简洁,支持垃圾回收,适用于.NET框架开发。2)C 性能更高,需手动管理内存,常用于系统编程和游戏开发。

C#和C 的历史与演变各有特色,未来前景也不同。1.C 由BjarneStroustrup在1983年发明,旨在将面向对象编程引入C语言,其演变历程包括多次标准化,如C 11引入auto关键字和lambda表达式,C 20引入概念和协程,未来将专注于性能和系统级编程。2.C#由微软在2000年发布,结合C 和Java的优点,其演变注重简洁性和生产力,如C#2.0引入泛型,C#5.0引入异步编程,未来将专注于开发者的生产力和云计算。

C#和C 的学习曲线和开发者体验有显着差异。 1)C#的学习曲线较平缓,适合快速开发和企业级应用。 2)C 的学习曲线较陡峭,适用于高性能和低级控制的场景。


热AI工具

Undresser.AI Undress
人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover
用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool
免费脱衣服图片

Clothoff.io
AI脱衣机

Video Face Swap
使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸!

热门文章

热工具

SecLists
SecLists是最终安全测试人员的伙伴。它是一个包含各种类型列表的集合,这些列表在安全评估过程中经常使用,都在一个地方。SecLists通过方便地提供安全测试人员可能需要的所有列表,帮助提高安全测试的效率和生产力。列表类型包括用户名、密码、URL、模糊测试有效载荷、敏感数据模式、Web shell等等。测试人员只需将此存储库拉到新的测试机上,他就可以访问到所需的每种类型的列表。

SublimeText3 Linux新版
SublimeText3 Linux最新版

DVWA
Damn Vulnerable Web App (DVWA) 是一个PHP/MySQL的Web应用程序,非常容易受到攻击。它的主要目标是成为安全专业人员在合法环境中测试自己的技能和工具的辅助工具,帮助Web开发人员更好地理解保护Web应用程序的过程,并帮助教师/学生在课堂环境中教授/学习Web应用程序安全。DVWA的目标是通过简单直接的界面练习一些最常见的Web漏洞,难度各不相同。请注意,该软件中

ZendStudio 13.5.1 Mac
功能强大的PHP集成开发环境

安全考试浏览器
Safe Exam Browser是一个安全的浏览器环境,用于安全地进行在线考试。该软件将任何计算机变成一个安全的工作站。它控制对任何实用工具的访问,并防止学生使用未经授权的资源。