数学是科学之女王，素数可以说是数学中最核心的概念之一。关于素数有很多伟大的故事，最著名的是哥德巴赫猜想、素数定理和黎曼猜想有趣的是，分别是牛顿、欧拉、高斯和黎曼之后的三位最伟大的数学家，他们在这些问题上有着深厚的根基。我写这篇文章不是为了探索和解决这些伟大的猜测和定理，而是为了解决回归问题本身，使用计算机确定素数，并找到特定正整数值中包含的所有素数。这篇文章是我对素数问题思考的总结。
让我先说说素数的定义：
素数，也称为素数，是只能被和整除的非正整数。
第一个素数是，也是唯一的偶数素数。内素数列：
给定素数的定义，我们使用计算机程序来解决以下问题。
给定一个正整数，确定该数字是否为素数。
给定一个正整数，求所有小于或等于该数字的素数的列。
给定两个正整数，，找到它们之间的素数列。
从一开始就计算大素数。
解决上述问题的核心算法是Eratosthenes筛选法，称为Ehler筛选法。我们的想法是，每次我们得到一个质数，我们都会删除质数的所有倍数，重复这个过程，剩下的数必须是质数。
1.1.1算法
为了确定一个整数是否为素数，我们只需要确定该整数是否不可被小于它的非整数整除。
1.1.2代码
1.1.3算法复杂度
时间复杂度
空间复杂性
由于是唯一的偶数素数，我们可以对的情况进行特殊处理，并且每次只确定小于数的奇数情况。
1.2.1算法
要确定整数是否为素数，我们只需要确定
号码是“是”或“否”。
在该数不为奇数的情况下，确定该数是否不可被非奇数整除或小于非奇数。
1.2.2代码
1.2.3算法复杂度
时间复杂度
空间复杂性
事实上，为了确定一个整数是否为素数，我们可以通过改变之前的完整比较来减少决策范围，以确定该整数是否不可被从整数平方根向下舍入的非整数整除。
直觉是，一个自然数不能被一组整数整除。
该优化决策是可证明的。让我们来证明一下。
1.3.1证明
给定一个不可被平方根向下舍入的非整数整除的正整数，我们证明它必须是素数。
我们用矛盾来证明。
假设它是一个复合数，它必须表示为两个非整数的乘积。
我们还知道，它不能被向下舍入整数平方根的非整数整除，因此它不能包含和之间的素因子，否则它与可被1整除到的非整数相矛盾。
因此，它们都必须包含大于的素因子，这两个素因子分别表示为，。
因此
为什么 因为在这里，该值将是任何正实数。我们可以知道，任何正实数的向下舍入满足：
因此
尽量不要拖到明天。
1.3.2算法
为了确定一个整数是否为素数，我们只需确定该整数是否不可被从整数平方根向下舍入的非整数整除。
1.3.3代码
1.3.4算法复杂度
时间复杂度
空间复杂性
我们可以将1.2算法优化1和1.3算法优化2结合起来形成更好的算法。
1.4.1算法
要确定整数是否为素数，我们只需要确定
号码是“是”或“否”。
如果该数字不是，则该数字是否不能被以下数整除：
它是不可分割的，
一种非奇数，不能被平方根后向下舍入的整数整除。
1.4.2代码
1.4.3算法复杂度
时间复杂度
空间复杂性
很容易知道，这个问题是前一个问题的序列化，在平铺之后，它也将在前一问题的外层设置一层循环。
那么，让我们从一个初始算法开始。
2.1.1算法
给定一个正整数，求所有小于或等于该数的素数的列，即
对于从到的每个整数，我们依次决定该数是否为素数。如果它是素数，我们将该数字存储在生成的素数列中。
2.1.2代码
2.1.3算法复杂度
因为外层有一个额外的循环层，而内层确定整数是否为素数的算法是我们使用的初始算法，所以它的时间复杂度是，即。
空间复杂度，因为我们收集序列，所以这里的空间复杂度不是，而是。这里的值取自素数定理，即自然数中的素数，其渐近估计为。
时间复杂度
空间复杂性
这里，算法优化分为两部分。第一部分是确定单个整数是否为素数的优化。在第2部分中，我们优化了外环。
在第一部分中，我们采用第1.4节的算法优化，并将其结合起来，给出最终的优化方案。
在第二部分中，我们对循环内的数据执行一个简单的优化。也很容易知道，除了意外，所有的素数都是奇素数，所以这里我们也可以将外环确定的数据减半。
2.2.1算法
给定一个正整数，求所有小于或等于该数的素数的列，即
对于从和到的每个奇数，我们依次确定该数是否为素数根据1.4.1算法优化组合算法确定该数为素数。
如果它是素数，我们将该数字存储在生成的素数列中。
2.2.2代码
在这里，外部循环用于大于或等于的奇数，因此确定该数是否小于或等于、和是否可整除的内部方法是多余的，可以删除。更改为：
2.2.3算法复杂度
很容易知道外循环的时间复杂度为，内循环的时间复杂性为，因此总时间复杂度是。
空间复杂度仍然为零。
时间复杂度
空间复杂性
1.3在算法优化2中，确定整数是否为素数，即确定该数是否不能被整数平方根后向下舍入的非整数整除。
该位置的确定可以进一步优化以确定整数是否为素数，即该数字是否不可被向下舍入整数平方根的非素数整除。
直觉是，一个自然数不能被一组素数整除。
该证明是缩写的，与1.3.1算法优化2-证明相同。
有了以上的优化点，我们仍然缺少素列集。幸运的是，我们的目标是“给定一个正整数，查找所有小于或等于此数字的素数列”，这意味着包含了此信息，也就是说，目标基本相同。在这些条件下，我们可以在一定程度上优化2.1初始算法。
2.3.1算法
给定一个正整数，求所有小于或等于该数的素数的列，即
对于从到的每个整数，我们依次决定该数是否为素数。如果它是素数，我们将该数字存储在生成的素数列中。
确定一个数是否为素数的规则是它是否不可被一组素数列整除。
计算期间获得的素数列集。
2.3.2代码
在这种情况下，外部循环处理大于或等于该数字的奇数，因此确定该数字小于或等于该数值的内部方法是冗余的，可以在此处删除。更改为：
2.3.3算法复杂度
很容易知道外环的时间复杂度是；在内层，遍历素列集的时间复杂度为，因此总时间复杂度是。
获得空间复杂度为的素数列。
时间复杂度
空间复杂性
我们可以将2.2算法优化1和2.3算法优化2结合起来形成更好的算法。
针对2.4.1算法
给定一个正整数，求所有小于或等于该数的素数的列，即
对于从和到的每个奇数，我们依次确定该数是否为素数根据2.3.1算法优化2-算法确定该数为素数。
如果它是素数，我们将该数字存储在生成的素数列中。
2.4.2代码
2.4.3算法复杂度
很容易知道外环的时间复杂度是；在内层，遍历素列集的时间复杂度为，因此总时间复杂度是。
获得空间复杂度为的素数列。
时间复杂度
空间复杂性
这里有两种解决问题的方法：
对于第一类整数，我们依次确定它们是否为素数。如果它们是素数，我们收集它们并得到一个素数列。
其次，我们首先找出所有小于或等于的素列，然后取出的素列得到。
为了减少空间，1.4算法直接用于组合优化算法，而不是从头开始。
3.1.1算法
给定两个正整数，，找到它们之间的素数列，即
对于介于之间的整数，我们依次确定它们是否为素数。如果它们是素数，我们收集它们得到素数列。
确定素数的算法是1.4.1算法。
3.1.2代码
3.1.3算法复杂度
很容易知道外循环时间复杂度为，内循环时间复杂程度为，因此总时间复杂度是。
由于序列的集合，这里的空间复杂度是。
时间复杂度
空间复杂性
注：以上算法可以进一步优化。在外循环中，在我们处理了可能的特殊情况后，只取到之间的奇数个循环变量进行判断。通过这种方式，时间复杂度可以减半，变成。
此外，为了减少长度，我们直接使用2.4算法中的算法优化组合，而不是从头开始逐步优化。
3.2.1算法
给定两个正整数，，找到它们之间的素数列，即
首先，找到所有小于或等于该列的素数，然后取出到之间的素数。
查找所有小于或等于的素数列的算法取自算法2.4.1
3.2.2代码
3.2.3算法复杂度
很容易知道外环的时间复杂度是；在内层，遍历素列集的时间复杂度为，因此总时间复杂度是。
得到一个空间复杂度为的素数列，以及一个介于之间的素数行，空间复杂度是，因此总空间复杂度就是。
时间复杂度
空间复杂性
自从计算机诞生以来，就有可能计算出非常大的素数。已知的最大素数是一万位。通过计算大素数，超大素数可以用来测试许多关于素数的问题。
我们如何计算大素数 我将在这里做相反的事情。我们做了一些，然后我们做了些，然后我们得到了我们想要的任何数字。这太模糊了。让我给你举个例子。
首先，我们得到素数来构成初始素数列。我们取这些素数中最大的一个，也就是说，我们知道，然后我们可以得到大于和小于的奇数列。我们确定序列中不可被初始素数序列整除的数，得到序列。我们将初始素数列与新素数列组合，得到小于的素数列。
让我们做第二个循环。我们有初始的素数列。取最大素数，即我们知道，然后我们可以得到大于和小于的奇数列。我们确定序列中不可被已知初始素数序列整除的数，并获得序列。我们将初始素数列与新素数列组合，得到小于的素数列。
让我们做第三个循环。我们有初始的素数列。取最大素数，即我们知道，然后我们可以得到大于和小于的奇数列。我们确定序列中不可被已知初始素数序列整除的数，并获得序列。我们将初始素数列与新素数列组合，得到小于的素数列。
等等
我们可以这样做，我们可以继续这样做，并且我们可以得到任何大的素数。
4.4.1算法
从计算大素数开始，重复以下步骤。
设为初始素数的完整数组。我们取其中最大的奇数素数，也就是说，我们可以得到大于和小于的奇数列。我们确定序列中不可被初始素数序列整除的数，得到序列。我们将初始素列与新获得的素列组合，以获得小于的素列。
4.1.2代码
4.1.3算法复杂度
时间复杂度
空间复杂性
注意：虽然算法的复杂度没有改变，但递归方法的执行时间仍然比循环方法慢得多。我认为这可能与递归的高成本有很大关系。
1g
发表评论