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 ...
- 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> ...
- 609
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 ...
- 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 ...
- 91.7k
21
votes
Accepted
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. ...
- 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 ...
- 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 ...
- 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 ...
- 20k
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 ...
- 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 ...
- 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 ...
- 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 <...
- 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 ...
- 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, ...
- 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 ...
- 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 ...
- 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:
...
- 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 ...
- 5,493
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 <...
- 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 ...
- 58k
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 ...
- 24k
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 ...
- 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 ...
- 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 ...
- 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:
...
- 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.
...
- 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 ...
- 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, ...
- 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'...
- 34.7k
Only top scored, non community-wiki answers of a minimum length are eligible