38 votes
Accepted

Why is my Sieve of Eratosthenes using generators so slow

That's not the sieve of Eratosthenes It's rather prime trial division. Your filter for 2 lets 1/2 of all numbers through, your filter for 3 lets 2/3 of all remaining numbers through, etc. So ...
user avatar
  • 2,954
28 votes

Extending Sieve of Eratosthenes beyond a billion

A few things you can do: Use a bit vector (with bit manipulation) instead of a bool array. This gives you 8 times more memory. If you use C++ vector< bool> ...
user avatar
24 votes

Sieve of Eratosthenes implementation is running slowly

There is some room for improvement in your code, and I will try to explain that in several steps. But please note that I am not a C# person, so my review refers only to the algorithm and performance ...
user avatar
  • 22.3k
23 votes
Accepted

Prime sieve for all primes up to a number

Comments Most people write bad comments. Things that should be commented are idea/decisions/why. Writing comments that explain the code is horrible. This is because comments often fall out of date ...
user avatar
  • 91.7k
21 votes
Accepted

Prime sieve in Python

Using a set() is your bottleneck, memory-wise. ...
user avatar
  • 30.8k
19 votes

Sieve of Eratosthenes in C

This works really well and is very easy to read! Here are some suggestions. Don't Reinvent the Wheel There are plenty of ways to convert a string to a number in C. There's no need to write your own. ...
user avatar
  • 11.5k
17 votes
Accepted

Extending Sieve of Eratosthenes beyond a billion

There is a huge number of ways to make this run faster. First you save an awful lot of space by storing only odd numbers in the sieve. The only even prime is the number 2. Note that on a modern ...
user avatar
  • 2,446
16 votes
Accepted

Compile-time sieve of Eratosthenes

I believe I can help with these things: Obliterate macros Obliterate raw arrays Macros can be replaced with std::integer_sequence (C++14), and raw arrays can be ...
user avatar
  • 541
14 votes
Accepted

Sieve31, my sieve of Eratosthenes returning IEnumerable<int>

About the only huge, performance-impacting change I can see that would be necessary is replacing the BitArray for a literal bool ...
user avatar
13 votes

Why is my Sieve of Eratosthenes using generators so slow

Back to the roots - be lazier! (Taking this in another direction than my first answer, and it's different/long enough that I don't want to mix them.) We can vastly improve your approach by not eagerly ...
user avatar
  • 2,954
12 votes

Prime Sieve and brute force

When you find a prime number, say 7, you begin crossing out all odd multiples of 7 from the primeCandidates vector. You do this by incrementing ...
user avatar
  • 30.8k
11 votes
Accepted

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

using namespace std; It won't matter much with this program, but this can be a bad habit to start. See Why is using namespace std bad practice? Sieve of ...
user avatar
  • 6,894
11 votes

Sieve of Eratosthenes in C

Don't define bool yourself typedef unsigned char bool; is technically legal in C, but very bad style. If you want a proper <...
user avatar
  • 2,642
11 votes
Accepted

Prime Number Generator in Swift

That is not the Sieve of Eratosthenes The Sieve of Eratosthenes computes multiples of each found prime to mark subsequent composite numbers in the sieve. Your algorithm computes the remainder of all ...
user avatar
  • 22.3k
10 votes

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

Just some minor comments to the code style. Let's start with your fileheader...in these times and days it should be unnecessary. First it doesn't make sense to have the file/classname in the comment, ...
user avatar
  • 7,637
10 votes

Threshed and Malachi'd: Sieve of Eratosthenes

This line here is horrible, terrible, and miserable: if (number % i == 0) { primes.Remove(number); } That one line is basically (behind the scenes) doing the ...
user avatar
  • 96.7k
10 votes

Optimization on Sieve of Eratosthenes using vector<bool>

Repeating work already done The biggest problem with your solution is that for each test case, you start over from scratch. This causes you to do up to 10x the work that you need to do. What you ...
user avatar
  • 28.4k
10 votes
Accepted

Eratosthenes Sieve optimized in C

Bug At the end of your program, the b array is all full of 1s, which means that you didn't find any primes. The problem is here: ...
user avatar
  • 28.4k
10 votes
Accepted

Snakes on a prime

Introduction It took me a good 30 hours to figure out this solution. However when one sees the drastic speed increases it produces it might have been worth it. Before I go into the performance ...
user avatar
10 votes
Accepted

Finding nth Prime using Python and Sieve of Eratosthenes

Upper bound for p_n There is a known upper bound for the n-th prime. It means that you don't need any loop inside find_n_prime, and you don't need to check if <...
user avatar
  • 3,958
10 votes

Prime Sieve and brute force

Commenting You could improve the functions with some introductory comments. In particular, the isPrime() predicate has an extra argument compared with the ...
user avatar
10 votes

Prime sieve in Python

Is there a way to solve this memory or time problem using my code or should use a different algorithm? The algorithm is fine for the kind of scale you're talking about. It's the implementation of the ...
user avatar
10 votes

Sum of primes under a certain number

Method 1 (Sieve of Eratosthenes) is definitely the faster method to use. Starting point on my computer, summing primes less than 100,000 takes 39.916 seconds. List to Set The problem is basically ...
user avatar
  • 30.8k
9 votes

Sieve of Eratosthenes - segmented to increase speed and range

Generally speaking, I have to admit that I don't understand everything the code is doing and that I could use a little more time in order to understand it. However, I hope I can still give you some ...
user avatar
  • 19.9k
9 votes
Accepted

Wheel based unbounded sieve of Eratosthenes in Python

I thought of two things that achieve a 27 % speedup and simplify wsieve a bit, at the expense of some precomputations. Turning the wheel step by step from prime to ...
user avatar
  • 10.3k
9 votes

Extending Sieve of Eratosthenes beyond a billion

Although it's best to use container classes in C++ instead of allocating memory manually, I'll still point this out since it should still be said: ...
user avatar
  • 34.7k
9 votes
Accepted

Optimise Sieve of Eratosthenes

First, I would clean up the indices in the inner loop. I think the +2 and -2 are a bit confusing at the first glance. ...
user avatar
  • 106
9 votes

Prime sieve in Python

I think your performance problems at 10**6 elements start here: for i in range(3, int(num**(1/2)) + 1 , 2): This generates a list of numbers that you then build ...
user avatar
  • 507
8 votes
Accepted

Threshed and Malachi'd: Sieve of Eratosthenes

First problem: 1 is not a prime number. Second problem, after fixing that: Console.WriteLine(string.Join(", ", primes.Take(10))); 2, 3, 5, 7, 9, 11, 13, 15, ...
user avatar
  • 16.1k
8 votes

Generating prime numbers using Sieve of Eratosthenes with CUDA

I'd like to first compliment you for the extensive error-checking. It's harder to debug GPU code as opposed to CPU code, so it's important to utilize CUDA's error-checking functionality. You shouldn'...
user avatar
  • 34.7k

Only top scored, non community-wiki answers of a minimum length are eligible