-2

Thanks to this video I managed to further optimize the time for my code for Problem 7 on Project Euler. However, as someone who's getting more familiar with Python, I want to understand line 105 in the image here. What is this line of code trying to do? Also, any suggestions on how to optimize this solution even more are welcome.

if all(x%i for i in primeList): ...

image of Problem 7 solution

cerise hibiscus
  • 1
  • 1
  • It looks to me that this line is checking whether the remainder of the division of a number and all currently known primes are never zero, i.e. the current number is a prime too. – NotAName Aug 05 '22 at 06:53
  • 2
    `primeList` is the list of current primes. `x%i for i in primeList` produces a list, with one entry for each item in the list, with the result of the modulo operation. The `all` function returns True if all of its parameters are true-ish. If a number is prime, all of the modulos will be non-zero, so `all` will return true, and it gets added to the list. – Tim Roberts Aug 05 '22 at 06:53
  • Small addendum: `x%i for i in primeList` does not produce a (temporary) list, but is merely a generator expression, that will only evaluate elements until the first falsey is found (if any) and at no point will store all the elements. – tobias_k Aug 05 '22 at 07:01
  • Further optimizations: You don't have to test all the primes in `primeList`, but only those `<= sqrt(x)` (that may be tricky with `all`, but e.g. `itertools.takewhile` might help); also, the `if` in the loop is redundant, just put the `print` _after_ the loop instead. And instead of `max`, just print `primeList[-1]` for the last element. – tobias_k Aug 05 '22 at 07:04
  • I don't recommend watching videos spoiling the problems from Project Euler. Those are awesome problems, but you won't learn anything at all if you don't solve them on your own. – Stef Aug 05 '22 at 09:23

1 Answers1

0

Hi this line of code is checking if the new x value is divisible by each value on primeLisl. for example:

x=4
primes = [2,3]
list = [x%i for i in primes]

in this case list returns: [0, 1] (4 is divisible by 2 and not by 3) when applying the all function checks if any value in the list is equal to 0 and in this case returns fales. If all the values of the list are diferent to 0 returns true.

kithuto
  • 455
  • 2
  • 11
  • Why would recursion be faster? – deceze Aug 05 '22 at 07:05
  • The difference in the algorithm in the question is that it uses a generator so the evaluation will never get to `4 % 3 = 1`. It return False immediately as it encounters `4 % 2 = 0` – NotAName Aug 05 '22 at 07:05
  • It can be faster (depends on the implementation) just try it and time it. – kithuto Aug 05 '22 at 07:06
  • 1
    @NachoR. First and foremost, it depends on what the implementation is doing. Which would be what exactly? I don't see how recursion would be faster here at all. – tobias_k Aug 05 '22 at 07:07
  • 1
    In my experience in most cases an iterative approach in Python is faster than recursion and much more memory-efficient. – NotAName Aug 05 '22 at 07:07