yea, I changed the while to a for loop and the 6k one is faster almost always but the time difference is still in the same range and fluctuates wildly. I never realized that while loops are slower than for loops in python, ty for letting me know

you're comparing a while loop and a for one. In python, they behave differently about the perfs (while is slower) => those checks are meaningless in the current state.

hmm, the results of comparing the two often turns out to be wildly inconsistent in time difference but remains in the 1-10µs range, tho I found that the n = 19 and 1009 takes longer with 2k, n = 10000000019 takes less with the 2k one most of the time. Code used for testing:

import timeit
SETUP6K = '''
def prime_checker6k(n):
if n < 4:
return n > 1
if not (n % 2 and n % 3):
return False
for i in range(5, int(n ** 0.5)+1, 6):
if not ((n % i) and (n % (i + 2))):
return False
return True
'''
SETUP2K = '''
def prime_checker2k(n):
if n == 2: return True
if n%2 == 0 or n < 2: return False
for i in range(3, int(n**.5)+1, 2):
if n%i == 0: return False
return True
'''
def bench(n):
#print(f'Testing prime_checker2k and prime_checker6k with arg: {n}')
a = timeit.timeit(stmt=f"prime_checker2k({n})", setup = SETUP2K, number = 1)
b = timeit.timeit(stmt=f"prime_checker6k({n})", setup = SETUP6K, number = 1)
#print(f'Time taken for prime_checker2k = {a}\t\tTime taken for prime_checker6k = {b}\t\t2k-6k = {a-b}\n')
print(f'{"prime_checker2k" if a<b else "prime_checker6k"} is faster')
print(f'6k-2k = {round(b-a,9)}')
for _ in range(10):
#bench(19)
#bench(1009)
bench(10000000019)
print()

hmm, the results of comparing the two often turns out to be wildly inconsistent in time difference but remains in the 1-10µs range, tho I found that the n = 19 and 1009 takes longer with 2k, n = 10000000019 takes less with the 2k one most of the time. Code used for testing:

import timeit
SETUP6K = '''
def prime_checker6k(n):
if n < 4:
return n > 1
if n % 2 == 0 or n % 3 == 0:
return False
i = 5
sqrt_n = int(n ** 0.5)
while i <= sqrt_n:
if n % i == 0 or n % (i + 2) == 0:
return False
i += 6
return True
'''
SETUP2K = '''
def prime_checker2k(n):
if n == 2: return True
if n%2 == 0 or n < 2: return False
for i in range(3, int(n**.5)+1, 2):
if n%i == 0: return False
return True
'''
def bench(n):
#print(f'Testing prime_checker2k and prime_checker6k with arg: {n}')
a = timeit.timeit(stmt=f"prime_checker2k({n})", setup = SETUP2K, number = 1)
b = timeit.timeit(stmt=f"prime_checker6k({n})", setup = SETUP6K, number = 1)
#print(f'Time taken for prime_checker2k = {a}\t\tTime taken for prime_checker6k = {b}\t\t2k-6k = {a-b}\n')
print(f'{"prime_checker2k" if a<b else "prime_checker6k"} is faster')
print(f'6k-2k = {round(b-a,9)}')
for _ in range(10):
#bench(19)
#bench(1009)
bench(10000000019)
print()

Then how should c! be calculated without calculating (c-1)!?
OK, I see your solution. But factorial grows very fast, so the number of iterations is small in any case...
And division is expensive in general, although I'm not sure how much it matters in this case.

@quint Impressive, but looks overly mathematical for the task... I'd stay with the slower solution for the sake of readability.

agreed. also an edge case test: ",,treat"

, is not alphabetical

yea, I changed the while to a for loop and the 6k one is faster almost always but the time difference is still in the same range and fluctuates wildly. I never realized that while loops are slower than for loops in python, ty for letting me know

you're comparing a while loop and a for one. In python, they behave differently about the perfs (while is slower) => those checks are meaningless in the current state.

also I have no idea why my reply got posted twice

hmm, the results of comparing the two often turns out to be wildly inconsistent in time difference but remains in the 1-10µs range, tho I found that the n = 19 and 1009 takes longer with 2k, n = 10000000019 takes less with the 2k one most of the time. Code used for testing:

hmm, the results of comparing the two often turns out to be wildly inconsistent in time difference but remains in the 1-10µs range, tho I found that the n = 19 and 1009 takes longer with 2k, n = 10000000019 takes less with the 2k one most of the time. Code used for testing:

Why would it better?

It's less explicit and way slower.

I did a quick test, this will take 10s for a 3000*3000 matrix.

Using list comprehension, it only takes 1.8s

This comment is hidden because it contains spoiler information about the solution

Then how should

`c!`

be calculated without calculating`(c-1)!`

?OK, I see your solution. But factorial grows very fast, so the number of iterations is small in any case...

And division is expensive in general, although I'm not sure how much it matters in this case.

What do you mean?

Nice example! I can never understand when it's just the symbol soup of proofs and theorems.

Shouldn't it say

`(0 ≤ ai < mi)`

at the top?O(2N) = O(N)

Spoiler flag... ;p

But yes, this is much more "clever" than "best practices". But, considering the weirdness of the task itself, I'm not sure that should matter here. ;)

EDIT: look at the fork. ;)

This comment is hidden because it contains spoiler information about the solution

## Loading more items...