Created
September 13, 2015 17:22
-
-
Save amitt001/7cc66c3752e721519c84 to your computer and use it in GitHub Desktop.
Prime Factors of a number with sieve of ertosthenes also check if a number is prime or not
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#http://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/ | |
def prime_factors(n): | |
num = [] | |
#add 2 to list or prime factors and remove all even numbers(like sieve of ertosthenes) | |
while(n%2 == 0): | |
num.append(2) | |
n /= 2 | |
#divide by odd numbers and remove all of their multiples increment by 2 if no perfectlly devides add it | |
for i in xrange(3, int(sqrt(n))+1, 2): | |
while (n%i == 0): | |
num.append(i) | |
n /= i | |
#if no is > 2 i.e no is a prime number that is only divisble by itself add it | |
if n>2: | |
num.append(n) | |
print num |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment