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
5
votes
1answer
4k 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 ...
6
votes
1answer
323 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 ...
9
votes
1answer
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 ...
6
votes
2answers
403 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,...
6
votes
1answer
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 ...
5
votes
3answers
417 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 ...
19
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 ...
4
votes
7answers
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 ...
4
votes
1answer
285 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 ...
4
votes
2answers
136 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 ...
1
vote
1answer
514 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: ...
16
votes
3answers
793 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...
16
votes
3answers
1k 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): ...
1
vote
1answer
288 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: ...
3
votes
1answer
840 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 ...
0
votes
1answer
133 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>, ...
3
votes
2answers
230 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 ...
1
vote
0answers
139 views

R-Python sieve, 36 times slower than World Record

I decided to write a sieving prime-finding programme and make it fast. It works correctly but counting the primes below 10**9 takes 36 times as primesieve ...
4
votes
1answer
547 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 -...
5
votes
2answers
184 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? ...
3
votes
1answer
566 views

Optimization of a basic Sieve of Eratosthenes algorithm

I have the following Sieve of Eratosthenes algorithm: ...
4
votes
3answers
2k 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 ...
3
votes
1answer
105 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 ...
5
votes
2answers
492 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 ...
5
votes
1answer
474 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 ...
3
votes
3answers
181 views
2
votes
2answers
492 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, ...
7
votes
1answer
577 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,...
5
votes
3answers
1k 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 ...
2
votes
1answer
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. ...
5
votes
1answer
360 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, ...
6
votes
1answer
541 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 ...
2
votes
2answers
326 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 ...
1
vote
1answer
544 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 :) ...
3
votes
2answers
171 views

Efficiency of sieve of Eratosthenes

Can I make this more efficient? ...
5
votes
5answers
5k views

Creating vector of primes using Sieve of Eratosthenes

Please review my Sieve of Eratosthenes implementation. ...
5
votes
3answers
822 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: ...
11
votes
2answers
965 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.) ...
1
vote
2answers
224 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 ...
3
votes
2answers
228 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. ...
6
votes
2answers
352 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\$...
1
vote
1answer
219 views

Writing a Pythonic prime sieve

I'm practicing writing code less by brute force. I'd like feedback for writing a prime sieve more Pythonic, simpler, or more creatively perhaps. ...
8
votes
7answers
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> ...
8
votes
2answers
986 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 ...
7
votes
3answers
412 views

Modified Sieve of Eratosthenes has very long runtime

I am slowly moving through Project Euler, and have reached problem #10: The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17. Find the sum of all the primes below two million. I did a naive ...
16
votes
2answers
4k views

Generating prime numbers using Sieve of Eratosthenes with CUDA

I'm learning CUDA and wrote a little program which generates prime numbers using the Sieve of Eratosthenes. (I know the limitations of CUDA, specially with memory sizes and limits, but this program is ...
11
votes
4answers
403 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 ...
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
2answers
850 views

Submitting a Java program which implements the Sieve of Eratosthenes

I would like some feedback on a Java program which implements the Sieve of Eratosthenes to find prime numbers. Some of the 'features' I've included in the program include: It uses a ...
7
votes
5answers
2k views

A fast approach to prime number sieving (non-threaded array)

I am posting this question for input on comparisons between other sieving methods and opinions on what I have discovered. I believe this might be the fastest (singular, non-threaded) array ...