Сложение простых чисел python

Потому что для определения простоты числа Вы используете факторизацию, а задача факторизации имеет высокую сложность. Думаю, для вашей задачи больше подойдёт Решето Эратосфена. Либо можете попробовать для определения простоты использовать вероятностные алгоритмы (тесты Ферма, Соловея-Штрассена, Люка, Миллера-Рабина), но они вернут вам правильный ответ с некоторой вероятностью (не 100%).

В данном случае с решетом более верный подход - он даст сразу все простые числа, а определение простоты боле выгодно для теста единичного числа или небольшого диапазона

алгоритм нахождения всех простых чисел до некоторого целого числа n, в данном случаем число n - это номер последовательности?

4 ответа 4

Берем функцию, которая возвращает простые числа через Решето Эратосфена, и суммируем их:

def primes(n): """ Returns a list of primes < n """ sieve = [True] * n for i in range(3,int(n**0.5)+1,2): if sieve[i]: sieve[i*i::2*i]=[False]*((n-i*i-1)//(2*i)+1) return [2] + [i for i in range(3,n,2) if sieve[i]] print(sum(primes(2_000_000))) # 142913828922 

UPD. @MaxU предложил использовать оптимизированную версию функции получения простых чисел: https://stackoverflow.com/a/3035188/5909792 . Она выглядит сложно, но в сравнении с предыдущей, она в 16 раз быстрее выдала результат на моей машине.

вашу реализацию можно ускорить минимум на порядок если: 1. сразу исключить все четные числа for i in range(3,int(n**0.5)+1,2) . 2) при нахождении в цикле простого числа вычеркивать все числа кратные данному простому числу используя срезы (пример - функция primes() ) 😉

ага, добавил её в качестве ответа, но с отладочной/дополнительной информацией, чтобы было понятнее как она работает.

Для поиска простых чисел можно воспользоваться решетом Эратосфена, функция взята из ответа на английском StackOverflow

# Функция, реализующая решето Эратосфена def iprimes_upto(limit): is_prime = [True] * limit for n in range(2, limit): if is_prime[n]: yield n for i in range(n*n, limit, n): # start at ``n`` squared is_prime[i] = False # Получаем все простые числа до 2 миллионов primes = list(iprimes_upto(2000000)) print(sum(primes)) # выводим сумму > 142913828922 

@MaxU, честно говоря, я не помнил точно, где взял это код 🙂 Просто в своих примерах на компе нашёл. Спасибо, немного уточнил ответ

def primes(n): """ Returns a list of primes < n """ # (c) Robert William Hanks - https://stackoverflow.com/a/3035188/5741205 sieve = [True] * n print("все чётные числа игнорируются и будут пропущены при возврате. \n") for i in range(3,int(n**0.5)+1,2): if sieve[i]: print('содержимое решета:\t<>'.format([x for x in range(3,n,2) if sieve[x]])) print(f'i: вычёркиваем все числа кратные "", начиная с "^2": ') sieve[i*i::2*i]=[False]*((n-i*i-1)//(2*i)+1) print(f'sieve[*::2*]=[False]*((*)//(2*)+1)') print('содержимое решета:\t<>'.format([x for x in range(3,n,2) if sieve[x]])) print('*' * 60) return [2] + [i for i in range(3,n,2) if sieve[i]] 

In [165]: primes(50) все чётные числа игнорируются и будут пропущены при возврате. содержимое решета: [3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49] i:3 вычёркиваем все числа кратные "3", начиная с "3^2": [9, 15, 21, 27, 33, 39, 45] sieve[3*3::2*3]=[False]*((47*2)//(2*3)+1) содержимое решета: [3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49] ************************************************************ содержимое решета: [3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49] i:5 вычёркиваем все числа кратные "5", начиная с "5^2": [25, 35, 45] sieve[5*5::2*5]=[False]*((45*4)//(2*5)+1) содержимое решета: [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49] ************************************************************ содержимое решета: [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49] i:7 вычёркиваем все числа кратные "7", начиная с "7^2": [49] sieve[7*7::2*7]=[False]*((43*6)//(2*7)+1) содержимое решета: [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47] ************************************************************ Out[165]: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 

Источник

Два простых слагаемых

Два простых
Определите, можно ли представить введённое с клавиатуры число в виде суммы двух различных простых.

Представимо ли данное натурально число в виде суммы двух простых слагаемых
Составить программу, позволяющую выяснить, представимо ли данное натурально число M (M>2) в виде.

Даны два слагаемых которые могут содержать до 50 символов, определить их сумму
Даны два слогаемых которые могут содержать до 50 символов, определить их сумму

Вычисления суммы n слагаемых вида: 2х^3+i, где i=1,2,3. n, а n - количество слагаемых
Написать программу вычисления суммы n слагаемых вида: 2х^3+i, где i=1,2,3. n, а n - количество.

Сообщение было отмечено 4disc0nnect4 как решение

Решение

Добавлено через 55 секунд

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

def isPrime(n): d = 3 while d * d  n and n % d != 0: d += 2 return d * d > n def fun(num) : if not num % 2 : num1 = num2 = num // 2 if not num1 % 2: num1 -= 1 num2 += 1 while num1 > 1 : if isPrime(num1) and isPrime(num2) : return num1, num2 num1 -= 2 num2 += 2 elif isPrime(num - 2) : return 2, num - 2 return [-1] print(*fun(int(input())))

Источник