Как найти сумму простых чисел в питоне

I am Trying this question as an exercise but i am stuck.I will try to be as precise as possible

I would like to find the sum of primes with the list as an input

Say the input given to my function is a list like=[17,51,29,39],so it should return 46 as the answer as 17+29=46

Here’s the code what i could write:

def sumprimes(l):
    sum=0
    for value in l:
        for i in range(1,float((value)/2)):
            if value%i==0:
                      sum+=value     
    print(sum)

Note-on passing a list,the program should work. I haven’t written this part.

Thanks in advance

juanpa.arrivillaga's user avatar

asked Aug 1, 2016 at 17:05

Dhruv Marwha's user avatar

Dhruv MarwhaDhruv Marwha

1,0552 gold badges14 silver badges26 bronze badges

1

You’d better create a function to test if number is prime as @wim said.

def is_prime(n):
    if n < 2:
        return False
    elif n <= 3:
        return True
    elif n % 2 == 0:
        return False

    # round up the sqrt of n
    length = int(n**.5) + 1  # n**.5 is equal to sqrt(n)
    for i in range(3, length, 2):
        if n % i == 0:
            return False

    return True

This is a simple and efficient primality test.
Then you can simply sum with:

def sum_primes(l):
    return sum(n for n in l if is_prime(n))

answered Aug 3, 2016 at 16:12

Carlos Afonso's user avatar

Carlos AfonsoCarlos Afonso

1,8991 gold badge11 silver badges22 bronze badges

2

The problem with your code is that you are using range with float value.
What you really need here is integer division. In Python 3, that is the // operator:

def sum_primes(l):
    total = 0
    for value in l:
        for i in range(2, value // 2):
            if value%i == 0:
                break
        else:
            total += value     
    return total

Also, you need to check if value is divisible by every number except 1 and itself. All numbers will be divisible by 1. So start the range from 2. Furthermore, it is numbers that are divisible that aren’t prime, so add an else clause to your for-loop which is only executed if your for-loop goes to completion without the breaking i.e. none of the numbers you checked divide value, thus value is prime!

answered Aug 1, 2016 at 17:20

juanpa.arrivillaga's user avatar

Here is the solution for your queries

def sumprimes(l):
primeNum = []
for item in l:
    is_prime = True
    if(item >= 2):
        maxInt = int(item ** 0.5) + 1
        for i in range(2, maxInt):
            if(item % i == 0):
                is_prime = False
                break
        if(is_prime):
            primeNum.append(item)
return(sum(primeNum))

print(function([-3,1,6]))

wogsland's user avatar

wogsland

8,97819 gold badges56 silver badges91 bronze badges

answered Feb 2, 2017 at 16:46

user7507118's user avatar

def sumprime(list):
    sum =0
    flag =1
    for i in range(len(list)):
        num = list[i]
        for j in range(2, num):
            if list[i]%j ==0:
                flag = 0
                break
            else:
                flag = 1
        if num ==2:
            flag =1
        if flag ==1:
            sum =sum +list[i]
    return(sum)

list =[2,3,5,7]
print(sumprime(list))

answered Aug 22, 2018 at 11:22

Krishna Soni's user avatar

0

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

def sumprimes(l):
    x = list(filter(prime,l))
    y = sum(x)
    return y
print(sumprimes([-3,3,1,13]))

answered Feb 14, 2019 at 13:20

divya maddipudi's user avatar

1

Источник

Задача 10. Сложение простых чисел

Условие задачи

Сумма простых чисел меньше 10 — это 2 + 3 + 5 + 7 = 17.

Найдите сумму всех простых чисел меньше двух миллионов.

Решение

Мы уже использовали алгоритмы поиска простых чисел на python здесь и здесь. Но в этой задаче я хочу попробовать нечто новое — Решето Эратосфена . Это достаточно интересный и быстрый алгоритм, но я его не использовал в прошлых задачах т.к они не сильно подходили под условия — здесь же решето Эратосфена подходит практически идеально.

На заметку — недавно вычитал из статьи на Хабре, что один известный математик недавно оптимизировал решето Эратосфена. Речь идет о очень существенной экономии памяти — буквально с гигабайта к мегабайту. Если где-то опубликуют его алгоритм обязательно напишу об этом статью.

В данной программе я использовал 2 функции
eratosthen(n) — пропускаем через решето массив от 0 до числа n. Функция создает массив, а затем в цикле заполняем нулями числа согласно правил решета Эратосфена
sum — встроенная функция суммирования списков
Полный текст программы

def eratosthen(n):
    sieve = list(range(n))
    sieve[1] = 0
    for i in sieve[2:]:
            for j in range(i + i, len(sieve), i):
                sieve[j] = 0
    return sieve

print(sum(eratosthen(2000000)))

Задача решена

Популярные сообщения из этого блога

 . Задача №1 Если выписать все натуральные числа меньше 10, кратные 3 или 5, то получим 3, 5, 6 и 9. Сумма этих чисел — 23. Найдите сумму всех чисел меньше 1000, кратных 3 или 5. Решение

Условие задачи Простые делители числа 13195 — это 5, 7, 13 и 29. Каков самый большой делитель числа 600851475143, являющийся простым числом? Решение Простым числом, является натуральное число больше единицы, которое имеет 2 делителя — 1 и само себя.  Для начала найдем все простые делители необходимого числа.  Чтобы сократить поиск будем перебирать до квадратного корня  600851475143 округленного вверх  ( функцией  math.ceil) Перебор будем вести начиная с числа 3. Если i делит число на цело, рекурсивно обращаемся к функции issimple c аргументом i. Функция issimple возвращает пустой список если число является простым. В этом случае число попадает в результирующий список Далее остается только вернуть максимальное значение массива простых чисел, которые нацело делят число 600851475143  Код Python import math def issimple(a): r=math.ceil(math.sqrt(a)) lst=[] for i in range(3,r): if a%i==0: if issimple(i)==[]: lst.app

Условие задачи 2520 — самое маленькое число, которое делится без остатка на все числа от 1 до 10. Какое самое маленькое число  делится нацело  на все числа от 1 до 20? Скажу сразу — не смотря на не большой диапазон чисел условия реализация этой задачи получилась громоздкой и ее выполнение занимает больше всего времени — около 90 с  несмотря на все попытки оптимизации. Решение 

Источник

Вот очень эффективная реализация решета Эратосфена (c) Robert William Hanks — я лишь добавил отладочную информацию:

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:{i} вычёркиваем все числа кратные "{i}", начиная с "{i}^2": {list(range(i*i, n, 2*i))}')
            sieve[i*i::2*i]=[False]*((n-i*i-1)//(2*i)+1)
            print(f'sieve[{i}*{i}::2*{i}]=[False]*(({n-i}*{i-1})//(2*{i})+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]]

Вывод для n=50:

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

Источник

 

 Найти сумму простых чисел на Python

Сообщение11.07.2017, 16:09 


17/03/17
176

Всем привет. Нужно решить задачу.
Сумма простых чисел меньше $10$ $text{~---}$ это $2 + 3 + 5 + 7 = 17$.
Найдите сумму всех простых чисел меньше двух миллионов.

Для решения я использую метод решета Эратосфена(код внизу).

a=2000001
s=list(range(2,a))
s_sum=0
for i in s:
    if i**2<a:        
        k=0
        while k<len(s):
            if s[k]==i:
                k+=1
            elif s[k]%i==0:
                s.remove(s[k])
                k+=1
            else:
                k+=1
    s_sum=s_sum+i
print(s_sum)
 

Этот скрипт не плохо работает для чисел меньших $2cdot 10^4$, но для $2cdot 10^6$ нужно очень долго ждать результата(я не дождался). Как оптимизировать программу?

Профиль  

venco 

Re: Найти сумму простых чисел на Python

Сообщение11.07.2017, 16:25 
Заслуженный участник


04/05/09
4563

Решето Эратосфена работает хорошо, если использовать не список чисел, как у вас, а массив флагов простое/составное, по одному флагу на каждое число. Даже в википедии есть достаточно разумный псевдо-код, используйте его.
В вашем коде медленные операции поиска в списке удаляемых элементов. С массивом это будут элементарные операции выборки по кратным индексам.

Профиль  

guitar15 

Re: Найти сумму простых чисел на Python

Сообщение11.07.2017, 16:41 


17/03/17
176

То есть нужно использовать NumPy

?

Профиль  

venco 

Re: Найти сумму простых чисел на Python

Сообщение11.07.2017, 17:04 
Заслуженный участник


04/05/09
4563

Зачем? Нужен одномерный массив, надеюсь, такие есть в питоне.
Вы вот этот код понимаете: в википедии

Профиль  

guitar15 

 Re: Найти сумму простых чисел на Python

Сообщение11.07.2017, 17:13 


17/03/17
176

нет :oops:

— 11.07.2017, 18:18 —

Я не знаю, как создать массив (в python отсутствуют массивы. Вместо них для хранения однородных (и не только) объектов используются списки. )

Профиль  

Pphantom 

Re: Найти сумму простых чисел на Python

Сообщение11.07.2017, 18:08 
Заслуженный участник


09/05/12
25191

То есть нужно использовать NumPy?

В общем-то да. Или не Python, если это допустимо.

Профиль  

mihaild 

Re: Найти сумму простых чисел на Python

Сообщение11.07.2017, 18:13 
Заслуженный участник
Аватара пользователя


16/07/14
7085
Цюрих

в python отсутствуют массивы. Вместо них для хранения однородных (и не только) объектов используются списки

То, что в питоне называется list — и есть массив (в динамически типизированных языках).
Еще есть модуль array для типизированных массивов, они побыстрее. Но в данном случае непринципиально.

Профиль  

Aritaborian 

Re: Найти сумму простых чисел на Python

Сообщение12.07.2017, 13:49 

Аватара пользователя


11/06/12
10363
стихия.вздох.мюсли

guitar15

, позвольте полюбопытствовать, задачу нашли на Project Euler

?

Профиль  

guitar15 

Re: Найти сумму простых чисел на Python

Сообщение12.07.2017, 14:32 


17/03/17
176

Профиль  

guitar15 

Re: Найти сумму простых чисел на Python

Сообщение12.07.2017, 15:41 


17/03/17
176

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

Профиль  

Dmitriy40 

Re: Найти сумму простых чисел на Python

Сообщение12.07.2017, 15:58 
Заслуженный участник


20/08/14
10234
Россия, Москва

Для чисел до 2 миллионов можно не связываться с решетом (раз уж не понимаете его), сделать проверку каждого нечётного числа на простоту делением на все простые до корня из проверяемого числа. При нахождении нового простого числа добавлять его в список проверочных (если его квадрат меньше 2 миллионов) и добавлять его к сумме. Всё. Понадобится не более 223 миллионов делений (даже заметно меньше), это пара секунд, остальные операции ещё быстрее (проход списка подряд вперёд не медленнее прямого обращения в массив).

Профиль  

guitar15 

 Re: Найти сумму простых чисел на Python

Сообщение12.07.2017, 16:28 


17/03/17
176

У меня получился такой код (если я вас правильно понял), но время работы составляет 4 минуты.

s=[]
s_sum=0
n=2
while n<=2000000:
    k=2
    while k<=n**0.5:
        if n%k==0:
            n+=1
            k=2
        else:
            k+=1
    s.append(n)
    sum=s_sum+n
    s_sum=sum
    n+=1
print(sum)
 

Профиль  

mihaild 

Re: Найти сумму простых чисел на Python

Сообщение12.07.2017, 16:49 
Заслуженный участник
Аватара пользователя


16/07/14
7085
Цюрих

guitar15

, попробуйте перебирать не все k, а только уже найденные простые. Еще полученный код может неправильно работать для точных квадратов (вещественный корень может оказаться чуть меньше правильного значения). Ну и вместо сложной логики «на каждой итерации ищем следующее простое» можно сделать гораздо проще «проверяем, является ли текущее число простым» (т.е. n внутри цикла по k не менять — и вообще по нему сделать for n in range(2, 2*10^6)).

Профиль  

Dmitriy40 

Re: Найти сумму простых чисел на Python

Сообщение12.07.2017, 16:55 
Заслуженный участник


20/08/14
10234
Россия, Москва

Нет необходимости вычислять корень для каждого прохода цикла по k, достаточно запустить цикл прохода по всему накопленному массиву s, ведь там именно нужные числа и есть. А вот добавлять туда числа не все найденные, а лишь если их квадрат меньше 2 миллионов. У Вас основные тормоза в операции извлечения корня. Плюс проход по k должен идти не по всем числам подряд, а лишь по числам из списка s, это вшестеро ускорит программу.
Плюс ускорить вдвое можно если n начинать с 3 и увеличивать на 2, ведь проверять чётные числа (кроме 2) нет смысла.
В итоге ускорение будет минимум 12 раз, а на самом деле раз 30-50 (возведение в степень 0.5 медленнее деления).
Чем отличаются переменные sum и s_sum до меня не доходит.

Профиль  

Dmitriy40 

 Re: Найти сумму простых чисел на Python

Сообщение12.07.2017, 18:05 
Заслуженный участник


20/08/14
10234
Россия, Москва

Аналог Вашего кода на дельфи (паскале) выполняется 1.5 секунды (причём сумма неправильная!), после предложенных модификаций время 0.18 секунды, ускорение больше 8-ми раз, значит можно ожидать времени в полминуты на питоне. Решето Эратосфена без всяких оптимизаций выполняется за 0.06 секунды, ещё втрое быстрее. Ну и «скорость» питона видно. :-(
Для проверки: правильная сумма равна $142913828922$.

— 12.07.2017, 18:39 —

Ещё пара цифр, для чисел до 20 миллионов время выполнения программы (Ваша : оптимизированная : решето): 33с : 3.1с : 0.42с.
До 200 миллионов (аналогично): 894с : 62с : 4.9с.

Профиль  

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы

Источник

0 / 0 / 0

Регистрация: 06.12.2018

Сообщений: 34

1

Найти сумму простых чисел в списке

10.12.2018, 21:20. Показов 7654. Ответов 4

Студворк — интернет-сервис помощи студентам

Дан список состоящий из чисел.Найти сумму простых чисел в списке.



0

1303 / 843 / 409

Регистрация: 12.03.2018

Сообщений: 2,305

11.12.2018, 09:02

2

Пишите функцию проверки числа на простоту, которая вернет логическое значение (ищите на форуме).
Затем используете функцию sum, параметром которой будет является результат функции filter. Описание каждой функции можно найти в интернете.



0

Viktorrus

1728 / 967 / 199

Регистрация: 22.02.2018

Сообщений: 2,694

Записей в блоге: 6

11.12.2018, 15:11

3

Учел рекомендации ioprst, что бы код был компактнее:

Python 
1
2
3
4
5
6
7
8
9

import math
L = [55, 32, 128, 71, 9, 5, 11]
def is_prime1(n):
    for i in range(2, int(math.sqrt(n) + 1)):
        if n % i == 0: 
            return False
    return n > 1
S = sum(filter(is_prime1, L))
print(S)

здесь простые числа 71, 5, 11
сумма равна 87



0

0 / 0 / 0

Регистрация: 06.12.2018

Сообщений: 34

13.12.2018, 20:25

 [ТС]

4

Спасибо большое



0

Эксперт Python

4607 / 2028 / 359

Регистрация: 17.03.2012

Сообщений: 10,086

Записей в блоге: 6

14.12.2018, 11:31

5

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



0
Источник

Понравилась статья? Поделить с друзьями:
  • Как составить модель клетки
  • Как найти базу данных exe
  • Как найти центр гиперболы по каноническому уравнению
  • Как узнать хозяина айфона если нашли
  • Как найти стоимость произведенного товара