# Tag Info

104

Your code is a bit messy, and having the file name hard-coded in to your function is not great. Also, the "Hungarian Notation" (using things like arg to prefix your function parameters - note, it's a parameter, not an argument, by the way)... is not conventional. On the other hand, I understand this is an exercise to test performance.... and it's not about ...

77

bool isPrime = true; for (int j = 2; j < i / 2; j++) { if (i%j != 0) continue; isPrime = false; break; } if (!isPrime) continue; This is one of the most primitive and least efficient ways to calculate whether or not a value is prime. First and foremost, we deserve a method which encapsulates this logic and can be called repeatedly: bool ...

54

Using BufferedInputStream would be a quick fix with lesser modification of current code. The reason why readX methods of DataInputStream/FileInputStream are slow is that they ask for IO every time. BufferedInputStream simply loads a chunk of file to reduce the number of IO operations needed. Another solution is to use read() method to load the (whole or ...

31

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 ...

30

A few things in addition to what @Jamal and @200_success already wrote: g++ on Mac OS X won't compile this code, because of #include "stdafx.h" and the int _tmain(int argc, _TCHAR* argv[]) signature. It's good to keep your code portable, unless you have a special reason not to. g++ can compile if you drop the stdafx.h import and if change the main ...

29

TL;DR: Just use PyPy; it gets you to about 10x the time of C++. If you really want to use CPython, a lot of clever optimizations (not algorithm changes) gets you as fast as PyPy and then using Numpy gets you close to C++ (2x the time). The first thing of note is that your Python code is broken: if m > len(marked): break Remember that Python ...

28

You are doing brute-force trial division, and not particularly smartly. For example, you only need to test odd candidate factors up to sqrt(number). When you want to find many prime numbers, a much better algorithm to use is the sieve-of-eratosthenes. It involves just addition, no division, and skips processing of numbers that are already known to be ...

27

while True: for i, prime in enumerate(is_prime): if prime and i > p: p = i break else: break This is the cause of the slowness: track the state between loops and the 25 seconds drop to 0.05 seconds. multiple = p + p while multiple <= n: ...

25

Style The Style Guide for Python Code called PEP 8 recommends a 4-space indent. More functions You could split your logic into smaller logical pieces which are easier to understand, to test and to optimise (I'll come back to this later). For instance: def is_prime(n): for i in range(2, n): if n % i == 0: return False return ...

25

Your program has a bug. is_prime returns true in all possible return situations. You don't notice that because your prime factors already use a nice property of prime factors which we inspect later. Here's a short list of improvements first: return condition instead of if condition return true; else return false; return early. Use appropriate return types. ...

25

Style: Indent your operands to a consistent column, so mnemonics of different length don't make your code look so ragged. And use local .label labels inside functions. Comment code that depends on non-standard behaviour: stdout is only guaranteed to be line-buffered, and isn't automatically flushed when you read stdin in ISO C. Some systems (like Linux) ...

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

The major problem here is using imprecise floating point values. Not only does it slow the entire process (minor quibble), but it will produce incorrect results once the values pass the integral cutoff of the field width. If you truly want to allow calculations approaching infinity (or what? 24 bits?) you need to switch to BigInteger which can model "exact" ...

21

A faster method would be to skip all even numbers and only try up to the square root of the number. public static boolean isPrime(int num){ if ( num > 2 && num%2 == 0 ) { System.out.println(num + " is not prime"); return false; } int top = (int)Math.sqrt(num) + 1; for(int i = 3; i < top; i+=2){ if(num % ...

21

Things you could improve Efficiency As @rolfl stated, you want to use a Sieve of Eratosthenes (+1 to that answer). I can't see if you are doing this already, but you should be compiling with your compiler's highest optimization level. With GCC for example, this would be -O3. Portability Keep in mind to adhere to the standards as closely as possible, ...

21

Algorithm I think you've gotten distracted by focusing on the wrong aspect of the problem. The challenge asks for the largest prime factor of n = 600851475143. There are three approaches you might consider in tackling this challenge: Construct the list of all relevant prime numbers, then take the largest one that is a factor of n. How high do we need ...

21

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

The problem is: What is the largest prime factor of the number 600851475143? Your solution has a function named lpf, which computes the complete prime factorization of the number and prints it and returns the largest prime factor. That is doing too many things! Your function should do one thing: find the largest prime factor. Doing that, we can ...

21

There are a few algorithms that might help you: The sieve of Eratosthenes is the most simple to implement, but not the most efficient (still more efficient than your algorithm though) The sieve of Atkin is a lot faster, but a bit harder to implement BPSW-primality test. You can test a number for not being prime with this test, but you're never actually a ...

21

Here are a number of things that may help you improve your program. Use a better algorithm As already mentioned in the comments, a Sieve of Eratosthenes is going to be much, much faster than the current method. Generally speaking, doing division is a computationally expensive operation. For example, a simple Sieve program to solve this same problem takes ...

19

In C++, you should now use std::cout and std::cin instead of printf() and scanf() respectively. These are found in <iostream>, and you'll no longer need <stdio.h>. Example of std::cout: int number = 1; std::cout << "Number: " << number; Example of std::cin: int number; std::cin >> number; currentNum just needs to be ...

19

The algorithm itself is nowhere as efficient as it could be, but let's focus on your implementation instead: Choosing appropriate data types list<long long> lst={2ll,3ll}; Why bother with a list, and why bother with with long long? Only use a list if you need random inserts with a cached iterator. In your case, an vector would have fit much better. ...

19

Your method of generating primes is horribly slow. Running your code takes on the order of 5 minutes on my machine. Consider as an alternative a prime sieve, even a simple one like the Sieve of Eratosthenes will do (you don't need to go full Atkinson on it): def prime_sieve(limit): a = [True] * limit a[0] = a[1] = False for i, isprime in ...

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. ...

19

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 ...

18

Consider memory mapped files Disclaimer: This is also for me the first time I'm playing with memory mapped files in Java. The way I'm doing it might be suboptimal or even worse. I think that Java's DataInputStream has high overhead for portability and error handling that is probably not needed in your situation. The fastest way to achieve your problem ...

18

By starting with j = 3 and incrementing j by 2 you could skip a lot of unneeded computations because it will skip even values. Instead of using a float I would go with int. Both are 32-Bit and you won't need the floating point values. You should let your variables have some space to breathe. Consider while(primes[primes.Length-1]==0){ if(isPrime(...

18

There are numerous small things. You don't have to keep subtracting and adding 32 from rsp. Allocate the space once at the start of the function (main), reuse it for the duration, and add it back at the end (but see below). My personal preference would be to use mov ecx,offset question to make it clear that I want the address of the variable, and not the ...

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