37
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 1/2 * 2/3 * 4/5 * 6/7 = 22% of all numbers make it through your filters for 2, 3, 5 and 7, so your filter for 11 will have to check 22% of all numbers. The real sieve of ...
34
Here's my starting point for computing the performance improvement due to the various revisions below: how long does it take to sieve for the prime numbers below \$ 10^8 \$?
>>> from timeit import timeit
>>> test = lambda f: timeit(lambda:f(10**8), number=1)
>>> t1 = test(sieve)
The exact number is going to depend on how fast ...
28
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> you get this optimization for free.
Store only odd numbers in the array. This will save additional factor of 2 in memory. You need to adapt the logic of the program a little bit, but this is not ...
24
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 itself and not to the style or any language
specifics. And most probably I am making a lot of C# errors here.
The following tests were done on a MacBook Pro ...
23
As you are correctly assuming there are multiple threading related issues with your code, but lets tease you and start with the usual suspects.
Naming
The name apply_prime is misleading and inexpressive.
Neither does the function really require a prime nor does apply do it justice.
You should name it something along the lines: strike_out_multiples or ...
23
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 with the code, then you have to worry which is correct. Is the comment correct and the code is bad and thus I have a bug to fix, or os the code correct now I ...
22
Generally it's nice, well-structured code, but it relies on a promise that might not be kept.
Specifically, simultaneous access to different elements in std::vector<bool> is not guaranteed to be thread-safe because storage bytes may be shared by multiple bits in the vector.
Consider an alternative way to slice things. Each thread could be ...
21
Using a set() is your bottleneck, memory-wise.
>>> numbers = set(range(3, 10**8, 2))
>>> sys.getsizeof(numbers)
2147483872
>>> sys.getsizeof(numbers) + sum(map(sys.getsizeof, numbers))
3547483844
A set of odd numbers up to 100 million is consuming 2GB 3.5GB (thank-you @ShadowRanger) of memory. When you do an operation like ...
19
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. You could instead use atoi(), strtol() or sscanf().
Use the Right Comparison
You made max be an unsigned int, but then you compare it against -1 and -2. ...
17
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 computer the time your algorithm takes is roughly equivalent to the amount of data that it reads and writes, so halving the space needed will half the execution ...
16
Ignoring the memory problems with cache invalidation (which will slow the code down).
Creating a thread is relatively expensive (as you have to allocate a stack and maintain it). So rather than creating and destroying threads it is better to maintain a thread pool and reuse the threads.
The number of threads to put in the pool should be slightly larger ...
16
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 replaced with std::array (C++11).
#include <array>
#include <utility>
template <typename T, T... Is>
constexpr auto gen_primes_helper(std::integer_sequence<T, Is...>) {
...
14
About the only huge, performance-impacting change I can see that would be necessary is replacing the BitArray for a literal bool array.
This actually has a huge speed impact.
So, making that change, and inverting the related conditions causes us to have the following method:
public static IEnumerable<int> Primes(int upperLimit)
{
if (upperLimit &...
12
As 200_success pointed out, you have not implemented a sieve. See Wikipedia's pseudo code for the Sieve of Eratosthenes.
You need to check if reading in a number was actually successful:
if (!(std::cin >> number)) {
std::cerr << "Invalid number provided" << std::endl;
return EXIT_FAILURE;
}
(Note that you would need cstdlib for ...
12
Actually, the threading is just totally wrong. There are race conditions all over the place. Due to the kind of problem, it doesn't have many visible effects, but it is still wrong.
The out loop in sieve_eratosthenes loops over indices from 2 to end and checks whether array elements are marked as "prime". In that loop it starts threads which change array ...
12
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 index += loop, where loop is the prime number, and but primeCandidates only holds odd candidates, so the step size in natural numbers would be 2*loop.
The issue is you start by removing 7 from primeCandidates, then ...
12
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 adding filters and instead only adding filters up to the square root of the current candidate number. And I found an in my opinion neat way to do that. ...
11
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 Eratosthenes
bool f[100000001];
void siv()
You're asking for a code review, so you want to encourage people to read your code. You could make it easier on us by picking self-commenting names. For ...
11
Don't define bool yourself
typedef unsigned char bool; is technically legal in C, but very bad style. If you want a proper bool in C that works like it does in C++ (guaranteed to only be 0 or 1), #include <stdbool.h>.
If you want a 0 / non-zero integer type that avoids the possible inefficiencies of bool (Boolean values as 8 bit in compilers. Are ...
11
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 subsequent numbers instead.
That makes a huge difference. I'll come back to that later, let's start
with a
Review of your current code
There is a ...
10
Equally-sized sequential subsets of primes don't evenly divide the task. The smallest numbers lead to a lot more multiples.
Test-before-set might significantly reduce cache contention. Even better, don't start at prime*2u, start at prime*prime.
10
A few notes:
Right now you are using int[]s to represent the sieve. However, the int data type is internally stored as 32-bits, which is a waste of space.
Use java.util.BitSet to represent the sieve. It provides a vector of bits that grows as needed. All bits start out as 0, and we can set and clear a bit at any index. It uses only one bit per entry. This ...
10
Your first setting of all the even numbers to 0 is not very efficient, the whole point of sieving is to avoid those costly modulo operations. Try the following:
l = range(2, upperlimit+1) # use list(range(...)) in Python 3
l[2::2] = [0] * ((len(l) - 3) // 2 + 1)
You can do a similar thing for the setting of zeros of the sieve for other prime numbers, but ...
10
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, it's only something that will get out of date because refactoring can't reach it. Second, the other parts should be in the JavaDoc of the class.
Variable names....
10
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 following:
scan all the data from the beginning until you find the member with the value number
if you find that value:
for every remaining value, shift it one back (replace each n with the value at ...
10
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 should do instead is:
Read all test cases first (into a vector for example).
Find the maximum n of all the test cases.
Use your sieve once to find all primes up ...
10
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:
num_t j = i;
Because you start your j loop at i, you will mark i (which is prime) as non-prime. You should start your j loop at i*i instead (see below).
Don't get tricky
Why write this:
for(num_t i = 0; i ^ N; ++i)
...
10
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 optimizations I will give you some advice on the code you have written
Your naming scheme is for the most part good. Good variable names should be descriptive, ...
10
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 len(primes) >= n either.
import pytest
from math import log, ceil
def find_primes(limit):
nums = [True] * (limit + 1)
nums[0] = nums[1] = False
for (i, is_prime) in enumerate(nums):
...
10
Commenting
You could improve the functions with some introductory comments. In particular, the isPrime() predicate has an extra argument compared with the conceptual version - we should be clear what that's for (i.e. it's an ordered set of all primes up to √num). Similarly, sieve()'s results argument is assumed to be empty, but that's not clearly ...
Only top voted, non community-wiki answers of a minimum length are eligible
