check prime factors of a number

Question

Here I meet a problem to check the factors of a prime number

# using python2.7.10
from math import sqrt
def isprime(x):
    if x == 1:
        return False
    k = int(sqrt(x))
    for j in range(2,k+1):
        if x%j == 0:
            return False
        return True
num = input("please input a number:")
for i in range(2, num):
    if i!= num and num % i == 0:
        print i,

If I input a number 45, it prints out 3,5,9,15. However, 3 is a factor of 9 and 15, 5 is a factor of 15. I hope the results are 3, 5. How can I change my code in order to achieve my goal?

Answer 1

You just need to move the return True out of the loop, so you check all numbers for 2 - k :

from math import sqrt

def isprime(x):
    if x == 1:
        return False
    k = int(sqrt(x))
    for j in range(2,k+1):
        if x % j == 0:
            return False
    return True # if you get here, you have checked all 2-k

num = int(raw_input("please input a number:"))
for i in range(2, num):
     if isprime(i) and num % i == 0:
        print(i,)

You return True anytime that if x % j == 0 has a remainder so you don't check x against all the numbers. Also, don't use input to take user-input, use raw_input casting to int i.e num = int(raw_input()).

A more efficient way to do what to you want is here

Answer 2

Try This, It will help you to get your ans:

def isprime(x):
    if x >= 2:       
        for k in range(2,x):
            if x%k==0:
                return False
        return True
    else:
        return False 


num = input("please input a number:")
factor=[]
prime_factor=[]
for i in range(2, num):
    if num % i == 0:
        factor.append(i)

for k in factor:    
    if isprime(k):        
        prime_factor.append(k)

print 'Factors',factor
print 'Prime Factors',prime_factor

Output--

please input a number:45
Factors [3, 5, 9, 15]
Prime Factors [3, 5]

Answer 3

def isPrime(n):
isDivisible = False
i=2
while i<n:
    if n%i == 0:
        isDivisible = True
    i += 1
if isDivisible == False:
    return True
    #print(n," is a prime number!")
else: 
    return False
    #print(n,: is not a prime number!")


import pdb    
def primeFactors(n):
lst = []

while n>1:
    #pdb.set_trace()
    for i in range(2,n+1):
        if isPrime(i) and (n%i==0):
            #pdb.set_trace()
            lst.append(i)
            n = n//i
return lst


  
x = int(input("Enter a number: "))
print("The Prime Factors of the entered number are: ",primeFactors(x))

        

Answer 4

Here is the code to check prime or not . You can modify as you wish

prime_numbers = 0

def is_prime_number(x):
    if x >= 2:
        for y in range(2,x):
            if not ( x % y ):
                return False
    else:
    return False
    return True


for i in range(int(raw_input("How many numbers you wish to check: "))):
    if is_prime_number(i):
        prime_numbers += 1
        print i

print "We found " + str(prime_numbers) + " prime numbers."

Answer 5

Just to build slightly on vikram singh chandel's answer, this is a shorter solution that avoids the double for loop in the end. We only need to append factors that are primes:

EDIT: Minor change to cover for entering a prime number directly.

def isprime(x):

    if x < 2:
        return False

    for k in range(2, x):
        if x % k == 0:
            return False

    return True


num = input("please input a number:")

factors = []
for i in range(1, num + 1):
    if num % i == 0 and isprime(i):
        factors.append(i)

print 'Factors:', factors