fork download
copy 
  1. def prime_factors(n):
  2.     sqrt_n = int(n**0.5)
  3.     result = []
  4.     if n == 1: return result
  5.     while n%2 == 0:  # check for divisor = 2
  6.         result.append(2)
  7.         n /= 2 
  8.     while n%3 == 0:  # check for divisor = 3
  9.         result.append(3)
  10.         n /= 3
  11.     div = 5  # start with divisor = 6k-1 with k = 1
  12.     while div <= sqrt_n:
  13.         if n == 1: break
  14.         changed = n%div == 0
  15.         while n%div == 0:  # check for i = 6k-1
  16.             result.append(div)
  17.             n /= div
  18.         div += 2  # proceed to 6k+1 = 6k-1 + 2
  19.         if not changed: changed = n%div == 0
  20.         while n%div == 0:  # check for i = 6k+1
  21.             result.append(div)
  22.             n /= div
  23.         div += 4  # proceed to 6(k+1)-1 = 6k+5 = 6k+1 + 4
  24.         if changed: sqrt_n = int(n**0.5)
  25.     if n != 1: result.append(n)
  26.     return result
  27.  
  28. def largest_prime_factor(n):
  29.     if n == 1: return None
  30.     m = int(n**0.5)
  31.     while n%2 == 0: n /= 2
  32.     if n == 1: return 2
  33.     while n%3 == 0: n /= 3
  34.     if n == 1: return 3
  35.     i = 5
  36.     while i <= m:
  37.         changed = n%i == 0
  38.         while n%i == 0: n /= i
  39.         if n == 1: return i
  40.         i += 2
  41.         if not changed: changed = n%i == 0
  42.         while n%i == 0: n /= i
  43.         if n == 1: return i
  44.         i += 4
  45.         if changed: m = int(n**0.5)
  46.     if n != 1: return n
  47.  
  48.  
  49. if __name__ == '__main__':
  50.     print prime_factors(600851475143)
  51.     print largest_prime_factor(600851475143)
Success #stdin #stdout 0.01s 7728KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[71, 839, 1471, 6857L]
6857
https://ideone.com/nuiQAP
Largest prime factor, Prime factorization
language:
Python (cpython 2.7.16)
created:
10 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!