Single line for-loop

Question

I am trying to solve problem 7 of project Euler and this is the code I have

prime = []
counter = 0
while len(prime) < 10002:
    counter +=1 
    if counter%[i for i in range (counter)] == 0 and counter != 1:
        pass
    else:
        prime.append(counter)

print (prime[-1])

the line

if counter%[i for i in range (counter)] == 0 and counter != 1:

doesn't work. I am aware this is not the most elegent solution and will require a huge amount of time, but I am wondering how I can write this line as a single line and get it to work.

This line of code is supposed to say divide counter by every number smaller than counter. If any value yields no remainder, then the counter is NOT prime

Btw this question doesn't really have anything to do with Euler problem 7. It just so happens I am trying to solve it and thought it might help you understand what I'm trying to achievve

Thanks

look into [list comprehensions](https://docs.python.org/3/tutorial/datastructures.html#list-comprehensions). Also what is the `counter % [...]` supposed to do? — Henry Woody, May 05 '19 at 20:44
Perhaps you don't need, or shouldn't want, a single-line if-for construction. Instead (while at times confusing), this may be a practical case for the [for-else](https://stackoverflow.com/questions/9979970/why-does-python-use-else-after-for-and-while-loops) construction. — 9769953, May 05 '19 at 20:46

score 3 · Answer 1 · answered May 05 '19 at 20:47

3

Assuming you wanted to word it as "if counter is divisible by any of the numbers in [0, counter] range", any works like a charm:

if any((
  counter % i == 0
  for i in range(2, counter)  # note this implicitly contains "if counter != 1" condition
)):
  ...

answered May 05 '19 at 20:47

a small orange

560
2
16

1

I can't try it now, but it should work with single parentheses too (*Generator expressions always have to be written inside parentheses, but the parentheses signalling a function call also count.* - from https://docs.python.org/3/howto/functional.html#generator-expressions-and-list-comprehensions) – tevemadar May 05 '19 at 21:57

MarianD · Answer 2 · 2019-05-05T20:55:59.167

Instead of

if counter%[i for i in range (counter)] == 0 and counter != 1:

use

if any([counter % i == 0  for i in range (counter)]) and counter != 1:

The explanation:

The list

[counter % i == 0  for i in range (counter)]

is the list of values True and False - the results of the comparison counter % i == 0 for individual i.

Then the any() function returns True, if at least one of values in this list is True.

Henry Woody · Answer 3 · 2019-05-05T20:54:20.063

It looks like that counter % [...] line is meant to check if any number less than the current number divides the current number. To do this properly, you can iterate over each number from 2 up to the current number, check if each divides the current number and then check that none (not any) of the lesser numbers divides counter. You can do this by rearranging your current check.

For example:

primes = []
counter = 0
prime_count = 10002

while len(primes) < prime_count:
    counter += 1
    is_prime = counter != 1 and not any([i for i in range(2,counter) if counter % i == 0])
    if is_prime:
        primes.append(counter)

With prime_count as 10, we get the following result for primes:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

tevemadar · Answer 4 · 2019-05-06T11:46:37.083

If you want a "really" single-line prime test:

import math

isprime=lambda num:all((num%i)!=0 for i in range(2,int(math.sqrt(num)+1)))

count=0
num=1
while count<10001:
  num+=1
  if isprime(num):
    count+=1
    #print(count,num)

print(count,num)

all and any (next function on the same page) are useful for checking if all/any elements of an iterable are True
list comprehensions are nice, but generators are nicer here (related howto page). A list comprehension creates a list in one step, if the number in question is 1 000 000, it does all the 998 divisions (see next point). A generator generates its elements on the go, as 1000000 is already divisible by 2, all will not ask about the other 997 divisions, and thus they are not calculated
it is enough to run a prime test (or a collection for divisors) up to the square root of a number. After that, you find the same number-pairs, just slower: if i is a divisor of num, then num/i is also a divisor. And if i starts growing from 2, num/i will start decreasing from num/2. The two sequences meet at the square root of num, you can not find a "new" divisor afterwards.

You can try the following non-benchmark (the differences are so huge that a single-run is okay here) to see the effect of these factors:

import math,time

isprime1=lambda num:all((num%i)!=0 for i in range(2,int(math.sqrt(num)+1)))
isprime2=lambda num:all([(num%i)!=0 for i in range(2,int(math.sqrt(num)+1))])
isprime3=lambda num:all((num%i)!=0 for i in range(2,num))
isprime4=lambda num:all([(num%i)!=0 for i in range(2,num)])

def runtest(isprime):
  start=time.time()
  count=0
  num=1
  while count<10001:
    num+=1
    if isprime(num):
      count+=1
  end=time.time()
  print(count,num,end-start)

runtest(isprime1)
runtest(isprime2)
runtest(isprime3)
runtest(isprime4)

For me the output is

10001 104743 0.6920690536499023
10001 104743 3.529352903366089
10001 104743 110.67006587982178
10001 104743 1104.40642952919

score 0 · Answer 5 · answered May 06 '19 at 12:28

The part

if counter%[i for i in range (counter)] == 0 and counter != 1:
    pass
else:
    prime.append(counter)

may be replaced with

if all([counter % i  for i in range (counter)]) and counter != 1:
    prime.append(counter)

(For the function all() the expression counter % i behaves as counter % i != 0, because non-zero values are considered True.)

Single line for-loop

5 Answers5