Ad
  • Custom User Avatar

    Is there some reason for creating this many kumites?

    Do you have a problem with some functionality, or something does not work for you? Do you need any assistance?

  • Custom User Avatar

    the input(n) is first converted to unary (1=1, 2=11, 3=111, ...)

    first part (^1?$) and the ending $ check for n=0 or n=1

    in the second part, the regex uses basic divisor finding starting from 11(2 in decimal) (11+?)

    \1+ matches the previous group (initially 11) repeated one or more times in the unary representation of n. If at any point there is no match (the number is not divisible), the engine backtracks to make 11->111 (2->3 in decimal) and the process is repeated.

    e.g., even numbers (other than two) are pretty straightforward as they have an even number of ones (some multiple of 11 in unary, so the engine requires not backtracking)

    for odd numbers that are not prime, for example n=9(111111111), (11+?) matches 11 initially, but \1+ cannot match as there are 7 remaining ones. the engine backtracks and (11+?) 111 while \1+ takes care of the remaining ones

    for odd numbers that are prime, for example n=11, (11+?) matches the initial 11, but \1+ cannot match the remaining 5 ones. engine backtracks, checking for 3,4,5,... and the regex will not match.

    Learnt it myself from here

  • Custom User Avatar

    How does this work?😁

  • Default User Avatar

    n=10000000019

    • this solution: 21.4 ms ± 587 µs
    • faster version: 13.4 ms ± 40.5 µs

    Faster version:

    def prime_checker_6k(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
    
  • Custom User Avatar

    You might wanna try again, It wont work for n <= 1 and n == 4

  • Custom User Avatar

    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

  • Custom User Avatar

    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.

  • Custom User Avatar

    also I have no idea why my reply got posted twice

  • Custom User Avatar

    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()
    
  • Custom User Avatar

    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()
    
  • Default User Avatar

    Your solution is 2k optimization (only ignores multiples of 2).
    My first solution is 6k optimization (ignores multiples of 2 and 3).
    And last solution is 30k optimization (ignores multiples of 2, 3 and 5) — but in this solution, the constant is larger. Therefore, further I compare only 2k and 6k optimizations.

    n = 19 (is prime)

    • 2k optimization: 2.92 µs ± 59.9 ns
    • 6k optimization: 1.94 µs ± 41.6 ns

    n = 1009 (is prime)

    • 2k optimization: 6.74 µs ± 317 ns
    • 6k optimization: 5.91 µs ± 90.1 ns

    n = 10000000019 (is prime)

    • 2k optimization: 21.6 ms ± 598 µs
    • 6k optimization: 19.7 ms ± 586 µs
  • Custom User Avatar

    You can also just use more arguments of the range function, probably faster because it should be implemented in C.

  • Custom User Avatar

    Thanks for pointing out that I failed to check the boundary condition. I have added a new fork with that corrected. Please check!

  • Custom User Avatar

    And, in this case n ** 0.5 is square root of the number n.

  • Custom User Avatar
  • Loading more items...