mersenneforum.org Generating Small Primes
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2005-01-05, 05:16 #1 wblipp     "William" May 2003 New Haven 94316 Posts Generating Small Primes What's the fastest way to generate small primes? Crandall & Pomerance give a "Fancy Erotosthenes Sieve" in Algorithm 3.2.2 that is O(N / ln ln N). At about the same time Atkin and Bernstein published their sieve with binary quadratic forms that has the same asymptotic density. Has experience yet shown one to be better in practice? Calculating these and saving the results in a compressed bit map must be a common function. Has somebody optimized this and made source code available, or does everybody recreate this for themselves?
 2005-01-05, 07:00 #2 leifbk     May 2004 Oslo, Norway 23·3·5 Posts Don't know if you've seen "Fun with Prime Numbers" or even find it useful ... regards, Leif.
 2005-01-05, 13:29 #3 Mystwalker     Jul 2004 Potsdam, Germany 14778 Posts Primegen (comes as source) uses the Sieve of Atkin and seems to do fine - I don't know about the Big O, though...

 Similar Threads Thread Thread Starter Forum Replies Last Post mickfrancis Factoring 2 2016-05-06 08:13 kar_bon Riesel Prime Data Collecting (k*2^n-1) 3 2013-05-11 04:56 davar55 Math 14 2011-02-20 16:06 Housemouse Math 2 2008-06-04 05:23 ValerieVonck Octoproth Search 100 2007-02-16 23:43

All times are UTC. The time now is 00:36.

Tue May 17 00:36:23 UTC 2022 up 32 days, 22:37, 0 users, load averages: 1.55, 1.49, 1.41

Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔