New answers tagged

1

Problems There is one correcntness and two performance problems with your approach, both connected with running through the problem from the high numbers and down. For the correctness problem consider the number 91, it has the factorization of 7*13, but your approach would find 7 to be the largest, since 9 < 91**0.5 < 10 < 13, but the correct one ...


0

order You wrote: if is_prime(divisor) and number % divisor == 0: that is, if A and B:. But B is typically false and is quickly computed. Prefer if B and A: stride Rather than for divisor in range(int(number ** 0.5) + 1, 0, -1): you might want to begin with an odd number and then use a stride of -2. You needn't special case for when number is ...


1

#define int long long Not only is redefining int a bad idea, but using long long should be reserved for legacy code. Use <cstdint> and (given the ranges used in this code) std::uint_fast32_t. if (limit > 2) cout<<"2 "; if (limit > 3) cout<<"3 "; ... 21 lines ... for(int i=sieve._Find_first();i< ...


1

Here are a few things you could try... Including those mentioned by @tinstaafl I think that you can avoid a lot of the computations. I had a brief look at the Wikipedia page, it seems that you are otherwise properly following the algorithm. #include<bitset> #include<vector> #include<iostream> #include<algorithm> #pragma GCC target (...


1

It may well be more efficient to compute std::sqrt(max) once upfront than to multiply n * n every time around the loop. Removing an element by value from the set is O(log n), where n is the set size at the time. This will likely make this method slower than writing to elements in a fixed-size storage (such as a std::vector that's never resized), and ...


3

I'm not sure what your optimizations are doing(comments would be nice), but I did notice several inefficiencies: Never include a calculation in the limit test in a for loop. It get's re-calculated on every iteration. In this case set the limit to sqrt(limit). the calculation is kind of expensive but it's done only once. The same goes for the iteration ...


1

Organization Your function prime_sum() does three things. It computes primes up to a limit It sums up the computed primes It prints out the sum. What are the odds the next Euler problem will use prime numbers? You’re going to have to write and re-write your sieve over and over again if you keep embedding it inside other functions. Pull it out into its ...


Top 50 recent answers are included