Stack Overflow
Stack Overflow

Questions tagged [sieve-of-eratosthenes]

Sieve of Eratosthenes is a simple, ancient algorithm for finding all prime numbers up to a specified integer.

Sieve of Eratosthenes finds primes among the natural numbers above 1 between the composites, which it finds by direct enumeration from each prime (optimization: prime's square), as an arithmetic progression with the step equal to that prime.

The first prime number is 2.

In pseudocode, the timing issues aside, it is

primes = [2, 3, ...] \ [[p*p, p*p+p, ...] for p in primes]

469 questions
107
votes
5 answers

Time complexity of Sieve of Eratosthenes algorithm

From Wikipedia: The complexity of the algorithm is O(n(logn)(loglogn)) bit operations. How do you arrive at that? That the complexity includes the loglogn term tells me that there is a sqrt(n) somewhere. Suppose I am running…
Lazer
  • 90,700
  • 113
  • 281
  • 364
85
votes
24 answers

Sieve of Eratosthenes - Finding Primes Python

Just to clarify, this is not a homework problem :) I wanted to find primes for a math application I am building & came across Sieve of Eratosthenes approach. I have written an implementation of it in Python. But it's terribly slow. For say, if I…
Srikar Appalaraju
  • 71,928
  • 54
  • 216
  • 264
44
votes
11 answers

Speed up bitstring/bit operations in Python?

I wrote a prime number generator using Sieve of Eratosthenes and Python 3.1. The code runs correctly and gracefully at 0.32 seconds on ideone.com to generate prime numbers up to 1,000,000. # from bitstring import BitString def…
Xavier Ho
  • 17,011
  • 9
  • 48
  • 52
41
votes
6 answers

Segmented Sieve of Eratosthenes?

It's easy enough to make a simple sieve: for (int i=2; i<=N; i++){ if (sieve[i]==0){ cout << i << " is prime" << endl; for (int j = i; j<=N; j+=i){ sieve[j]=1; } } cout << i << " has " << sieve[i] << "…
John Smith
  • 11,678
  • 17
  • 46
  • 51
37
votes
16 answers

The sieve of Eratosthenes in F#

I am interested in an implementation of the sieve of eratosthenes in purely functional F#. I am interested in an implementation of the actual sieve, not the naive functional implementation that isn't really the sieve, so not something like this: let…
IVlad
  • 43,099
  • 13
  • 111
  • 179
33
votes
28 answers

Program to find prime numbers

I want to find the prime number between 0 and a long variable but I am not able to get any output. The program is using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ConsoleApplication16 { class…
sandy101
  • 3,395
  • 3
  • 23
  • 19
25
votes
8 answers

Sieve of Eratosthenes algorithm in JavaScript running endless for large number

I have been trying to write Sieve of Eratosthenes algorithm in JavaScript. Basically I just literally followed the steps below: Create a list of consecutive integers from 2 to (n-1) Let first prime number p equal 2 Starting from p, count up in…
Bao
  • 617
  • 2
  • 10
  • 17
22
votes
13 answers

Finding prime numbers with the Sieve of Eratosthenes (Originally: Is there a better way to prepare this array?)

Note: Version 2, below, uses the Sieve of Eratosthenes. There are several answers that helped with what I originally asked. I have chosen the Sieve of Eratosthenes method, implemented it, and changed the question title and tags appropriately. …
eleven81
  • 6,301
  • 11
  • 37
  • 48
22
votes
5 answers

Sieve of Atkin explanation

I am doing a project at the moment and I need an efficient method for calculating prime numbers. I have used the sieve of Eratosthenes but, I have been searching around and have found that the sieve of Atkin is a more efficient method. I have found…
marc lincoln
  • 1,551
  • 4
  • 21
  • 25
17
votes
12 answers

Sieve of Eratosthenes in Erlang

I'm in the process of learning Erlang. As an exercise I picked up the Sieve of Eratosthenes algorithm of generating prime numbers. Here is my code: -module(seed2). -export([get/1]). get(N) -> WorkList = lists:duplicate(N, empty), get(2,…
Roskoto
  • 1,722
  • 1
  • 16
  • 27
15
votes
5 answers

Sieve of Eratosthenes in Ruby

Rather than scraping a Ruby version of this algorithm off the net I wanted to create my own based on its description here. However I cannot figure out two things def primeSieve(n) primes = Array.new for i in 0..n-2 primes[i] = i+2 end …
Damian
  • 663
  • 1
  • 9
  • 12
12
votes
1 answer

Clojure: Avoiding stack overflow in Sieve of Erathosthene?

Here's my implementation of Sieve of Erathosthene in Clojure (based on SICP lesson on streams): (defn nats-from [n] (iterate inc n)) (defn divide? [p q] (zero? (rem q p))) (defn sieve [stream] (lazy-seq (cons (first stream) …
nixx
  • 121
  • 2
12
votes
1 answer

double stream feed to prevent unneeded memoization?

I'm new to Haskell and I'm trying to implement Euler's Sieve in stream processing style. When I checked the Haskell Wiki page about prime numbers, I found some mysterious optimization technique for streams. In 3.8 Linear merging of that…
FooBee
  • 778
  • 7
  • 23
10
votes
2 answers

Understanding the Limitations of Lazy Evaluation (Sieve of Eratosthenes)

In the Haskell Wiki article on prime numbers, the following implementation of the Sieve of Eratosthenes is described: primes = 2 : 3 : minus [5,7..] (unionAll [[p*p, p*p+2*p..] | p <- tail primes]) When doing... primes !! 2 ... how does Haskell…
Wilson
  • 203
  • 2
  • 4
10
votes
5 answers

Better algorithm - Next semiprime

Given n, find m such that m is the smallest semiprime greater than n. Next prime is pretty straightforward, semiprime is less so. To be clear, only the semiprime is needed, though getting the factors at the same time would be convenient. I've…
user4159038
1
2 3
…
31 32