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
14
votes
3answers
616 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...
15
votes
3answers
918 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
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: ...
3
votes
1answer
738 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
120 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>, ...
2
votes
2answers
188 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 ...
3
votes
0answers
133 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
508 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
179 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
459 views

Optimization of a basic Sieve of Eratosthenes algorithm

I have the following Sieve of Eratosthenes algorithm: ...
4
votes
3answers
946 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
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 ...
5
votes
2answers
459 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
399 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
174 views
2
votes
2answers
441 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
524 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
844 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
2k 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
291 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
485 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
317 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
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 :) ...
3
votes
2answers
169 views

Efficiency of sieve of Eratosthenes

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

Creating vector of primes using Sieve of Eratosthenes

Please review my Sieve of Eratosthenes implementation. ...
5
votes
3answers
746 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
852 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
202 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
182 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
307 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
186 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. ...
7
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
954 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
372 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
3k 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
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 ...
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
794 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 ...
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, ...
5
votes
3answers
671 views

Psycho and ordinary numbers

The problem statement can be found here. In short, here's what the problem is about: You're given a set of numbers and you need to find whether the the numbers are ordinary or psycho. For a number ...
5
votes
1answer
2k views

Sieve of Eratosthenes - Standard and Optimized implementation

I am a Java developer who is taking Python for the first time. I'm sure this is not at all elegant since I am thinking more in C syntax. ...
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 ...
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 ...
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 ...
14
votes
4answers
9k views

Sieve of Eratosthenes in C++

I'm looking for some feedback on my implementation of the algorithm. How can I improve it? I ran into problems when calculating the larger prime numbers > 46349 due to integer overflow, but fixed that ...
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? ...
10
votes
4answers
1k views

Sieve of Eratosthenes optimization

I am making a program to find primes between the given range of numbers. Unfortunately, the algorithm I created is too slow. Do you have any ideas of how to optimize the code? ...
9
votes
3answers
3k views

Sieve of Eratosthenes in Java

Here you can find my implementation of sieve of Eratosthenes in Java. ...
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. ...