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
2 votes
1 answer
93 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 ...
user avatar
4 votes
1 answer
102 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 ...
user avatar
  • 259
2 votes
2 answers
88 views

Sieve of Eratosthenes for primes up to 100

...
user avatar
5 votes
5 answers
658 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 ...
user avatar
5 votes
5 answers
663 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 ...
user avatar
  • 25.3k
13 votes
1 answer
308 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 ...
user avatar
  • 499
5 votes
3 answers
151 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 ...
user avatar
4 votes
2 answers
148 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 ...
user avatar
21 votes
4 answers
5k views

Why is my Sieve of Eratosthenes using generators so slow

This is my prime sieve based on the Sieve of Eratosthenes. ...
user avatar
2 votes
1 answer
91 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 ...
user avatar
6 votes
3 answers
923 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 ...
user avatar
  • 253
2 votes
2 answers
95 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: ...
user avatar
  • 153
1 vote
0 answers
93 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 ...
user avatar
  • 2,643
2 votes
1 answer
179 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 ...
user avatar
  • 171
4 votes
4 answers
922 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 ...
user avatar
  • 199
4 votes
1 answer
97 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. ...
user avatar
  • 5,522
7 votes
2 answers
809 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 ...
user avatar
  • 2,710
7 votes
1 answer
195 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 ...
user avatar
11 votes
2 answers
710 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 ...
user avatar
  • 185
8 votes
1 answer
334 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 ...
user avatar
  • 185
1 vote
2 answers
183 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 ...
user avatar
  • 335
4 votes
1 answer
373 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 ...
user avatar
  • 2,889
3 votes
2 answers
788 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? ...
user avatar
13 votes
3 answers
2k views

Prime sieve in Python

I was trying to write Sieve for the first time and I came up with this code: ...
user avatar
  • 509
5 votes
1 answer
74 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 ...
user avatar
  • 91.5k
14 votes
3 answers
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. ...
user avatar
  • 91.5k
9 votes
3 answers
1k views

Implementing Sieve of Eratosthenes faster

I wrote a version of sieve of eratosthenes: ...
user avatar
3 votes
1 answer
210 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 ...
user avatar
4 votes
2 answers
319 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 ...
user avatar
  • 201
1 vote
0 answers
61 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 ...
user avatar
  • 201
2 votes
1 answer
400 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 ...
user avatar
  • 195
2 votes
1 answer
931 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: ...
user avatar
  • 1,796
0 votes
1 answer
75 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: ...
user avatar
2 votes
1 answer
294 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 ...
user avatar
  • 857
2 votes
2 answers
132 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 ...
user avatar
  • 839
0 votes
3 answers
143 views

Short Eratosthenes Sieve

I've written a short implementation of the Eratosthenes' sieve. ...
user avatar
3 votes
2 answers
845 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. ...
user avatar
0 votes
2 answers
166 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? ...
user avatar
7 votes
2 answers
159 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 ...
user avatar
4 votes
1 answer
172 views

Sieve of Eratosthenes in Python

This is yet another take in Python for the infamous Sieve of Eratosthenes. I am a beginner in Python so any criticism is highly appreciated. ...
user avatar
  • 1,545
1 vote
0 answers
134 views

Get prime divisors of an Int32 using a wheel

I recently played around with prime factorization using a prime wheel. Much of the heavy lifting is done by the PrimeWheel class. I think the implementation is ...
user avatar
  • 5,522
2 votes
2 answers
3k views

Find primes using Sieve of Eratosthenes with Python

I was Googling for a 'correct' or 'efficient' implementation of the Sieve of Eratosthenes. I found them all more complicated than what I came up with. I am by no means a Python expert, so I was ...
user avatar
3 votes
1 answer
608 views

Functional Sieve of Eratosthenes in Clojure

For some reason, this is the first time I've ever written an implementation of the Sieve of Eratosthenes. I basically just stared at the Wikipedia walkthrough of the algorithm until it made sense, ...
user avatar
2 votes
2 answers
2k views

Finding the size of the largest connected component in a graph

Given this question, which simply can be explained as follows: Given the number of nodes and the number of edges in a graph, find the size of the largest connected component of the graph. If this ...
user avatar
4 votes
4 answers
870 views

Sieve of eratosthenes with std::vector<bool>

How can I improve and optimise this code? ...
user avatar
  • 2,439
8 votes
1 answer
4k 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 ...
user avatar
4 votes
2 answers
326 views

Sieve of Eratosthenes for small limits

I coded a sieve of Eratosthenes, I think it's quite fast for small limits. Any suggestions how to improve it? Especially for small limits, say limits < 50,000,000. (Also coded a parallel sieve (in ...
user avatar
  • 141
6 votes
1 answer
210 views

Kotlin sieve using sequences

While learning about functional programming the simple sieve example was brought up in Haskell. I wanted to try a Kotlin implementation using sequences. Are there any other quick wins without ...
user avatar
8 votes
1 answer
2k views

Finding nth Prime using Python and Sieve of Eratosthenes

I'm currently working through the Project Euler Problems using HackerRank to evaluate the code and I'm stuck on the 7th Problem. ...
user avatar
5 votes
4 answers
664 views

Improved RandomGenerator with nextPrime() method

I am trying to implement a method that generates a random prime number between a given range. I have tried using a simple method to find whether a number is prime or not, advanced simple method, ...
user avatar