The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [sieve-of-eratosthenes]

The Sieve of Eratosthenes is a prime-finding algorithm developed by the ancient Greek mathematician Eratosthenes. It works by writing down as many numbers as needed and then, traversing from lowest to highest, cross out all multiples of a number, beginning with 2. The numbers that remain are considered prime and the lowest of it will be used for the next run.

Filter by
Sorted by
Tagged with
23
votes
4answers
7k views

Sieve of Eratosthenes - Python

I've been doing a lot of Project Euler lately and just wanted to make sure my implementation was as good as it could be. Does anyone have any suggestions to speed this up? ...
14
votes
3answers
618 views

Sieve31, my sieve of Eratosthenes returning IEnumerable<int>

This very fast, simple sieve quickly finds 31 bit primes. It uses a memory efficient BitArray for odd numbers. How a 32 bit int...
18
votes
1answer
1k views

Compile-time sieve of Eratosthenes

There are many instances of prime number sieve implementation both here and other places on the web, but I wanted something a little different. In particular, I wanted to create a static array of the ...
6
votes
0answers
376 views

Sieve32FastV2 - A fast parallel Sieve of Eratosthenes

I’ve created a much cleaner, better designed version to my parallel sieve. I’ve implemented most of EBrown’s micro-optimizations but also revamped the code on my own (that is not in direct response ...
3
votes
1answer
213 views

Sieve32, a simple 32 bit sieve returning IEnumerable<uint> using C#

What a difference 1 bit makes! This very fast, simple sieve of Eratosthenes quickly finds 32 bit primes. It uses a memory efficient BitArray for odd numbers – but ...
3
votes
4answers
2k views

Sieve of Eratosthenes: making it quicker

I was thinking about doing problem 23 of Project Euler. It includes the difficulty where you have to factorize primes. I had already done that in problems I solved earlier, but it was only necessary ...
8
votes
5answers
8k views

Sieve of Eratosthenes optimization

I have applied some optimizations like storing only odd values and starting to mark off from square of the number. Can it be optimized further? ...
14
votes
3answers
1k views

Prime Sieve and brute force

Got caught up with this morning's C++ question. So I thought I would have a go. SO here is my attempt at printing the first 1001 primes. ...
8
votes
1answer
1k views

Prime Number Generator in Swift

I would like to make (or improve my function) a function that returns an array of integers containing all the prime numbers from 2...n that can execute as quickly ...
15
votes
3answers
924 views

Wheel based unbounded sieve of Eratosthenes in Python

Answering this SO question recently, I've developed the following code (based on a well-known Active Code recipe, as discussed here): ...
12
votes
7answers
9k views

Sieve of Eratosthenes

For practice, I've implemented Sieve of Eratosthenes in Java by thinking about this visual animation. I would like to hear some suggestions for improvements, especially how to make it more efficient ...
11
votes
2answers
853 views

Sieve of Eratosthenes - segmented to increase speed and range

A lot of the sieve code floating around here and on the 'net is sloppy or broken; in fact, I've yet to see a single one that is correct, clean (in the sense of avoiding superfluous iterations etc.) ...
11
votes
2answers
126 views

Segmented wheel Sieve of Eratosthenes in Python

Here is a new version of a segmented and wheel factorized Sieve of Eratosthenes. It currently uses mod 30 wheel factorization to eliminate multiples of 2, 3, and 5 in the sieve data structure to gain ...
2
votes
1answer
722 views

Unbounded Sieve of Eratosthenes in Swift

I've spent a while teaching myself Swift, and decided to take on the challenge of writing an unbounded Sieve of Eratosthenes to challenge myself. This is actually the first time I've written an ...
9
votes
1answer
933 views

Sieve32Fast - A very fast, memory efficient, multi-threaded Sieve of Eratosthenes

An improved version Sieve32FastV2 is available. The classical solutions for the Sieve of Eratosthenes fall into 2 camps: one uses a bool[], which is fast but very ...
8
votes
2answers
955 views

Sieve of Eratosthenes implementation is running slowly

I have written this code to find prime numbers, and it works well, but the calculation speeds are incredibly slow. Am I doing this wrong? I know that I might be really doing this the wrong way, but ...
8
votes
1answer
128 views

Segmented and wheel factorized prime generator in Python

I recently discovered that it is much faster to generate primes using a Sieve of Eratosthenes (SoE) with a boolean array data structure than with a heap. Since then I have been looking for fast and ...
6
votes
1answer
486 views

Project Euler #10 in Swift - Summation of primes

I just finished Project Euler #10 in Swift, and since there is not any version yet on Code Review, I would like to have some comments on what I did to try to improve it. I hope I learned some from ...
6
votes
4answers
1k views

Threshing: Sieve of Eratosthenes

I would like a complete threshing of this code so that I can see what I did wrong and what I am using incorrectly. I made this super simple, trying to learn a little bit about ...
5
votes
3answers
845 views

Project Euler Problem #10

I've read other solutions about solving the 10th problem for Project Euler (finding the sum of all prime numbers under 2,000,000) but I wanted to try it on my own using the Sieve of Eratosthenes ...
4
votes
2answers
112 views

Incremental Sieve of Eratosthenes using iterators

I am in the process of learning Rust and am still having some issues with borrowing and ownership. I find myself trying to borrow mutable references that are already borrowed as immutable references ...
28
votes
4answers
2k views

Extending Sieve of Eratosthenes beyond a billion

For MAX value of 1000000000 (\$10^9\$), it takes about 45 seconds to reach the line where it prints "done". How can I speed this ...
38
votes
5answers
5k views

Parallel sieve of Eratosthenes

For the first time, I tried to use threads by myself in order to implement a parallel sieve of Eratosthenes. The trick is that each time a prime is found, a thread is spawned to eliminate all the ...
11
votes
5answers
3k views

Prime Number Sieving Algorithm

Last semester in my Masters Program I developed this code for sieving. My professor wants me to write a report that he might use locally within the school, but I feel like I've done nothing that new, ...
11
votes
3answers
1k views

Parallel sieve of Eratosthenes, version 2

This question is a revision of Parallel sieve of Eratosthenes. The goal is to implement a sieve of Eratosthenes with parallel strikes out from the boolean array. I tried to fix the data races and all ...
9
votes
3answers
3k views

Sieve of Eratosthenes in Java

Here you can find my implementation of sieve of Eratosthenes in Java. ...
7
votes
2answers
119 views

Prime number segmented sieve

I tried to solve the SPOJ prime number problem below. The code produced correct results, but Time limit exceeded and also memory need around 970M which is not efficient(?) How can I optimize this ...
6
votes
1answer
285 views

Sieve of Eratosthenes for prime generation

I was originally going to write this intro as just being the bare-bones "here's my problem, here are some ideas, what do you recommend" format (which I am still going to follow, mind you), but I've ...
5
votes
3answers
195 views

Snakes on a prime

The challenge is to find and print the largest palindrome prime under 1000. ...
5
votes
1answer
3k views

Sieve of Eratosthenes in Python 3

Currently, the code will generate a range of natural numbers from 1 to N and store it in a list. Then the program will iterate through that list, marking each multiple of a prime as 0 and storing each ...
4
votes
3answers
962 views

Sieve of Eratosthenes in C#

Just because I've never written a real Sieve of Eratosthenes, I decided I should probably write one just to make sure I know what it is. I'd like (constructive) criticism on best practices, potential ...
11
votes
4answers
396 views

Threshed and Malachi'd: Sieve of Eratosthenes

I took a little bit from all the answers to my previous question Threshing: Sieve of Eratosthenes. This may be bordering on code-golfing, but I think that I have a pretty good piece of code here. Is ...
7
votes
5answers
969 views

Project Euler #35 - Circular primes solution is slow

This is my code for project euler #35 (in Python): The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime. There are thirteen ...
7
votes
1answer
419 views

The rusty Sieve of Eratosthenes

To get familiar with the Rust language I've decided to implement the method of Sieve of Eratosthenes to find primes up to a number N. I have created the following code that both prints the prime ...
7
votes
1answer
459 views

Prime Numbers Store

Let's say we need to create a store for selling prime numbers. Users enter the store and ask to buy a number. If the number asked is a prime number, 1.1. then it's either available for sale 1.2. ...
6
votes
1answer
345 views

Prime Number Generator Time Limit Exceeded

PRIME1- Prime Generator The code is working fine and it's generating a prime number from M to N but the only problem is I'm getting TLE when I submit my answer. How do I optimise my code to pass the ...
6
votes
1answer
86 views

Object oriented, runtime expandable Sieve of Eratosthenes

In answering this question, it seemed to me that it would be nice to have a runtime expandable Sieve of Eratosthenes. This is my implementation of that notion. Design I've created a class named <...
5
votes
3answers
405 views

Implementation of Sieve of Eratosthenes algorithm

I have made an implementation of Sieve of Eratosthenes algorithm in Java, and am not certain that it is as efficient as possible. I have looked at other peoples implementations on Google, and on this ...
5
votes
1answer
834 views

Find the 10001st prime number (in C++)

I wrote this solution for project Euler #7, to find the 10001th prime number using sieve of eratosthenes. It's really slow though. Any suggestions to improve performance (without using more complex ...
5
votes
1answer
58 views

Prime Sieve and brute force #2

Based on my previous attempt. Prime Sieve and brute force Trying to make the interface simpler I have moved all the code into a class. This way I can keep track of the ...
5
votes
0answers
96 views

Multiple rusty Sieves of Eratosthenes

To get more familiar with the multi-threading aspects in the Rust language I decided to multi-thread my earlier implementation of The rusty Sieve of Eratosthenes. I have to say that it is probably in ...
5
votes
2answers
241 views

Reduce Prime Sieve Memory Consumption 2

I've made a prime number generator (for Project Euler). It uses Euler's Sieve (a modified Sieve of Eratosthenes), with a mod 30 step. I'd like to reduce the memory consumption to 4/15 what it ...
4
votes
2answers
1k views

Get nth prime number using sieve of Eratosthenes

I am tasked with being able to find the \$n\$th prime number. I've tried to implement something like the sieve of Eratosthenes in increments of 200. The code works and returns the \$n\$th prime number....
3
votes
3answers
175 views
3
votes
1answer
421 views

Initialize a Sieve of Eratosthenes in Scala

I am learning Scala while solving some exercises and I am currently solving an exercise where I need to initialize a Sieve of Eratosthenes. I am using the following code: ...
3
votes
2answers
77 views

Number Theory Inhibitor Calculator

I've been working on generating primes and prime products quickly to aid me in my research on prime numbers, their density, etc. The answer to my Large Number Limit Extravaganza question proved to be ...
1
vote
1answer
415 views

Sieve of Eratosthenes in Haskell

I've implemented the Sieve of Eratosthenes algorithm in Haskell. Please take a look. Any suggestions are greatly appreciated :) ...
1
vote
0answers
54 views

Incremental Sieve of Eratosthenes using unstable generators [duplicate]

I am in the process of learning Rust and am still having some issues with borrowing and ownership. I find myself trying to borrow mutable references that are already borrowed as immutable references ...
0
votes
1answer
167 views

Fast Prime Sieve (Python Implementation)

A modified version of the prime sieve. I actually doubt it could be implemented any faster, but I might be wrong: ...
-1
votes
1answer
739 views

Prime sieve implementation (using trial division) in C++

How can I optimize this? ...