Spread a number into prime factors

This task is called factorization of integers

One of the implementations (taken from OEIS # A238724 ):

 def primfacs(n): i = 2 primfac = [] while i * i <= n: while n % i == 0: primfac.append(i) n = n / i i = i + 1 if n > 1: primfac.append(n) return primfac 

There are two essential points in the code, because of which it searches for all dividers instead of factorization. I’ll add one more change for the sake of optimization and I’ll get this code:

http://ideone.com/qi60fH

 import math number=int(input()) for i in range(2, int(math.sqrt(number)) + 1): # обычно делитель не будет больше корня while (number % i == 0): # while, а не if print(i) number //= i # убираем множитель из числа if (number != 1): # но один делитель может быть больше корня print (number) 

PS: But in general, the variant with the cycle from the next answer is better.

Look, for example, as done here . There are more complex and effective methods . And also pay attention to the sieve of Eratosthenes ( here ). If you want to get factorization not for one number, but for a large set of numbers, then it is more profitable to use brute force by simple. I will tell about it below.

In addition, I think you meant that you want to decompose a number into prime factors, right? I judge by your comment about the correct answer:

 7 = [63, 3, 21, 3, 7] А должно: 63 = 3 * 3 * 7 

Although, the lines are:

 if n > 1: factors.append(n) else: break 

They say that you are trying to look for all dividers.

In this case, you need to write the correct title of the question, so as not to embarrass people.

About your decision. I do not understand why you are adding the current divider to the final list. This is incorrect, since only simple numbers should be added to the final list, and the current divisor is obviously not simple. So the lines are:

 if n > 1: factors.append(n) else: break 

superfluous.

In order to get all the dividers, you need to slightly modify your algorithm:

 #!/usr/bin/env python3 n = int(input("Integer: ")) factors = [] d = 2 m = n # Запомним исходное число while d * d <= n: if n % d == 0: factors.append(d) n//=d else: d += 1 factors.append(n) # Добавим последнеё простое число print('{} = {}' .format(m, factors)) # Выводим исходное число и все простые множители. 

Now about the precondition with prime numbers. It is easy to understand that since we know all the primes, it is more advantageous not to go over those elements that are in themselves the product of primes. Those. we will go through only the numbers:

 2, 3, 5, 7, 11, 13 ... 

The numbers are the same:

 4, 6, 8, 9, 10, 12 ... 

leave alone, as they are the product of the simple. For this, using the sieve of Eratosthenes, we can calculate in advance all the simple ones up to a certain limit ( 2 ^ 64 ). After that, we will decompose the number obtained from the input line for factorization in a simple way as follows. Divide the number n until it is divisible by the i -th prime. All simple will be recorded in factors . As soon as the number ceases to be divided by the i th, we take the i+1 th number. And so on, as long as n != 1 .

I hasten to note that the storage of prime numbers, of course, is expensive. BUT! For most tasks, it is very suitable, since it is not necessary to calculate prime numbers above 100000000 . RAM modern PCs more than allows you to store 1ГБ or more data. There are not too many prime numbers. According to one fairly well-known prime numbers theorem , they turn out to be of order n/ln(n) with increasing n . This means that for 100000000 there will be about 5,3 млн , which is quite a valid one. Moreover, even 1 млрд. numbers can withstand the average PC, since there will be no more than 50 млн simple numbers. So, for memory, it will be 50 млн . 4-байтовых numbers, i.e. 200000000 байт . In megabytes it is only 200 . So there is no big problem in storage.

 def factors(num, d=2): while num > 1: n1, n2 = divmod(num, d) if n2: d += 1 else: yield d num = n1 n = int(input("Integer: ")) print('{} = {}' .format(n, ' * '.join(map(str, factors(n))))) >>> Integer: 63 >>> 63 = 3 * 3 * 7 

 num = int(input()) list_simple = [] simple = 2 while num > 1: if num % simple == 0: list_simple.append(simple) num = num/simple else: simple += 1 print(list_simple)