On a practice exercise about prime numbers I found out that filter does not return a list itself and I need to do:
list(filter())
to obtain that list.
I do the exercise twice, once with a for loop:
def is_prime_for(n:init):
if n <=3:
return True
else:
m=list(range(2,n//2+1)) #+1 on the range for evade a bad result if 'n==4'
for i in m:
if n % i == 0:
return False
else:
return True
value = 864203
print(is_prime_for(value))
other time with filter and lambda:
def is_divisible(num1:float,num2:float):
if num1 % num2 == 0:
return True
else:
return False
def is_prime(num:int):
if list(filter(lambda x: is_divisible(num,x), list(range(2,num//2+1)))) != []:
return False
else:
return True
value = 864203 #Same prime number that i found on google
print(is_prime(value))
Later I re-use the code for higher order functions and find that my "compact" filter and lambda function takes double time than for function to execute and much more with a "False" number (for example a number that can be divided by 2).
I can understand the double time because it goes through the list twice instead of once but in the case of the "False" number I thought that filter() is going to give me a empty list until the first number appear but that's not the case, list is "empty" until filtering ends.
Does anyone know a way to "update" filtered items list one as a time instead at the end of the filtering?
That's my code now with the higher order function that show the execute time:
import time
def timeis(func): #Decorator that reports the execution time.
def wrap(*args, **kwargs):
start = time.time()
result = func(*args, **kwargs)
end = time.time()
print(func.__name__, end-start)
return result
return wrap
def is_divisible(num1:float,num2:float):
if num1%num2 == 0:
return True
else:
return False
@timeis
def is_prime(num:int):
if list(filter(lambda x: is_divisible(num,x),list(range(2,num//2+1)))) != []: #+1 on the range for evade a bad result if 'n==4'
return False
else:
return True
@timeis
def is_prime_for(n : int = 2):
if n <= 3:
return True
else:
m = list(range(2,n//2+1))
for i in m:
if n%i == 0:
return False
else:
return True
value = 864203 #A prime number that i found on google
#print(is_prime(value)) #That is used for prove the value find on google for no "false" positives
is_prime(value)
is_prime_for(value)
and that's the output:
is_prime 0.06304740905761719
is_prime_for 0.02378678321838379
**
**
After testing with the code from answer and coments the code end like this:
import time
def timeis(func): #Decorator that reports the execution time.
def wrap(*args, **kwargs):
start = time.time()
result = func(*args, **kwargs)
end = time.time()
print(func.__name__, end-start)
return result
return wrap
def is_divisible(num1:float,num2:float):
if num1%num2 == 0:
return True
else:
return False
@timeis
def is_prime(num:int):
if any(is_divisible(num,x) for x in range(2,int(num**0.5+1.01))): #Improved math with @Trincot answer and the help of @OneCricketeer on comments section
return False
else:
return True
@timeis
def is_prime_all(num: int): #@Trincot answer
return all(num%x for x in range(2, int(num**0.5+1.01)))
@timeis
def is_prime_all_mod(num: int): #@Trincot answer 'moded', it's faster on "False" numbers
return all(num%x for x in range(2, num//2+1))
@timeis
def is_prime_for(n : int = 2): #Improved math with @Trincot answer
if n <= 3:
return True
else:
m = range(2,int(n**0.5+1.01))
for i in m:
if n%i == 0:
return False
else:
return True
@timeis
def is_prime_while(n : int = 2): #Improved math with @Trincot answer
if n <= 3:
return True
else:
x = int(n**0.5+1.01)
i = 2
while i < x:
if n % i == 0:
return False
i+=1
else:
return True
#value = 28122221 #A prime number that i found on google
value = 28122222 #A "false" prime number for tests
#print(is_prime(value))
is_prime(value)
is_prime_all(value)
is_prime_all_mod(value)
is_prime_for(value)
is_prime_while(value)
With an output with a "Real" prime number:
is_prime 0.00029087066650390625
is_prime_all 0.0001399517059326172
is_prime_all_mod 0.607919454574585
is_prime_for 0.0001266002655029297
is_prime_while 0.00017380714416503906
And the output if a number is not prime like:
is_prime 1.0013580322265625e-05
is_prime_all 7.152557373046875e-06
is_prime_all_mod 1.6689300537109375e-06
is_prime_for 1.1920928955078125e-06
is_prime_while 4.76837158203125e-07
There are a few things to improve here:
There is no need to apply list to the range for the second argument of filter. filter just needs an iterable as second argument, so a range is fine.
There is no need either to apply list to the result of filter when the goal is to verify that filter yields no results. In that case you can use any instead of filter. If you use the opposite condition to filter by, then you can use all.
The following pattern is something to get rid of:
if <boolean-expression>:
return True
else:
return False
Instead, just return the value of the boolean expression.
You have given is_prime_for a slight advantage by making it perform the modulo operation inline, while is_prime must call a function for that. To have an equal playing field, is_prime should also perform that operation in line.
Both implementations can do better by limiting the search for divisors to the square root of n. Any greater divisor would have a smaller counter part. For instance, if n has n//2 as a divisor, then it also has 2 as a divisor, so no need to test both.
That brings us to this version of the code:
@timeis
def is_prime(num: int):
return all(num%x for x in range(2, int(num**0.5+1.01)))
Further improvements are possible.