Решение Project Euler 46 дает один неверный ответ вместе с правильным ответом - PullRequest
0 голосов
/ 23 мая 2019

Я написал решение для PE # 46 , которое дает мне два ответа: 57 (неправильно) и 5777 (справа).И я действительно изо всех сил пытаюсь понять, почему!Я знаю, что это не самый эффективный код, но если бы я мог понять это, я мог бы сделать его быстрее.Моя функция is_prime() - та, которую я написал для # 7 и которая использовалась для решения ряда других проблем, поэтому я знаю (ну, я уверен;)), что проблема не существует, но я включил ее здесь радиполноты.

from math import sqrt


def is_prime(x):
    if x % 2 == 0:
        return x == 2
    if x % 3 == 0:
        return x == 3

    step = 4
    m = int(sqrt(x)) + 1
    i = 5

    while i < m:
        if x % i == 0:
            return False
        step = 6 - step
        i += step

    return True


def is_composite(n):
    for x in range(2, n):
        for y in range(x, n):
            if x * y == n:
                return True
    return False


def test(n):
    for p in range(3, n):
        if is_prime(p):
            for t in range(1, p // 2):
                if p + (2 * t**2) == n:
                    return True
    return False


# currently this gives 57 (wrong) and also 5777 (right)                                                                                                                                                                                       
i = 33
while True:
    if is_composite(i):
        if not test(i):
            print(i)
    i += 2

Есть мысли?

РЕДАКТИРОВАТЬ: Вот полный текст проблемы по ссылке выше:

Кристиан Голдбах предложил, что каждое нечетное составное число может быть записано как сумма простого идважды в квадрат.

9 = 7 + 2 × 1 ^ 2

15 = 7 + 2 × 2 ^ 2

21 = 3 + 2 × 3 ^ 2

25 = 7 + 2 × 3 ^ 2

27 = 19 + 2 × 2 ^ 2

33 = 31 + 2 × 1 ^ 2

Получается, что гипотеза была ложной.

Какая наименьшая нечетная композиция, которую нельзя записать в виде суммы простого и двойного квадрата?

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...