幸运数字 - 它是 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 由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 的学习曲线较陡峭,适用于高性能和低级控制的场景。

C#和C 在面向对象编程(OOP)中的实现方式和特性上有显着差异。 1)C#的类定义和语法更为简洁,支持如LINQ等高级特性。 2)C 提供更细粒度的控制,适用于系统编程和高性能需求。两者各有优势,选择应基于具体应用场景。

从XML转换到C 并进行数据操作可以通过以下步骤实现:1)使用tinyxml2库解析XML文件,2)将数据映射到C 的数据结构中,3)使用C 标准库如std::vector进行数据操作。通过这些步骤,可以高效地处理和操作从XML转换过来的数据。

C#使用自动垃圾回收机制,而C 采用手动内存管理。1.C#的垃圾回收器自动管理内存,减少内存泄漏风险,但可能导致性能下降。2.C 提供灵活的内存控制,适合需要精细管理的应用,但需谨慎处理以避免内存泄漏。

C 在现代编程中仍然具有重要相关性。1)高性能和硬件直接操作能力使其在游戏开发、嵌入式系统和高性能计算等领域占据首选地位。2)丰富的编程范式和现代特性如智能指针和模板编程增强了其灵活性和效率,尽管学习曲线陡峭,但其强大功能使其在今天的编程生态中依然重要。

C 学习者和开发者可以从StackOverflow、Reddit的r/cpp社区、Coursera和edX的课程、GitHub上的开源项目、专业咨询服务以及CppCon等会议中获得资源和支持。1.StackOverflow提供技术问题的解答;2.Reddit的r/cpp社区分享最新资讯;3.Coursera和edX提供正式的C 课程;4.GitHub上的开源项目如LLVM和Boost提升技能;5.专业咨询服务如JetBrains和Perforce提供技术支持;6.CppCon等会议有助于职业

C#适合需要高开发效率和跨平台支持的项目,而C 适用于需要高性能和底层控制的应用。1)C#简化开发,提供垃圾回收和丰富类库,适合企业级应用。2)C 允许直接内存操作,适用于游戏开发和高性能计算。


热AI工具

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

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

Undress AI Tool
免费脱衣服图片

Clothoff.io
AI脱衣机

AI Hentai Generator
免费生成ai无尽的。

热门文章

热工具

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

SublimeText3汉化版
中文版,非常好用

SublimeText3 英文版
推荐:为Win版本,支持代码提示!

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

PhpStorm Mac 版本
最新(2018.2.1 )专业的PHP集成开发工具