Dada una serie de límites. Para cada límite, encuentre el número primo que se puede escribir como la suma de la mayoría de los primos consecutivos menores o iguales al límite.
El valor máximo posible de un límite es 10^4.
Ejemplo:
Input : arr[] = {10, 30}
Output : 5, 17
Explanation : There are two limit values 10 and 30.
Below limit 10, 5 is sum of two consecutive primes,
2 and 3. 5 is the prime number which is sum of largest
chain of consecutive below limit 10.
Below limit 30, 17 is sum of four consecutive primes.
2 + 3 + 5 + 7 = 17
A continuación se muestran los pasos.
- Encuentre todos los números primos por debajo de un límite máximo (10 ^ 6) usando Sieve of Sundaram y guárdelos en números primos [].
- Construya una array de suma de prefijos prime_sum[] para todos los números primos en primos[]
prime_sum[i+1] = prime_sum[i] + primes[i].
La diferencia entre dos valores en prime_sum[i] y prime_sum[j] representa la suma de números primos consecutivos desde el índice i hasta el índice j. - Atraviesa dos bucles, el bucle exterior desde i (0 hasta el límite) y el bucle interior desde j (0 hasta i)
- Para cada i, recorrido del bucle interno (0 a i), verificamos si la suma actual de números primos consecutivos ( consSum = prime_sum[i] – prime_sum[j]) es un número primo o no (buscamos consSum en prime[] usando la búsqueda binaria ).
- Si consSum es un número primo, actualizamos el resultado si la longitud actual es mayor que la longitud del resultado actual.
A continuación se muestra la implementación de los pasos anteriores.
C++
\
// C++ program to find Longest Sum of consecutive
// primes
#include<bits/stdc++.h>
using namespace std;
const int MAX = 10000;
// utility function for sieve of sundaram
void sieveSundaram(vector <int> &primes)
{
// In general Sieve of Sundaram, produces primes smaller
// than (2*x + 2) for a number given number x. Since
// we want primes smaller than MAX, we reduce MAX to half
// This array is used to separate numbers of the form
// i+j+2ij from others where 1 <= i <= j
bool marked[MAX/2 + 1] = {0};
// Main logic of Sundaram. Mark all numbers which
// do not generate prime number by doing 2*i+1
for (int i=1; i<=(sqrt(MAX)-1)/2; i++)
for (int j=(i*(i+1))<<1; j<=MAX/2; j=j+2*i+1)
marked[j] = true;
// Since 2 is a prime number
primes.push_back(2);
// Print other primes. Remaining primes are of the
// form 2*i + 1 such that marked[i] is false.
for (int i=1; i<=MAX/2; i++)
if (marked[i] == false)
primes.push_back(2*i + 1);
}
// function find the prime number which can be written
// as the sum of the most consecutive primes
int LSCPUtil(int limit, vector<int> &prime, long long int sum_prime[])
{
// To store maximum length of consecutive primes that can
// sum to a limit
int max_length = -1;
// The prime number (or result) that can be represented as
// sum of maximum number of primes.
int prime_number = -1;
// Consider all lengths of consecutive primes below limit.
for (int i=0; prime[i]<=limit; i++)
{
for (int j=0; j<i; j++)
{
// if we cross the limit, then break the loop
if (sum_prime[i] - sum_prime[j] > limit)
break;
// sum_prime[i]-sum_prime[j] is prime number or not
long long int consSum = sum_prime[i] - sum_prime[j];
// Check if sum of current length of consecutives is
// prime or not.
if (binary_search(prime.begin(), prime.end(), consSum))
{
// update the length and prime number
if (max_length < i-j+1)
{
max_length = i-j+1;
prime_number = consSum;
}
}
}
}
return prime_number;
}
// Returns the prime number that can written as sum
// of longest chain of consecutive primes.
void LSCP(int arr[], int n)
{
// Store prime number in vector
vector<int> primes;
sieveSundaram(primes);
long long int sum_prime[primes.size() + 1];
// Calculate sum of prime numbers and store them
// in sum_prime array. sum_prime[i] stores sum of
// prime numbers from primes[0] to primes[i-1]
sum_prime[0] = 0;
for (int i = 1 ; i <= primes.size(); i++)
sum_prime[i] = primes[i-1] + sum_prime[i-1];
// Process all queries one by one
for (int i=0; i<n; i++)
cout << LSCPUtil(arr[i], primes, sum_prime) << " ";
}
// Driver program
int main()
{
int arr[] = {10, 30, 40, 50, 1000};
int n = sizeof(arr)/sizeof(arr[0]);
LSCP(arr, n);
return 0;
}
Java
// Java program to find longest sum
// of consecutive primes
import java.util.*;
class GFG{
static int MAX = 10000;
// Store prime number in vector
static ArrayList<Object> primes = new ArrayList<Object>();
// Utility function for sieve of sundaram
static void sieveSundaram()
{
// In general Sieve of Sundaram,
// produces primes smaller than
// (2*x + 2) for a number given
// number x. Since we want primes
// smaller than MAX, we reduce MAX
// to half. This array is used to
// separate numbers of the form
// i+j+2ij from others where 1 <= i <= j
boolean []marked = new boolean[MAX / 2 + 1];
Arrays.fill(marked, false);
// Main logic of Sundaram. Mark
// all numbers which do not
// generate prime number by
// doing 2*i+1
for(int i = 1;
i <= (Math.sqrt(MAX) - 1) / 2; i++)
for(int j = (i * (i + 1)) << 1;
j <= MAX / 2;
j = j + 2 * i + 1)
marked[j] = true;
// Since 2 is a prime number
primes.add(2);
// Print other primes. Remaining
// primes are of the form 2*i + 1
// such that marked[i] is false.
for(int i = 1; i <= MAX / 2; i++)
if (marked[i] == false)
primes.add(2 * i + 1);
}
// Function find the prime number
// which can be written as the
// sum of the most consecutive primes
static int LSCPUtil(int limit, long []sum_prime)
{
// To store maximum length of
// consecutive primes that can
// sum to a limit
int max_length = -1;
// The prime number (or result)
// that can be represented as
// sum of maximum number of primes.
int prime_number = -1;
// Consider all lengths of
// consecutive primes below limit.
for(int i = 0; (int)primes.get(i) <= limit; i++)
{
for(int j = 0; j < i; j++)
{
// If we cross the limit, then
// break the loop
if (sum_prime[i] - sum_prime[j] >
limit)
break;
// sum_prime[i]-sum_prime[j] is
// prime number or not
long consSum = sum_prime[i] -
sum_prime[j];
Object[] prime = primes.toArray();
// Check if sum of current length
// of consecutives is prime or not.
if (Arrays.binarySearch(
prime, (int)consSum) >= 0)
{
// Update the length and prime number
if (max_length < i - j + 1)
{
max_length = i - j + 1;
prime_number = (int)consSum;
}
}
}
}
return prime_number;
}
// Returns the prime number that
// can written as sum of longest
// chain of consecutive primes.
static void LSCP(int []arr, int n)
{
sieveSundaram();
long []sum_prime = new long[primes.size() + 1];
// Calculate sum of prime numbers
// and store them in sum_prime
// array. sum_prime[i] stores sum
// of prime numbers from
// primes[0] to primes[i-1]
sum_prime[0] = 0;
for(int i = 1; i <= primes.size(); i++)
sum_prime[i] = (int)primes.get(i - 1) +
sum_prime[i - 1];
// Process all queries one by one
for(int i = 0; i < n; i++)
System.out.print(LSCPUtil(
arr[i], sum_prime) + " ");
}
// Driver code
public static void main(String []arg)
{
int []arr = { 10, 30, 40, 50, 1000 };
int n = arr.length;
LSCP(arr, n);
}
}
// This code is contributed by pratham76
Python3
# Python3 program to find Longest Sum of consecutive # primes MAX = 10000; # utility function for sieve of sundaram def sieveSundaram(primes): # In general Sieve of Sundaram, produces primes smaller # than (2*x + 2) for a number given number x. Since # we want primes smaller than MAX, we reduce MAX to half # This array is used to separate numbers of the form # i+j+2ij from others where 1 <= i <= j marked = [0 for _ in range(1 + MAX // 2)] # Main logic of Sundaram. Mark all numbers which # do not generate prime number by doing 2*i+1 for i in range(1, 1 + (int(MAX ** 0.5) - 1) // 2): for j in range((i*(i+1))<<1, 1 + MAX//2, 2*i+1): marked[j] = True # Since 2 is a prime number primes.append(2); # Print other primes. Remaining primes are of the # form 2*i + 1 such that marked[i] is false. for i in range(1, 1 + MAX // 2): if (marked[i] == False): primes.append(2*i + 1); return primes # function find the prime number which can be written # as the sum of the most consecutive primes def LSCPUtil(limit, prime, sum_prime): # To store maximum length of consecutive primes that can # sum to a limit max_length = -1; # The prime number (or result) that can be represented as # sum of maximum number of primes. prime_number = -1; # Consider all lengths of consecutive primes below limit. i = 0 while (prime[i] <= limit): for j in range(i): # if we cross the limit, then break the loop if (sum_prime[i] - sum_prime[j] > limit): break; # sum_prime[i]-sum_prime[j] is prime number or not consSum = sum_prime[i] - sum_prime[j]; # Check if sum of current length of consecutives is # prime or not. if consSum in prime: # update the length and prime number if (max_length < i-j+1): max_length = i-j+1; prime_number = consSum i += 1 return prime_number; # Returns the prime number that can written as sum # of longest chain of consecutive primes. def LSCP(arr, n): # Store prime number in vector primes = []; primes = sieveSundaram(primes); sum_prime = [None for _ in range(1 + len(primes))] # Calculate sum of prime numbers and store them # in sum_prime array. sum_prime[i] stores sum of # prime numbers from primes[0] to primes[i-1] sum_prime[0] = 0; for i in range(1, 1 + len(primes)): sum_prime[i] = primes[i-1] + sum_prime[i-1]; # Process all queries one by one for i in range(n): print(LSCPUtil(arr[i], primes, sum_prime), end = " "); # Driver program arr = [ 10, 30, 40, 50, 1000 ]; n = len(arr) LSCP(arr, n); # This code is contributed by phasing17
C#
// C# program to find longest sum
// of consecutive primes
using System;
using System.Collections;
class GFG{
static int MAX = 10000;
// Store prime number in vector
static ArrayList primes = new ArrayList();
// Utility function for sieve of sundaram
static void sieveSundaram()
{
// In general Sieve of Sundaram,
// produces primes smaller than
// (2*x + 2) for a number given
// number x. Since we want primes
// smaller than MAX, we reduce MAX
// to half. This array is used to
// separate numbers of the form
// i+j+2ij from others where 1 <= i <= j
bool []marked = new bool[MAX / 2 + 1];
Array.Fill(marked, false);
// Main logic of Sundaram. Mark
// all numbers which do not
// generate prime number by
// doing 2*i+1
for(int i = 1;
i <= (Math.Sqrt(MAX) - 1) / 2; i++)
for(int j = (i * (i + 1)) << 1;
j <= MAX / 2;
j = j + 2 * i + 1)
marked[j] = true;
// Since 2 is a prime number
primes.Add(2);
// Print other primes. Remaining
// primes are of the form
// 2*i + 1 such that marked[i] is false.
for(int i = 1; i <= MAX / 2; i++)
if (marked[i] == false)
primes.Add(2 * i + 1);
}
// Function find the prime number
// which can be written as the
// sum of the most consecutive primes
static int LSCPUtil(int limit, long []sum_prime)
{
// To store maximum length of
// consecutive primes that can
// sum to a limit
int max_length = -1;
// The prime number (or result)
// that can be represented as
// sum of maximum number of primes.
int prime_number = -1;
// Consider all lengths of
// consecutive primes below limit.
for(int i = 0; (int)primes[i] <= limit; i++)
{
for(int j = 0; j < i; j++)
{
// If we cross the limit, then
// break the loop
if (sum_prime[i] - sum_prime[j] >
limit)
break;
// sum_prime[i]-sum_prime[j] is
// prime number or not
long consSum = sum_prime[i] -
sum_prime[j];
int[] prime = (int[])primes.ToArray(typeof(int));
// Check if sum of current length
// of consecutives is prime or not.
if (Array.BinarySearch(prime,
(int)consSum) >= 0)
{
// Update the length and prime number
if (max_length < i - j + 1)
{
max_length = i - j + 1;
prime_number = (int)consSum;
}
}
}
}
return prime_number;
}
// Returns the prime number that
// can written as sum of longest
// chain of consecutive primes.
static void LSCP(int []arr, int n)
{
sieveSundaram();
long []sum_prime = new long[primes.Count + 1];
// Calculate sum of prime numbers
// and store them in sum_prime
// array. sum_prime[i] stores sum
// of prime numbers from
// primes[0] to primes[i-1]
sum_prime[0] = 0;
for(int i = 1; i <= primes.Count; i++)
sum_prime[i] = (int)primes[i - 1] +
sum_prime[i - 1];
// Process all queries one by one
for(int i = 0; i < n; i++)
Console.Write(LSCPUtil(
arr[i], sum_prime) + " ");
}
// Driver code
public static void Main(string []arg)
{
int []arr = { 10, 30, 40, 50, 1000 };
int n = arr.Length;
LSCP(arr, n);
}
}
// This code is contributed by rutvik_56
Javascript
// JavaScript program to find Longest Sum of consecutive
// primes
let MAX = 10000;
// utility function for sieve of sundaram
function sieveSundaram(primes)
{
// In general Sieve of Sundaram, produces primes smaller
// than (2*x + 2) for a number given number x. Since
// we want primes smaller than MAX, we reduce MAX to half
// This array is used to separate numbers of the form
// i+j+2ij from others where 1 <= i <= j
let marked = new Array(Math.floor(MAX / 2) + 1).fill(0);
// Main logic of Sundaram. Mark all numbers which
// do not generate prime number by doing 2*i+1
for (var i=1; i<=(Math.sqrt(MAX)-1)/2; i++)
for (var j=(i*(i+1))<<1; j<=MAX/2; j=j+2*i+1)
marked[j] = true;
// Since 2 is a prime number
primes.push(2);
// Print other primes. Remaining primes are of the
// form 2*i + 1 such that marked[i] is false.
for (var i=1; i<=MAX/2; i++)
if (marked[i] == false)
primes.push(2*i + 1);
}
// function find the prime number which can be written
// as the sum of the most consecutive primes
function LSCPUtil(limit, prime, sum_prime)
{
// To store maximum length of consecutive primes that can
// sum to a limit
let max_length = -1;
// The prime number (or result) that can be represented as
// sum of maximum number of primes.
let prime_number = -1;
// Consider all lengths of consecutive primes below limit.
for (var i=0; prime[i]<=limit; i++)
{
for (var j=0; j<i; j++)
{
// if we cross the limit, then break the loop
if (sum_prime[i] - sum_prime[j] > limit)
break;
// sum_prime[i]-sum_prime[j] is prime number or not
let consSum = sum_prime[i] - sum_prime[j];
// Check if sum of current length of consecutives is
// prime or not.
if (prime.indexOf(consSum) != -1)
{
// update the length and prime number
if (max_length < i-j+1)
{
max_length = i-j+1;
prime_number = consSum;
}
}
}
}
return prime_number;
}
// Returns the prime number that can written as sum
// of longest chain of consecutive primes.
function LSCP(arr, n)
{
// Store prime number in vector
let primes = [];
sieveSundaram(primes);
let sum_prime = new Array(primes.length + 1);
// Calculate sum of prime numbers and store them
// in sum_prime array. sum_prime[i] stores sum of
// prime numbers from primes[0] to primes[i-1]
sum_prime[0] = 0;
for (var i = 1 ; i <= primes.length; i++)
sum_prime[i] = primes[i-1] + sum_prime[i-1];
// Process all queries one by one
for (var i=0; i<n; i++)
process.stdout.write(LSCPUtil(arr[i], primes, sum_prime) + " ");
}
// Driver program
let arr = [ 10, 30, 40, 50, 1000 ];
let n = arr.length;
LSCP(arr, n);
// This code is contributed by phasing17
Producción:
5 17 17 41 953
Este artículo es una contribución de Nishant_singh (pintu) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA