标签: primes

作为圣诞礼物,我用Java编写了一个小程序来计算素数.我的目的是让它彻夜不眠,计算下一个素数并将其写入.txt文件.早上我会杀了这个程序并将.txt文件带给我的朋友过圣诞节.

有什么我应该担心的吗？请记住,这是真正的初学者Ziggy,你正在谈论,而不是一些聪明的错误检查ASM的家伙.

编辑更具体地说,因为我将在整夜计算素数时离开这个程序,有没有机会我会遇到某种与内存相关的错误？喜欢,堆叠压碎堆或狗和猫睡在一起？

EDIT更具体地说,当文件大小为4GB时,是否有一行代码可以用来停止打印行？为了安全起见？

编辑:成功:整夜离开之后,我得到的素数不超过13 KB,我得到的最高值是22947217,就像成千上万的素数一样.成功!

作为我自己的练习,我正在实施Miller-Rabin测试.(通过SICP工作).我理解费马的小定理并且能够成功地实现它.我在米勒 - 拉宾测试中被绊倒的部分是这个"1 mod n"业务.是不是1 mod n(n是一些随机整数)总是1？所以我很困惑"1模数n的非平方根"可能是什么,因为在我看来"1 mod n"在处理整数值时总是1.我错过了什么？

我一直在努力学习生成素数的算法,我在维基百科上遇到了阿特金的Sieve.我理解算法的几乎所有部分,除了少数几个.以下是问题:

1. 下面的三个二次方程如何形成？4x ^ 2 + y ^ 2,3x ^ 2 + y ^ 2和3x ^ 2-y2
2. 维基百科中的算法讨论模数为60但我不明白在下面的psudocode中使用的方式/位置.
3. 如何找到这些提醒1,5,7和11？

以下是维基百科的伪代码供参考:

// arbitrary search limit                                                   
limit ? 1000000                                                             

// initialize the sieve                                                     
for i in [5, limit]: is_prime(i) ? false                                    

// put in candidate primes:                                                 
// integers which have an odd number of                                     
// representations by certain quadratic forms                               
for (x, y) in [1, ?limit] × [1, ?limit]:                                    
    n ? 4x²+y²                                                              
    if (n ? limit) and (n mod 12 = 1 or …

来自Project Euler的问题10 是找到给定n下面所有素数的总和.

我只是通过总结Eratosthenes筛子产生的素数来解决它.然后我通过Lucy_Hedgehog(次线性!)找到了更有效的解决方案.

对于n =2⋅10^ 9:

• Python代码(来自上面的引用)在Python 2.7.3中运行1.2秒.

• C++代码(我的)在大约0.3秒内运行(用g ++ 4.8.4编译).

我在Haskell中重新实现了相同的算法,因为我正在学习它:

import Data.List

import Data.Map (Map, (!))
import qualified Data.Map as Map

problem10 :: Integer -> Integer
problem10 n = (sieve (Map.fromList [(i, i * (i + 1) `div` 2 - 1) | i <- vs]) 2 r vs) ! n
              where vs = [n `div` i | i <- [1..r]] ++ reverse [1..n …

我正在尝试生成低于10亿的素数列表.我正在尝试这个,但这种结构非常糟糕.有什么建议？

a <- 1:1000000000
d <- 0
b <- for (i in a) {for (j in 1:i) {if (i %% j !=0) {d <- c(d,i)}}}

为了帮助我学习Haskell,我正在研究Project Euler的问题.在解决了每个问题之后,我会针对Haskell wiki检查我的解决方案,以尝试学习更好的编码实践.下面是解决到问题3:

primes = 2 : filter ((==1) . length . primeFactors) [3,5..]

primeFactors n = factor n primes
  where
    factor n (p:ps) 
        | p*p > n        = [n]
        | n `mod` p == 0 = p : factor (n `div` p) (p:ps)
        | otherwise      = factor n ps

problem_3 = last (primeFactors 317584931803)

我对此的天真解读是根据primes定义primeFactors来定义的primes.所以评估primeFactors 9将遵循这个过程:

1. 评估factor 9 primes.
2. 要求primes它的第一个元素,即2.
3. 要求primes它的下一个元素. …

我一直在尝试用JavaScript 编写Sieve of Eratosthenes算法.基本上我只是遵循以下步骤:

1. 创建从2到(n-1)的连续整数列表
2. 设第一个素数p等于2
3. 从p开始,以p为增量计数并删除每个数字(p和p的倍数)
4. 转到列表中的下一个数字并重复2,3,4
5. 将无意删除的素数添加回列表

这就是我想出的:

function eratosthenes(n){
var array = [];
var tmpArray = []; // for containing unintentionally deleted elements like 2,3,5,7,...
var maxPrimeFactor = 0;
var upperLimit = Math.sqrt(n);
var output = [];

// Eratosthenes algorithm to find all primes under n

// Make an array from 2 to (n - 1)
//used as a base array to delete composite number from
for(var i = 2; i < n; i++){
    array.push(i); …

你能否建议一种在实践中可用的快速,确定性的方法,用于测试大数是否为素数？

另外,我想知道如何正确使用非确定性素性测试.例如,如果我使用这样的方法,如果输出为"no",我可以确定数字不是素数,但是当输出"可能"时,另一种情况呢？在这种情况下,我是否必须手动测试素数？

提前致谢.

我正在为Diffie-Hellman类型密钥生成2048位安全素数,p使得p和(p-1)/ 2都是素数.

我可以在p和(p-1)/ 2上使用几次Rabin-Miller迭代,并且仍然对加密密钥有信心吗？在我做过的研究中,我已经听到了1024位普通素数的6到64次迭代的所有内容,所以我在这一点上有点困惑.一旦确定,如果您正在生成一个安全的素数而不是普通素数,那么数字是否会改变？

计算时间非常宝贵,所以这是一个实际的问题 - 我基本上想知道如何找到尽可能少的测试数量,同时保持非常有保障的安全性.

我一直在测试竞争性编程的水域,我已经看过很多次提到的这个陈述:

打印结果模10 ⁹ + 7

现在我可以弄清楚这是一种在处理非常大的数字时防止数字溢出的方法.但它是如何以及为什么有效？如果有人能解释这背后的数学推理,我将不胜感激.