# 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.

187 questions
Filter by
Sorted by
Tagged with
675 views

### Performance of Haskell prime sieve

I have this code, which is a pseudo-Sieve of Eratosthenes for generating primes: ...
• 173
2k views

### Sieve of Eratosthenes in C++ with wheel factorization

I have written a completely working C++ program for the first time, and I have managed to compile it. I have decided to learn C++ and I have written a C++ program to familiarize myself with C++, this ...
• 3,014
107 views

### Image generator using prime numbers in polar coordinates

Related This is a Python script that generates images using prime numbers up to a given positive integer, it generates prime numbers using the Sieve of Eratosthenes with some rudimentary Wheel ...
• 3,014
109 views

### Prime sieve in Rust

Using Sieve of Eratosthenes, I created a function that returns a vector of primes up to given limit. ...
• 97
282 views

### Prime sieve for large numbers

I state that I am not an expert and that certainly the code can be improved. I made this prime number sieve to be able to handle large numbers. The basic idea is to write a number p=r+bW*k where r is ...
• 153
691 views

### Next level Improved Sieve of Eratosthenes

This is the next development for the Sieve of Eratosthenes algorithm, where all the multiples of 2,3 and 5 are eliminated, which will not take any memory or time. As my last question Improved Sieve of ...
• 119
4k views

### Improved Sieve of Eratosthenes

How can I get to a perfect coding for this algorithm? I made the mathematical theorem, which is a development of the Sieve of Eratosthenes algorithm. I might use some help in coding. You can find the ...
• 119
291 views

### Counting primes less than n in Python

I implemented (a refinement of) the Sieve of Eratosthenes for counting primes less than a given number n. This is a coding exercise from LeetCode. The class Solution...
453 views

### Sieve of Eratosthenes in x86 assembly

Hello I made a sieve of Eratosthenes algorithm on x86 assembly using NASM. The highest number it can take is about 2 million and it takes like 2 seconds to complete. Here's the code: ...
1k views

### the 10001st prime number

Problem description: By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13. What is the 10001st prime number? Prime number: A prime number is a whole ...
130 views

### Sieve of Atkin C#

I don't fully understand how to make the Sieve of Atkin faster than the most ancient sieve. All implementations I found online where slower than the one I made, but still It isn't faster than ...
155 views

### Sieve of Eratosthenes in F#

after looking at the pseudocode for the Sieve of Eratosthenes on wikipedia I tried implementing a similar version using F#. The code runs just fine, that is, it returns all prime numbers up until a ...
190 views

### Segmented Sieve of Eratosthenes with wheel factorisation

Problem I have a project in which I implemented variants of the Sieve of Eratosthenes as well as benchmarking and profiling harnesses for these (which can be ran with ...
• 259
108 views

...
785 views

### Implementation of Sieve of Eratosthenes in Java

I have implemented Sieve of Eratosthenes in Java as follows. Is there a way I can modify the below code to make it more efficient? The current execution time is 0.8481224 seconds ...
692 views

### Comparing 2 distinct sieve of Eratosthenes algorithms in Java

In this post, I will present and compare two distinct algorithms for sieve of Eratosthenes: com.github.coderodde.math.prime.PrimeFinder ...
• 27k
330 views

### Sieve of Eratosthenes in Vyxal

I'm trying to learn the golfing language Vyxal because I occasionally contribute to it, and I'm slightly ashamed I can't even use it. To do this, I started with implementing the Sieve of Eratosthenes ...
• 499
265 views

### Optimize Sieve of Eratosthenes for big numbers in Python

I'm solving Euler exercise number 7 and trying to go a bit further on bigger primes. It is too slow with big numbers. I've been reading ways to optimize the sieve, but I would like to ask people with ...
183 views

### Sieve of eratosthenes: My optimized version

I wrote a simple prime number program that checks if a number is prime or not using sieve of eratosthenes, I also wrote an optimized version that only generates the ...
• 1,878
5k views

### Why is my Sieve of Eratosthenes using generators so slow

This is my prime sieve based on the Sieve of Eratosthenes. ...
• 329
152 views

### A Sieve of Eratosthenes

I have written this Sieve of Eratosthenes. This is a bit of software that will find all of the prime numbers between 2 and n, where n is a user-defined value. The code does seem quite bloated and any ...
1k views

### Prime sieve generator

I wrote a simple prime sieve in Python. But it ended up looking... ugly. I included a few of the most basic optimizations. When posting this question SE suggested a bunch of questions on the same ...
• 253
112 views

### Sieve of Eratosthenes optimisation

I'm implementing Sieve of Eratosthenes by working with multiples of 30 and comparing it to multiples of 3 from a previous answer code for multiples of 30: ...
• 153
1 vote
136 views

### Zen and the Sieve of Eratosthenes - Part 1: A Basic Windowed Sieve

The Sieve of Eratosthenes is one of the oldest known algorithms and yet it is still the best method for sieving prime numbers in bulk in many situations. It is brutally simple, but to make it brutally ...
• 2,721
219 views

### Further Optimizing a Segmented Sieve of Eratosthenes

I've implemented a Segmented Sieve of Eratosthenes that assumes each segment is about length $\sqrt{N}$ for some upper limit $N$. I further optimized the function by skipping all the evens when ...
• 171
1k views

### Sum of primes under a certain number

I have tried two different methods to find the sum of primes under a certain number. However both of these methods end up taking a very long time for large numbers. How can I optimise either of these ...
• 199
149 views

### Prime Number Table, i.e. List<int>

I have written many variations of the Sieve of Eratosthenses, which is the fastest way to generate a large collection of primes. (@slepic asked for clarification, which I provide in an answer below. ...
• 6,257
1k views

### Project Euler problem 50

I was just trying Project Euler problem 50. The prime 41, can be written as the sum of six consecutive primes: 41 = 2 + 3 + 5 + 7 + 11 + 13 This is the longest sum of consecutive primes that ...
• 2,720
267 views

### Understanding RSA key generation and implementation in Java

Here is an attempt to leverage Java's BigInteger class to implement the RSA algorithm, as well as md5 and sha512 hashing functions to generate keys for what I hope to be strong cryptography. My prayer ...
• 79
1k 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 ...
• 305
518 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 ...
• 305
1 vote
219 views

### Optimizing the Sieve of Eratosthenes for prime generation

I've been on a Project Euler spree and I've been solving problems and as you might know, many of them require you to use prime numbers. I've been using the following code to generate and store primes ...
• 375
496 views

### Incremental Sieve of Eratosthenes Generator

So I was fiddling around with the Euler challenges. One of the things they mentioned in their discussions of the solutions is the Sieve of Eratosthenes and that you can only use it when you know an ...
• 2,909
1k views

### Sum of primes up to 2 million using the Sieve of Eratosthenes

I've solved question 10 on Project Euler using the Sieve of Eratosthenes, what can I do to optimize my code? ...
2k views

### Prime sieve in Python

I was trying to write Sieve for the first time and I came up with this code: ...
• 519
83 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 ...
• 94.3k
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. ...
• 94.3k
2k views

### Implementing Sieve of Eratosthenes faster

I wrote a version of Sieve of Eratosthenes: ...
• 193
259 views

### Efficiency of a recursive implementation of the Sieve of Erasthotenes in Python

I implemented the Sieve of Erasthotenes recursively using filter and I was wondering how efficient this implementation is and wether a non-recursive implementation ...
407 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 ...
• 183
491 views

### Simple Sieve of Eratosthenes in Python 3

So yet another Sieve of Eratosthenes in Python 3. The function returns a list of all primes smaller but not equal max_n. The motivation is, as a practice, a ...
• 195
1k 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,806
212 views

### Computing a prime table in Rust

My objective is computing a table of primes up to n, where n is a natural number passed as an argument to the prime_table function. Here is src/lib.rs: ...
• 227
381 views

### Faster Sieve of Eratosthenes

This is an implementation of the Sieve of Eratosthenes : It takes advantages of the fact that all primes from 5 and above can be written as 6X-1 or ...
• 869
167 views

### Project Euler #10 (sum of primes less than two million) in Clojure

I'm new to Clojure and using some Project Euler problems to familiarize myself with the language's capabilities. Problem #10 asks to find the sum of all primes less than two million. I wanted to ...
• 839
181 views

### Short Eratosthenes Sieve

I've written a short implementation of the Eratosthenes' sieve. ...
2k views

### Sieve of Eratosthenes in Rust

This is a relatively simple implementation of the Sieve of Eratosthenes in Rust. The main objective is to find the $n$th prime quickly when $n$ might grow to huge numbers. ...
• 3,007
217 views

### Prime number generation - SPOJ

This is a program to generate prime numbers for a given range. The sieve of Eratosthenes algorithm was implemented, but still the SPOJ says time limit exceeded. Where can some optimizations be made? ...