CODEWITHSUNDEEP
python
Legend_recalls
Legend_recalls

Reputation: 273

Input a number and find its factors - wrong answer

I wrote a simple code for to input a number and find its factors and print them:

import math
n=int(input("Enter your number : "))
i=int(math.sqrt(n)+1)
while i !=0:
    if n%i==0:
        print(i)
    i=i-1

but it's not giving me correct answer for some reason.

Output:

Enter your number : 35
5
1

Upvotes: 2

Views: 192

Answers (2)

alani
alani

Reputation: 13079

This will quickly get a list of factors, starting by obtaining a list of prime factors and the power to which each is raised, and then multiplying them together in all combinations. Note that the candidate numbers are not all necessarily prime, but they do include all prime numbers.

import itertools

def gen_candidates():
    yield 2
    yield 3
    c = 0
    while True:
        c += 6
        yield c - 1
        yield c + 1

def gen_prime_factors_with_powers(x):
    for c in gen_candidates():
        if c * c > x:
            yield (x, 1)
            return
        power = 0
        while x % c == 0:
            power += 1
            x //= c
        if power:
            yield (c, power)
            if x == 1:
                break

def product(lst):
    prod = 1
    for item in lst:
        prod *= item
    return prod
    
def get_factors(x):

    factors = [[(pf ** i) for i in range(1 + power)]
               for pf, power in gen_prime_factors_with_powers(x)]
    return sorted([product(lst) for lst in itertools.product(*factors)])

print(get_factors(12345678909876543210))

Obviously if the prime factors are themselves large, then it could still take some time, but it will only search up to the larger of:

  • the second-largest prime factor
  • the square root of the largest prime factor

It does not search up to x, and only in the worst case of a prime number does it search up even to the square root of x.

Upvotes: 0

Legend_recalls
Legend_recalls

Reputation: 273

ok so i am stupid and writing an answer to my own question....

import math
n= 35#int(input("Enter your number : "))
i=int(math.sqrt(n)+1)
while i !=0:
    if n%i==0:
        print(i)
        print(n/i)
    i=i-1

this is actually the most efficient way

Upvotes: 3

Related Questions