Как получить различные множители из списка простых чисел? - PullRequest
Новая
       109

Как получить различные множители из списка простых чисел?

0 голосов
/ 28 мая 2020

Я пробовал задачу 47 (из проекта euler), вопрос приведен ниже:

Первые два последовательных числа, которые имеют два различных простых множителя: 

14 = 2 × 7
15 = 3 × 5

Первые три последовательных числа, у которых есть три различных простых множителя: 

644 = 2² × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19.

Найдите первые четыре последовательных целых числа, у каждого из которых будет четыре различных простых множителя. Какое первое из этих чисел?

Вот мой подход: (вам может потребоваться (pip) установить sympy) 

import time
import sympy

start=time.time()
a=list(sympy.primerange(1,101))

b=[] 

for i in range(646,100000):
    c=[]
    for j in a:
        if i%j==0:
            c.append(j)
            if len(c)==4:
                s=[str(o) for o in c]
                res=int("".join(s))
                b.append(res)
            else:
                pass
        else:
            pass

print(b[:4])
end=time.time()
print(end-start)

Как мне реализовать logi c, что факторы должны быть разными? ответ, который я получаю сейчас (который, очевидно, неверен): 23511 правильный ответ: 134043

простые простые числа бази c функции: https://www.geeksforgeeks.org/prime-functions-python-sympy

Спасибо!

Ответы [ 2 ]

1 голос
/ 28 мая 2020

Ваш res представляет собой конкатенацию факторов, а не произведение 4 чисел, которые делят i поровну. Вместо того, чтобы преобразовывать элементы c в строки и объединять их, попробуйте просто b.append(prod(c)), где вы импортировали prod как from sympy.core.mul import prod. При этом [2, 3, 5, 11] -> 330 вместо 23511.

BTW, len(sympy.factorint(n)) == 4 сообщит вам, имеет ли n 4 различных фактора.

1 голос
/ 28 мая 2020

Хорошо, давайте предположим, что у вас есть функция, которая дает вам простые множители 

def find_4_diff(i):
    fact_i = find_factors(i)
    fact_i_plus_1 = find_factors(i+1)
    if all([f_i not in f_i_plus_1 for i in fact_i]):
        fact_i_plus_2 = find_factors(i+2)
        if all([f_i not in f_i_plus_2 for i in fact_i]) and  all([f_i not in f_i_plus_2 for i in fact_i_plus_1]):
            fact_i_plus_3 = find_factors(i+3)
            if all([f_i not in fact_i_plus_3 for i in fact_i]) and  all([f_i not in fact_i_plus_3 for i in fact_i_plus_1]) and all([f_i not in fact_i_plus_3 for i in fact_i_plus_2]):
                return i
    return 


i = 646
myval = find_4_diff(i)
while  myval is None:
    i += 1
    myval = find_4_diff(i)
print(i)

Теперь вы можете подумать о способах оптимизации: например, вы всегда вычисляете, по крайней мере, множители i + 1, поэтому не нужно сделать это еще раз (cможет передать его в качестве аргумента), если факторы i + 1 недействительны по сравнению с факторами i + 2, вы можете пропустить i + 1 et c et c

Все, что вам нужно, это функция для возврата множителей числа в виде чисел, например от 2 до 3, возвращаемых как 8 et c

...