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

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

    Is latex an option in the markdown?