如果您已经对数字进行了素数分解,那么获得该数字的所有因子的最简单方法是什么？我知道我可以从2循环到sqrt(n)并找到所有可分的数字,但这似乎效率低,因为我们已经有了素数分解.
我想它基本上是组合/选择功能的修改版本,但我似乎找到的只是计算组合数量的方法,以及计算因子数量的方法,而不是实际生成组合/因子.
注意:下面的版本2使用了Eratosthenes的Sieve.有几个答案有助于我最初的问题.我选择了Eratosthenes筛选方法,实现了它,并适当地更改了问题标题和标签.感谢所有帮助过的人!
我写了这个花哨的小方法,它生成一个int数组,其中包含小于指定上限的素数.它工作得很好,但我有一个担忧.
private static int [] generatePrimes(int max) {
int [] temp = new int [max];
temp [0] = 2;
int index = 1;
int prime = 1;
boolean isPrime = false;
while((prime += 2) <= max) {
isPrime = true;
for(int i = 0; i < index; i++) {
if(prime % temp [i] == 0) {
isPrime = false;
break;
}
}
if(isPrime) {
temp [index++] = prime;
}
}
int [] primes = new int …对于库,我需要将第一个素数存储到极限L.此集合必须具有O(1)查找时间(以检查数字是否为素数)并且必须很容易,给定数字,找到下一个素数(假设它小于L).
鉴于L是固定的,生成清单的Eratostene筛子很好.现在,我使用一个打包的布尔数组来存储列表,该列表仅包含3到L(含)之间的奇数的条目.这需要(L-2)/ 2位内存.我希望能够在不使用更多内存的情况下静态增加L.
是否存在使用具有相似属性的较少内存的数据结构？或者至少具有恒定的查找时间？(然后可以枚举奇数,直到我们得到一个素数)
(我在其中编写的语言是因子,但这个问题在内置或易于编程的打包位数组的任何语言中都是相同的)
我正在做一个项目,我需要一种有效的方法来计算素数.我使用了Eratosthenes的筛子,但是我一直在寻找并发现Atkin的筛子是一种更有效的方法.我发现很难找到这种方法的解释(我能够理解!).它是如何工作的？示例代码(最好是在C或python中)很棒.
编辑:感谢您的帮助,我唯一不理解的是x和y变量在伪代码中引用的内容.有人可以帮我解释一下吗？
使用Miller-Rabin测试的概率版本,我生成了一个中大(200-300位)可能素数的列表.但可能还不够好!我需要知道这些数字是素数.是否有一个库 - 最好是在Python中包装或包装 - 实现了一种更有效的素性证明算法？
或者,有没有人知道我在哪里可以找到一个清晰,详细,完整的ECPP(或类似的快速算法)描述,它不会假设大量的先验知识？
更新:我发现另一个测试APRT-CLE 的Java实现,最终证明了primality.它在原子处理器上用不到10分钟的时间验证了291位数的候选人.仍然希望更快的东西,但这似乎是一个充满希望的开始.
我正在编写一个加密协议的实现.到目前为止,我一直很难找到1024位到4096位整数(308到1233位数字)的最快确定性素性测试.我知道几个选项,但我无法找到真实世界的速度比较.
具体来说,AKS测试与Rabin-Miller的确定性版本和Elliptic Curve Primality Proving测试(以及其他)相比,这个大小的一般随机数如何？
我正在努力学习Python编程,我对此很陌生.
我在打印一系列素数从一到百时遇到了问题.我无法弄清楚我的代码是什么问题.
这是我写的; 它打印所有奇数而不是素数:
for num in range(1,101):
for i in range(2,num):
if (num%i==0):
break
else:
print(num)
break
我正在尝试解决C#中最大的主要编程实践问题.问题很简单,打印出或写入文件号:2 58,885,161 - 1(其中有17,425,170位)
我已经设法使用神奇的GNU多精度算术库通过Emil Stevanof .Net包装器来解决它
var num = BigInt.Power(2, 57885161) - 1;
File.WriteAllText("biggestPrime.txt", num.ToString());
即使所有当前发布的解决方案都使用此库,对我来说也感觉像是作弊.有没有办法在托管代码中解决这个问题？想法？建议？
PS:我已经尝试过使用.Net 4.0 BigInteger,但它永远不会结束计算(我等了5分钟,但与GMP解决方案的50秒相比已经很多了).
我们知道可以使用以下方法生成3以上的所有素数:
6 * k + 1
6 * k - 1
但是,我们从上面的公式生成的所有数字都不是素数.
For Example:
6 * 6 - 1 = 35 which is clearly divisible by 5.
为了消除这些条件,我使用Sieve方法并删除了数字,这些数字是从上面公式生成的数字的因子.
使用事实:
如果没有素数因素,那么一个数字被称为素数.
生成低于1000的素数.
ArrayList<Integer> primes = new ArrayList<>();
primes.add(2);//explicitly add
primes.add(3);//2 and 3
int n = 1000;
for (int i = 1; i <= (n / 6) ; i++) {
//get all the numbers which can be generated by the formula
int prod6k = 6 * i;
primes.add(prod6k - 1); …我无法理解这段代码:
let
sieve (p:xs) = p : sieve (filter (\ x -> x `mod` p /= 0) xs)
in sieve [2 .. ]
有人可以为我分手吗？我知道它有递归,但这就是问题我无法理解这个例子中的递归是如何工作的.