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

166 questions
Filter by
Sorted by
Tagged with
103 views

### Factors sieve optimization

I've written a more powerful version of the Sieve of Eratosthenes, this Sieve returns the number of factors of all the numbers below the limit.Sadly the running ...
216 views

### Windowed Sieve of Eratosthenes in Java

I wanted to try and use the Sieve of Eratosthenes to find all prime numbers between some arbitrary bounds 1 <= m <= n. The simple implementation of the sieve ...
1k 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 ...
1k views

### Goldbach's Conjecture using Sieve of Eratosthenes

I created a simple Java program to calculate Goldbach's conjecture and I was wondering how I could improve it (besides using clearer prompt messages). ...
336 views

### Sieve of Eratosthenes using a Javascript array

Any feedback on my code would be greatly appreciated. ...
147 views

### Yet another Sieve of Eratosthenes in Java

I wanted a reusable class for generating a list of primes till some arbitrary (but reasonable) limit. So, I wrote a class Primes that implements the Sieve of ...
304 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 ...
225 views

### Sieve of Eratosthenes Primes Efficiency

I'm fairly new to Java and was trying to make a program that's generates the primes from 2 - 100. I originally had a design of my own making but it was fairly inefficient so I did some research and ...
3k views

### Sieve of Eratosthenes in JavaScript

I found this method kinda tough to get for a beginner like me, but I tried to do my best, and here's what I came up with. Is this good code regarding performance? Is there anything wrong with it? <...
197 views

### Optimizing Sieve of Eratosthenes for larger numbers

I am having difficulty optimizing my code for the Sieve of Eratosthenes. The code works fine for smaller numbers (up to 10,000) but takes a long time to run for numbers over 100,000. ...
472 views

### Optimization of a “Sieve of Eratosthenes” in Java

I have created a simple Pseudo "Sieve of Eratosthenes," for a class in Java. I am looking for the most optimized option, or at least an option that is more optimized than current. If there is any ...
1k 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 ...
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 ...
125 views

### A non-static Sieve of Eratosthenes class, version 1

Over the years I’ve seen many C# sieves and despite their varying internals all that I have seen invariably are a static method that returns a List<int>, ...
386 views

### Java Implementation of Sieve of Eratosthenes algorithm

I previously asked about my implementation of the Sieve of Eratosthenes algorithm here. After looking at all of the feedback, I have reworked the code to make it significantly more efficient. However,...
302 views

### Sieve of Eratosthenes in Scheme (R7RS)

I've seen many implementations of Sieve of Eratosthenes in Scheme, but I thought I'd try to write one that is both space- and time-efficient: Space-efficient: I use R7RS bytevectors as a bitset, ...
64 views

### Pythonic sieve of Erasthotones that saves results to file

I'd like to have some feedback on this sieve of erasthotones that I've wrote. It outputs all prime numbers up to n correctly (I've tested with the first 10k prime ...
410 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 ...
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 ...
1k views

### Primes Without 1's

Requirement primes numbers which do not have digit 1 in it. Input The first line contains T, the number of test cases. Followed by T lines each contain two numbers M and N Output ...
254 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 ...
765 views

### Sieve of Eratosthenes Optimization in Rust

When I want to try a new language, I first try to write a fairly basic sieve of Eratosthenes project in said language. This is a very simple algorithm, with predictable results, and can even be ...
231 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 ...
129 views

### Object-oriented approach to sieve of Eratosthenes

I was trying to implement the sieve of Eratosthenes entirely by myself, using only what I have learned so far. Now I'm wondering what I can do to improve my code's readability. Optimizing the ...
511 views

### Sieve of Eratosthenes to print prime numbers in a given range

This is my implementation for Sieve of Eratosthenes in Java.Please let me know how can I further improve my code: ...
286 views

### Sum of primes between two number from optimized Sieve of Eratosthenes

Here is the code that I wrote to give me sum of prime numbers between n and m: ...
200 views

### Effecient Use Sieve of Eratosthenes algorithm

Given this as a the Problem Statement Given two numbers, find the sum of prime numbers between them, both inclusive. Input: The first line contains the number of test cases T. Each ...
514 views

### Finding number of primes till n - Sieve of Eratosthenes

I've written a ruby implementation for Sieve of Eratosthenes algorithm, however benchmarking it against the Ruby's Prime module I have still a far slower algorithm -...
182 views

### Bitmap-based Sieve of Erastothenes

I have written a simple implementation of Sieve of Erasthotenes (in C, MSVC flavour), which I believe is correct (source below). Is there a way to make it faster and more readable? ...
495 views

### Optimization of a basic Sieve of Eratosthenes algorithm

I have the following Sieve of Eratosthenes algorithm: ...
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, ...
452 views

### Sieve of Eratosthenes JavaScript implementation - performance very slow over a certain number

I've been playing around with the code challenges on projecteuler.net. A few of them involve prime numbers, so I've created a function to find them based on the sieve of Eratosthenes. It works fine, ...
412 views

### Prime number calculator using Sieve of Eratosthenes

I've been writing this prime number calculator, and I've gotten it pretty quick in comparison to most I've seen knocking about. This one uses the Sieve of Eratosthenes approach, and I've optimised the ...
177 views

...
503 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 ...
545 views

### Making prime (sieve) code faster and able to run on big numbers

For an input triple (a, b, c), the task is to count the number of integers in the inclusive range [a, b] which have c distinct prime factors. This entails factoring each of the numbers in the range [a,...
916 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 ...
3k views

### A prime number sieve using recursion

Out of curiosity, I built a recursive Sieve of Eratosthenes in Python and I was wondering how it could be improved for efficiency and how it can improved to be aligned with python best practices. ...
318 views

### Attemped Sieve of Eratosthenes

I've just done Project Euler question 10: Find the sum of all the primes below two million. I get the correct answer and it takes about 3.5-4 seconds to run. I tried to use the Sieve of ...
453 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 :) ...
5k views

### Creating vector of primes using Sieve of Eratosthenes

Please review my Sieve of Eratosthenes implementation. ...
170 views

### Efficiency of sieve of Eratosthenes

Can I make this more efficient? ...
779 views

### Prime less than N that is a sum of the most consecutive other primes

Here's a Python implementation of the Sieve of Eratosthenes: ...
1k views

### Sieve of Eratosthenes in C++11

Please point out every problem you see with this code. Any fundamental flaws, naming conventions, design decisions, you name it. ...
207 views

### Sieve of Erathosthenes speedup

While reading HackerNews, I learned about a data set of the first 50 million primes. This would be a lot, but his website has disclaimer: n this directory I have the first fifty million primes in ...
13k views

### Find prime numbers under N

I'm using the Sieve of Eratosthenes to find primes numbers under N. Is there any performance problems you see with my approach? I used the LinkedList<Integer> ...
2k views

### Eratosthenes sieve and MPI

I wrote this sieve of Eratosthenes with MPI, but I'm not sure if it's good enough. Should I use MPI_Scatter and MPI_Gather ...
319 views

### Quadratic Primes - Project Euler 27

Project Euler Problem 27 Euler discovered the remarkable quadratic formula: $n^2 + n + 41$ It turns out that the formula will produce $40$ primes for the consecutive values $n = 0$...