Удаление кратных числа из списка в Python

Question

Я новичок в Python, и я работаю над программой, которая находит главные факторы числа. Мой код до сих пор выглядит следующим образом:

num = int(input('\nEnter a natural number greater than 1: '))
if num <= 1:
    while num <= 1:
        num = int(input('\nI said greater than 1: '))
if num == 2:
    print('\n', num, 'is a prime number.')
else:
    toggle = 0
    flist = []
    for i in range(2, num - 1):
        if num % i == 0:
            flist.append(i)
            toggle = 1
    if toggle == 0:
        print('\n', num, 'is a prime number.')
    if toggle == 1:
        print('\n', num, 'is not a prime number.')
        print('\nIt\'s prime factors are:', flist)

Например, при вводе 30 я получаю следующий вывод:

Enter a natural number greater than 1: 30

30 is not a prime number.

It's prime factors are: [2, 3, 5, 6, 10, 15]

Основные факторы в этом случае 2, 3, 5. Как я могу удалить их кратные? Спасибо.

Answer 1

Я бы определил дополнительную функцию для проверки, является ли число простым

def is_prime(n):
    if n>1:
        for i in range(2,n):
            if (n % i)==0:
                return False
    return True

Тогда я бы использовал его внутри вашего кода, чтобы проверить, является ли число простым, прежде чем добавить его в окончательный список простых факторы.

num = int(input('\nEnter a natural number greater than 1: '))
if num <= 1:
    while num <= 1:
        num = int(input('\nI said greater than 1: '))
if num == 2:
    print('\n', num, 'is a prime number.')
else:
    toggle = 0
    flist = []
    for i in range(2, num - 1):
        if num % i == 0:
            if is_prime(i):   # append only prime numbers
                flist.append(i)
            toggle = 1
    if toggle == 0:
        print('\n', num, 'is a prime number.')
    if toggle == 1:
        print('\n', num, 'is not a prime number.')
        print('\nIt\'s prime factors are:', flist)

Это дает правильный вывод:

Enter a natural number greater than 1: 30

 30 is not a prime number.

It's prime factors are: [2, 3, 5]

Answer 2

Вы получаете кратные вашим основным факторам, таким как 6 = 2 × 3, 10 = 2 × 5 и 15 = 3 × 5.

Чтобы избежать этого, вы должны разделить свое первоначальное число на простые факторы, как вы находите их, так что он не будет делиться снова на кратные эти простые факторы.

Кроме того, вы должны делать это многократно, так как числа часто имеют показатель простого фактора (для например, 12 = 2² × 3, поэтому вы должны разделить на 2 дважды.)

for i in range(2, num):
    while num % i == 0:
        flist.append(i)
        num = num // i
    if num == 1:
        break

Когда вы доберетесь до 1, вы знаете, что можете остановиться.

Есть и другие оптимизации, которые вы например, когда i² больше num, вы знаете, что num должно быть простым числом, поскольку вы уже поделили его на все факторы, меньшие i.

Вы также можете пропустить четные числа после 2, так как они будут никогда не будьте факторами.

Используя простой код выше, вы будете знать, что num - это простое число, когда flist пуст. (Вам не нужен дополнительный переключатель для отслеживания этого.) Это работает, так как вы никогда не делите на само num, поэтому, если вы дойдете до конца и не делите один раз, это означает, что это простое число.

Для числа, такого как 12, у вашего флиста будет [2, 2, 3]. Если вам нужны уникальные простые множители без повторений, вы можете использовать set(flist), чтобы избавиться от дубликатов.

Answer 3

Вот решение, использующее Сито Эратосфена, чтобы сначала найти все простые числа ниже N, а затем go через них, чтобы найти все простые факторы, это должно быть довольно эффективно

import numpy as np

def findSieve(num):
    allN = np.arange(1,num+1,1)
    mask = allN == allN
    maskN = np.ma.MaskedArray(allN)
    p = 2

    while maskN[p:].count() > 0:
        mask = mask & ((allN%p != 0) | (allN <= p))
        maskN = np.ma.MaskedArray(maskN, mask =~ mask)
        p = maskN[p:].min()

    return np.asarray(maskN[maskN.mask == False])

def findPrimeFactors(num):        
    sieve = findSieve(num)
    flist = []
    num_factored = num
    for i in range(1,len(sieve)) :
        while num_factored % sieve[i] == 0:
            flist.append(sieve[i])
            num_factored = num_factored // sieve[i]
            if num_factored == 1:
                break

    prime = len(flist) == 1
    if prime:
        print('\n', num, 'is a prime number.')
    else:
        print('\n', num, 'is not a prime number.')
        print('\nIt\'s prime factors are:', flist)


num = int(input('\nEnter a natural number greater than 1: '))
findPrimeFactors(num)