fork download
copy 
  1. def largest_prime_factor(num):
  2.     '''returns the largest prime factor of a number'''
  3.     ans = 0
  4.     if num % 2 == 0:
  5.         ans = 2
  6.         num /= 2
  7.         while num % 2 == 0:
  8.             num /= 2
  9.  
  10.     i = 3
  11.     while i <= num:
  12.         if num % i == 0:
  13.             ans = i
  14.             num /= i
  15.             while num % i == 0:
  16.                 num /= i
  17.  
  18.         i += 2
  19.  
  20.     return ans
  21.  
  22. def largest_prime_factor2(num):
  23.     '''returns the largest prime factor of a number'''    
  24.     ans = 0
  25.     if num % 2:
  26.         pass
  27.     else:
  28.         ans = 2
  29.         while True:
  30.             num //= 2
  31.             if num % 2:
  32.                 break
  33.  
  34.     i = 3
  35.     while i <= num:
  36.         if num % i:
  37.             pass
  38.         else:
  39.             ans = i
  40.             while True:
  41.                 num //= i
  42.                 if num % i:
  43.                     break
  44.  
  45.         i += 2
  46.  
  47.     return ans
  48.  
  49. def largest_prime_factor3(num):
  50.     '''returns the largest prime factor of a number'''
  51.     def check(j):
  52.         nonlocal ans
  53.         nonlocal num
  54.         if num % j:
  55.             return
  56.         ans = j
  57.         while True:
  58.             num //= j
  59.             if num % j:
  60.                 return
  61.     ans = 0
  62.     check(2)
  63.     i = 3
  64.     while i <= num:
  65.         check(i)
  66.         i += 2
  67.  
  68.     return ans
  69.  
  70. def testing():
  71.     from timeit import Timer
  72.     import random
  73.  
  74.     def tests(f, times):
  75.         def test1(f):
  76.             f(random.randint(1, 1000))
  77.         def test2(f):
  78.             f(random.randint(100000, 1000000))
  79.  
  80.         print(f.__name__)
  81.         print(Timer(lambda: test1(f)).timeit(number = times))
  82.         print(Timer(lambda: test2(f)).timeit(number = times//10))
  83.         print()
  84.  
  85.  
  86.     tests(largest_prime_factor, 100)
  87.     tests(largest_prime_factor2, 100)
  88.     tests(largest_prime_factor3, 100)
  89.  
  90. if __name__ == "__main__":
  91.     testing()
Success #stdin #stdout 0.2s 12360KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
largest_prime_factor
0.0030820369720458984
0.03284001350402832

largest_prime_factor2
0.002521038055419922
0.05350303649902344

largest_prime_factor3
0.0027778148651123047
0.02176213264465332
https://ideone.com/565hyx
language:
Python 3 (python  3.12)
created:
12 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!