# Tag Info

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 ...
• 2,954

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

### 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 ...
• 22.3k
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 ...
• 91.7k
Accepted

### Prime sieve in Python

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

### 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. ...
• 11.5k
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 ...
• 2,446
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 ...
• 541
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 ...

### 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 ...
• 2,954

### 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 ...
• 30.8k
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 ...
• 6,894

### 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 <...
• 2,642
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 ...
• 22.3k

### 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, ...
• 7,637

### 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 ...
• 96.7k

### 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 ...
• 28.4k
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: ...
• 28.4k
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 ...
• 5,493
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 <...
• 3,958

### 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 ...
• 58k

### 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 ...
• 24k

### 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 ...
• 30.8k

### 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 ...
• 19.9k
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 ...
• 10.3k

### 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: ...
• 34.7k
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. ...
• 106

### 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 ...
• 507
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, ...
• 16.1k