Как найти сумму простых чисел в интервале - Сайт, где вы сможете решить свои вопросы

Improve Article

Save Article

Like Article

Read

Discuss

Improve Article

Save Article

Like Article

Given a range [l, r], the task is to find the sum of all the prime numbers within that range.

Examples:

Input : l=1 and r=6
Output : 10
Input : l=4 and r=13Output : 36

Approach 1: (Naive Approach)
Iterate the loop from ‘l’ to ‘r’ and add all the numbers which are prime.

Below is the implementation of the above approach:

C++

#include <iostream>

using namespace std;

bool checkPrime(int numberToCheck)

{

if(numberToCheck == 1) {

return false;

}

for (int i = 2; i*i <= numberToCheck; i++) {

if (numberToCheck % i == 0) {

return false;

}

return true;

}

int primeSum(int l, int r)

{

int sum = 0;

for (int i = r; i >= l; i--) {

bool isPrime = checkPrime(i);

if (isPrime) {

sum = sum + i;

}

return sum;

}

int main()

{

int l = 4, r = 13;

cout << primeSum(l, r);

}

Java

public class GFG {

static boolean checkPrime(int numberToCheck)

{

if(numberToCheck == 1) {

return false;

}

for (int i = 2; i*i <= numberToCheck; i++) {

if (numberToCheck % i == 0) {

return false;

}

return true;

}

static int primeSum(int l, int r)

{

int sum = 0;

for (int i = r; i >= l; i--) {

boolean isPrime = checkPrime(i);

if (isPrime) {

sum = sum + i;

}

return sum;

}

public static void main(String[] args)

{

int l = 4, r = 13;

System.out.println(primeSum(l, r));

}

Python 3

from math import sqrt

def checkPrime(numberToCheck) :

if numberToCheck == 1 :

return False

for i in range(2, int(sqrt(numberToCheck)) + 1) :

if numberToCheck % i == 0 :

return False

return True

def primeSum(l, r) :

sum = 0

for i in range(r, (l - 1), -1) :

isPrime = checkPrime(i)

if (isPrime) :

sum += i

return sum

if __name__ == "__main__" :

l, r = 4, 13

print(primeSum(l, r))

C#

using System;

class GFG

{

static bool checkPrime(int numberToCheck)

{

if(numberToCheck == 1)

{

return false;

}

for (int i = 2;

i * i <= numberToCheck; i++)

{

if (numberToCheck % i == 0)

{

return false;

}

return true;

}

static int primeSum(int l, int r)

{

int sum = 0;

for (int i = r; i >= l; i--)

{

bool isPrime = checkPrime(i);

if (isPrime)

{

sum = sum + i;

}

return sum;

}

public static void Main()

{

int l = 4, r = 13;

Console.Write(primeSum(l, r));

}

PHP

<?php

function checkPrime($numberToCheck)

{

if($numberToCheck == 1)

{

return false;

}

for ($i = 2; $i * $i <= $numberToCheck; $i++)

{

if ($numberToCheck % $i == 0)

{

return false;

}

return true;

}

function primeSum($l, $r)

{

$sum = 0;

for ($i = $r; $i >= $l; $i--)

{

$isPrime = checkPrime($i);

if ($isPrime)

{

$sum = $sum + $i;

}

return $sum;

}

$l = 4; $r = 13;

echo primeSum($l, $r);

?>

Javascript

<script>

function checkPrime(numberToCheck)

{

if(numberToCheck == 1)

{

return false;

}

for (let i = 2; i * i <= numberToCheck; i++)

{

if (numberToCheck % i == 0)

{

return false;

}

return true;

}

function primeSum(l, r)

{

let sum = 0;

for (let i = r; i >= l; i--)

{

let isPrime = checkPrime(i);

if (isPrime)

{

sum = sum + i;

}

return sum;

}

let l = 4, r = 13;

document.write(primeSum(l, r));

</script>

Time Complexity:
Auxiliary Space:

Approach 2: (Dynamic Programming)

Declare an array dp and arr
Fill the array arr to 0
Iterate the loop till sqrt(N) and if arr[i] = 0 (marked as prime), then set all of its multiples as non-prime by marking the respective location as 1
Update the dp array with the running prime numbers sum, where each location ‘dp[i]’ holds the sum of all the prime numbers within the range [1, i]

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

const int N = 1000;

int dp[N + 1];

void sieve()

{

int arr[N + 1];

arr[0] = 1;

arr[1] = 1;

for (int i = 2; i <= sqrt(N); i++)

if (arr[i] == 0)

for (int j = i * i; j <= N; j += i)

arr[j] = 1;

long runningPrimeSum = 0;

for (int i = 1; i <= N; i++)

{

if (arr[i] == 0)

runningPrimeSum += i;

dp[i] = runningPrimeSum;

}

int main()

{

int l = 4, r = 13;

sieve();

cout << dp[r] - dp[l - 1];

return 0;

}

Java

public class GFG {

static int N = 1000;

static long dp[] = new long[N + 1];

static void sieve()

{

int arr[] = new int[N + 1];

arr[0] = 1;

arr[1] = 1;

for (int i = 2; i <= Math.sqrt(N); i++)

if (arr[i] == 0)

for (int j = i * i; j <= N; j += i)

arr[j] = 1;

long runningPrimeSum = 0;

for (int i = 1; i <= N; i++) {

if (arr[i] == 0)

runningPrimeSum += i;

dp[i] = runningPrimeSum;

}

public static void main(String[] args)

{

int l = 4, r = 13;

sieve();

System.out.println(dp[r] - dp[l - 1]);

}

Python 3

import math

N = 1000

dp = [0] * (N + 1)

def sieve():

array = [0] * (N + 1)

array[0] = 1

array[1] = 1

for i in range(2, math.ceil(math.sqrt(N) + 1)):

if array[i] == 0:

for j in range(i * i, N + 1, i):

array[j] = 1

runningPrimeSum = 0

for i in range(1, N + 1):

if array[i] == 0:

runningPrimeSum += i

dp[i] = runningPrimeSum

l = 4

r = 13

sieve()

print(dp[r] - dp[l - 1])

C#

using System;

public class GFG {

static int N = 1000;

static long[] dp = new long[N + 1];

static void sieve()

{

int []arr = new int[N + 1];

arr[0] = 1;

arr[1] = 1;

for (int i = 2; i <= Math.Sqrt(N); i++)

if (arr[i] == 0)

for (int j = i * i; j <= N; j += i)

arr[j] = 1;

long runningPrimeSum = 0;

for (int i = 1; i <= N; i++) {

if (arr[i] == 0)

runningPrimeSum += i;

dp[i] = runningPrimeSum;

}

public static void Main()

{

int l = 4, r = 13;

sieve();

Console.WriteLine(dp[r] - dp[l - 1]);

}

Javascript

<script>

let N = 1000;

let dp=new Array(N+1);

for(let i=0;i<dp.length;i++)

{

dp[i]=0;

}

function sieve()

{

let arr=new Array(N+1);

for(let i=0;i<arr.length;i++)

{

arr[i]=0;

}

arr[0] = 1;

arr[1] = 1;

for (let i = 2; i <= Math.ceil(Math.sqrt(N)+1); i++)

if (arr[i] == 0)

for (let j = i * i; j <= N; j += i)

arr[j] = 1;

let runningPrimeSum = 0;

for (let i = 1; i <= N; i++) {

if (arr[i] == 0)

runningPrimeSum += i;

dp[i] = runningPrimeSum;

}

let l = 4, r = 13;

sieve();

document.write(dp[r] - dp[l - 1]);

</script>

Time Complexity: O(n*log(log(n)))
Auxiliary Space:

Last Updated :
17 Nov, 2022

Like Article

Save Article

Источник

Введите два числа a, b и найдите сумму всех простых чисел в диапазоне от a до b.
Идея:
Сначала поговорим об определении простых чисел:
Простое число также называется простым числом, натуральным числом больше 1, за исключением 1 и самого себя; число, которое не может делиться на другие натуральные числа, называется простым числом; в противном случае оно называется составным числом. Итак, 1 – не простое число. Количество простых чисел бесконечно.
проанализировать идеи;
Поскольку у простого числа есть только два делителя: 1 и само себя, то есть если вы используете каждое число в диапазоне от 2 до самого себя (не включая себя) в качестве делителя, то результатом будет остаток Если это так, то результат не будет равен 0.
Определите, является ли число простым числом, разделите число на 2 на предыдущее число числа, то есть возьмите остаток от каждого числа в диапазоне (2, число), если результат не 0 – простое число (также называемое простым числом)
Процедура:

lst = [] # Создать пустой список для всех простых чисел
 first = int (input ('Пожалуйста, введите минимальное значение интервала:'))
 end = int (input ('Пожалуйста, введите максимальное значение интервала:'))
total = 0
for num in range(first, end + 1):
         если num> 1: # 1 не является индексом, удалите 1
                 for i in range (2, num): # пройти по числам, кроме 1 и самого себя как делителя
                         if num% i == 0: # Если num делится на i, а остаток равен 0, это не простое число (простое число)
                break
                 else: # Здесь используется структура for ... else. Если остаток результата не равен 0, то это простое число
            lst.append(num)
            total += num
print(lst)
print(total)

результат операции:

Пожалуйста, введите минимальный интервал: 1
 Пожалуйста, введите максимальное значение интервала: 10
[2, 3, 5, 7]
17

Источник

No Namer

0 / 0 / 0

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

Сообщений: 2

Сумма всех простых чисел в заданном диапазоне

15.09.2022, 10:41. Показов 559. Ответов 3

Метки с# (Все метки)

Приветствую! Буду благодарен за помощь в решении задачи которую пытаюсь решить долгое время:/ Условие задания: найти сумму всех простых чисел в заданном диапазоне с помощью циклов. Язык программирования С#.

Вот моя попытка решить задачу:

using System;
 
public class MainClass
{
    public static void Main()
    
    {
        int startValue = int.Parse(Console.ReadLine());
        int endValue = int.Parse(Console.ReadLine());
        
 
 
        int sum = 0;
        for (int i = startValue; i <= endValue; i++)
        {
            for (int j = 2; j <= (int)(endValue / 2); j++)
            {
                if (endValue % j == 0)
                    break;
            }
            sum += endValue;
        }
 
        Console.WriteLine(sum);  
    }
}

iLinks

572 / 382 / 212

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

Сообщений: 1,056

15.09.2022, 11:28

private static bool IsPrime(int number)
{
    for (int i = 2; i < number; i++)
    {
        if (number % i == 0)
            return false;
    }
    return true;
}
static void Main(string[] args)
{
    int startValue = int.Parse(Console.ReadLine());
    int endValue = int.Parse(Console.ReadLine());
    int sum = 0;
    Console.WriteLine($"Простые числа из диапазона [{startValue},{endValue}]:");
    for (int i = startValue; i <= endValue; i++)
    {
        if (IsPrime(i))
        {
            Console.Write(i + " ");
            sum += i;
        }
    }
    Console.WriteLine();
    Console.WriteLine(sum);
    Console.ReadLine();
}

Элд Хасп

Модератор

13780 / 9992 / 2661

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

Сообщений: 29,763

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

15.09.2022, 11:36

Сообщение от No Namer

Вот моя попытка решить задачу:

Для решения “в лоб” сначала создайте статический метод bool IsPrime(int), который будет возвращать true для простого числа.
И уже после используйте его в цикле по диапазону – суммируйте только те которые прошли через этот метод.

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

Сообщение от iLinks

bool IsPrime(int number)

Пока писал ответ, вы уже решение сбросили.

Добавлено через 2 минуты

Сообщение от iLinks

3	for (int i = 2; i < number; i++)

Чуть по другому:

3	for (int i = 2; i*i <= number; i++)

Добавлено через 2 минуты
No Namer, для больших диапазонов такая реализация будет работать крайне медленно.
Нужно делать через алгоритм “Решето Эратосфена”.

0 / 0 / 0

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

Сообщений: 2

16.09.2022, 07:55

[ТС]

Огромное спасибо за вашу помощь в решении и объяснении решения!

Источник

Простое число — это натуральное число, которое больше 1 и не имеет положительного делителя, кроме 1 и самого себя, например 2, 3, 5, 7, 11, 13 и так далее.

Пользователю даются два целых числа, нижнее значение и верхнее значение. Задача состоит в том, чтобы написать программу Python для вывода всех простых чисел в заданном интервале (или диапазоне).

Чтобы напечатать все простые числа в заданном интервале, пользователь должен выполнить следующие шаги:

Шаг 1: Переберите все элементы в заданном диапазоне.
Шаг 2: Проверьте для каждого числа, есть ли у него какой-либо множитель между 1 и самим собой.
Шаг 3: Если да, то число не простое, и оно перейдет к следующему числу.
Шаг 4: Если нет, то это простое число, и программа распечатает его и проверит следующее число.
Шаг 5: Цикл прервется, когда будет достигнуто верхнее значение.

Пример: код Python для печати простого числа в заданном интервале.

 
# First, we will take the input: 
lower_value = int(input("Please, Enter the Lowest Range Value: ")) 
upper_value = int(input("Please, Enter the Upper Range Value: ")) 
 
print("The Prime Numbers in the range are: ") 
for number in range(lower_value, upper_value + 1): 
    if number > 1: 
        for i in range(2, number): 
            if(number % i) == 0: 
                break 
        else: 
            print(number)

Выход:

Please, Enter the Lowest Range Value:  14 
Please, Enter the Upper Range Value:  97 
The Prime Numbers in the range are:  
17 
19 
23 
29 
31 
37 
41 
43 
47 
53 
59 
61 
67 
71 
73 
79 
83 
89 
97

Заключение

В этом уроке мы показали, как написать код для печати простых чисел в заданном диапазоне чисел.

Изучаю Python вместе с вами, читаю, собираю и записываю информацию опытных программистов.

Источник

Найдите сумму простых чисел, расположенных в интервале от числа 256 до числа 16384 включительно.

В ответе запишите одно целое число.

Вы открыли страницу вопроса Найдите сумму простых чисел, расположенных в интервале от числа 256 до числа 16384 включительно?. Он относится к категории
Информатика. Уровень сложности вопроса – для учащихся 5 – 9 классов.
Удобный и простой интерфейс сайта поможет найти максимально исчерпывающие
ответы по интересующей теме. Чтобы получить наиболее развернутый ответ,
можно просмотреть другие, похожие вопросы в категории Информатика,
воспользовавшись поисковой системой, или ознакомиться с ответами других
пользователей. Для расширения границ поиска создайте новый вопрос, используя
ключевые слова. Введите его в строку, нажав кнопку вверху.

Источник

C++

Java

Python 3

C#

PHP

Javascript

C++

Java

Python 3

C#

Javascript

Сумма всех простых чисел в заданном диапазоне

Заключение

Вам также может понравиться

Как составить транскрипцию английского предложения

Как составить протокол собрания учредителей на выплату дивидендов

Как найти противоречие в законе

Добавить комментарий Отменить ответ