Finding prime divisors from a given integer

Question

I have to find all the divisors of a given integer, and from all those divisors I have to find the prime numbers and put them in a list from lowest to highest.

This is what I have so far:

def prime_divisors(n): 
    j = 2
    list1 = []
    prime_list = []
    for i in range(2,n+1):
            if n%i == 0:
                if i==2 or i==3:
                    prime_list.append(i)
                elif i%j == 0:
                    for j in range(2,n+1,2):
                        list1.append(j)
            elif n%2 == 1 or n%3 == 1:
                prime_list.append(n)
                return prime_list
    return prime_list
prime_divisors(12)

You really need to give more information here. What is currently not working out for you. Are you getting any errors? If so, give the traceback. — idjaw, Mar 07 '16 at 03:02
When I run it through some test cases. I don't get any errors. Its just that I am not getting all the prime numbers from a given integer. For instance, I believe I am getting the prime numbers for 12. But for integers like 15 or 28, or one of the test cases involves 1225, I am not getting all the prime numbers. Really need help with that. Sorry about that I did forget to include j, but I edited it. — brian012, Mar 07 '16 at 03:16
Basically the example of 12 I would need to get multiplies of 12 that evenly divide into 12, such as 2,3,4,6 and 12 would be my divisors and from those I need to find my prime numbers which would be 2 and 3. I would return those prime numbers in a list. — brian012, Mar 07 '16 at 05:02
Since a prime factor can occur multiple times, you should remove it as much as you can when it is present. For example, 800=2*2*2*2*2*5*5. Start by testing with i=2, then with i=3, and so on (you do that with `for i in range(2,n+1)`). Use a `while n%i==0` instead of a `if n%i ==0`. Remove the `if i==2 or i==3` since it prevents checking for prime divisors other than 2 or 3. — Sci Prog, Mar 07 '16 at 05:07

score 0 · Answer 1 · edited May 23 '17 at 12:23

0

Your test to check if the divisor is prime is incorrect. The error seems to be at the elif i%j == 0: section. Also, what happens to list1?

Linked are questions regarding prime testing: answer1 answer2. The one I picked below may not be the most efficient, but works.

from math import sqrt; from itertools import count, islice    
def is_prime(n):
    return n > 1 and all(n%i for i in islice(count(2), int(sqrt(n)-1)))

def prime_divisors(n): 
    prime_list = []
    search_list = range(2, n/2 +1) # search only to n/2
    search_list.append(n) # also check n 

    for i in search_list:
        if n%i == 0:
        # i has been found to evenly divide input number n
        # now determine if it is prime
            if is_prime(i):
                prime_list.append(i)
    return prime_list

edited May 23 '17 at 12:23

Community

1
1

answered Mar 07 '16 at 04:15

ljk07

952
5
13

is there a way you can do this without using built in functions, I'm only allowed to use if else statements, for loops and appending in a list. I understand your code but I can't use those functions, which makes it a little bit harder to code. – brian012 Mar 07 '16 at 04:39
Please see the links for alternative approaches for prime testing. – ljk07 Mar 07 '16 at 04:47

score 0 · Answer 2 · answered Mar 07 '16 at 08:00

You could use this:

def prime_divisors(n):  
prime_list = []
if n%2==0:
    prime_list.append(2)
for i in range(3,n):
    if n%i==0:          
        for j in range(2,i):
            if i%j==0:
                break
            if j<i-1:
                continue
            prime_list.append(i)
if len(prime_list)==0:
    prime_list.append(n)
return prime_list

Valid input are only whole numbers greater than 1, and, is pretty inefficient.

Finding prime divisors from a given integer

2 Answers2