查找給定範圍內的大素數（〜8000位）

我在java中編寫代碼來查找素數，但找到下一個我需要使用此質數的8761數字[P]（使用此找到的代碼）和另一個在給定範圍內小於P的素數，現在我正在尋找250萬個距離內的素數。查找給定範圍內的大素數（〜8000位）

問題是找到此範圍內的所有素數。使用我從125M（奇數）到600萬可能的素數之前得到的速度減慢之前，有一個erasthostenes篩。但是，這是我得到的。

由於BigInteger的.isPrime（1）需要3分鐘的每個號碼，我會讓孩子在大學時，我完成了這一點。

在我的代碼中，我使用P和PRP之間的距離來避免使用bigIntegers。另外我將它存儲在我讀取和寫入的.txt文件中。這裏是我的代碼的一小部分：

//Stores PRPs to List<Long> Erros = new ArrayList(); 

BigInteger Primo = new BigInteger("1"); 

while (Primo.longValueExact() <= Max){ 

     while(Erros_Eliminados.size() < 200000){ 

      Primo = Primo.nextProbablePrime(); 
      BigInteger R1 = BPrimo_Dado.mod(Primo); //[BPrimo_Dado = P = 8761 Digits number] 

      long R = R1.longValue(); 

      while(R <= Max){ //Max = 250000000 

       if(R >= Min){ //Min = 0 

        Erros_Eliminados.add(R); 

       } 

       R += Primo.longValue(); 

      } 

     } 

     ... 
     //removes the ErrosEliminados from Erros List and save it again to .txt 

}

**我也使用250M和1億美元之間的素數同類者代碼，並大於1億美元（從bitlist讀），還有一些細微的變化......

所以問題是：找到那些大素數的最快方法是什麼？有更好的方法，而不是篩子？我是開放的任何東西...

PS：這是我的第一個問題，並給予我的問題有點怪異有很高的機會，我打破了一些行爲規則，如模糊或類似的東西，所以原諒我，如果是這種情況，請告訴我可以修理任何東西。

來源

2016-11-19 BarriaKarl

歡迎來到StackOverflow！在等待時，隨時閱讀一些問題提示。 http://stackoverflow.com/help/asking。如果您認爲缺少某些東西，請隨時[編輯] –

我可能會誤解您的代碼，但不應該在BigInteger R1 = BPrimo_Dado.mod（Primo）;是BigInteger R1 = Primo.subtract（BPrimo_Dado.mod （Primo））;'？ – SpiderPig

你爲什麼這樣做？這聽起來像是一個X-Y問題。 – erickson

BigInteger類可以爲您生成大素數：BigInteger.probablePrime()也可以找到下一個素數：BigInteger.nextProbablePrime()。

來源

2016-11-19 16:39:23 rossum

是的，但對於這個尺寸的素數來說太長了。我測試了它，但我放棄之前甚至無法得到結果... – BarriaKarl

我懷疑你可以寫更快的代碼。大數字的測試可能會很慢，這就是爲什麼使用Miller-Rabin等方法的原因。 – rossum

@BarriaKarl：看看'BigInteger.nextProbablePrime（）'的源代碼。它做了eratosthenes篩選，然後是米勒 - 拉賓。如果你能在Java中做得更好，那麼Oracle希望擁有你的代碼。 –

查找給定範圍內的大素數（〜8000位）

回答

相關問題