Dado un número entero N , la tarea es encontrar la suma de todos los primos truncables por debajo de N . Primo truncable es un número que es primo truncable por la izquierda (si el dígito inicial («izquierdo») se elimina sucesivamente, entonces todos los números resultantes son primos) así como primo truncable por la derecha (si el último dígito («derecho») es eliminados sucesivamente, entonces todos los números resultantes son primos).
Por ejemplo, 3797 es primo truncable por la izquierda porque 797, 97 y 7 son primos. Y 3797 también es primo truncable por la derecha, ya que 379, 37 y 3 son primos. Por lo tanto, 3797 es un número primo truncable.
Ejemplos:
Entrada: N = 25
Salida: 40
2, 3, 5, 7 y 23 son los únicos primos truncables por debajo de 25.
2 + 3 + 5 + 7 + 23 = 40Entrada: N = 40
Salida: 77
Enfoque: un enfoque eficiente es encontrar todos los números primos utilizando la criba de Eratóstenes y, para cada número por debajo de N , comprobar si es primo truncable o no. En caso afirmativo, agregue es a la suma acumulada.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define N 1000005
// To check if a number is prime or not
bool prime[N];
// Sieve of Eratosthenes
// function to find all prime numbers
void sieve()
{
memset(prime, true, sizeof prime);
prime[1] = false;
prime[0] = false;
for (int i = 2; i < N; i++)
if (prime[i])
for (int j = i * 2; j < N; j += i)
prime[j] = false;
}
// Function to return the sum of
// all truncatable primes below n
int sumTruncatablePrimes(int n)
{
// To store the required sum
int sum = 0;
// Check every number below n
for (int i = 2; i < n; i++) {
int num = i;
bool flag = true;
// Check from right to left
while (num) {
// If number is not prime at any stage
if (!prime[num]) {
flag = false;
break;
}
num /= 10;
}
num = i;
int power = 10;
// Check from left to right
while (num / power) {
// If number is not prime at any stage
if (!prime[num % power]) {
flag = false;
break;
}
power *= 10;
}
// If flag is still true
if (flag)
sum += i;
}
// Return the required sum
return sum;
}
// Driver code
int main()
{
int n = 25;
sieve();
cout << sumTruncatablePrimes(n);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
static final int N = 1000005;
// To check if a number is prime or not
static boolean prime[] = new boolean[N];
// Sieve of Eratosthenes
// function to find all prime numbers
static void sieve()
{
Arrays.fill(prime, true);
prime[1] = false;
prime[0] = false;
for (int i = 2; i < N; i++)
{
if (prime[i])
{
for (int j = i * 2; j < N; j += i)
{
prime[j] = false;
}
}
}
}
// Function to return the sum of
// all truncatable primes below n
static int sumTruncatablePrimes(int n)
{
// To store the required sum
int sum = 0;
// Check every number below n
for (int i = 2; i < n; i++)
{
int num = i;
boolean flag = true;
// Check from right to left
while (num > 0)
{
// If number is not prime at any stage
if (!prime[num])
{
flag = false;
break;
}
num /= 10;
}
num = i;
int power = 10;
// Check from left to right
while (num / power > 0)
{
// If number is not prime at any stage
if (!prime[num % power])
{
flag = false;
break;
}
power *= 10;
}
// If flag is still true
if (flag)
{
sum += i;
}
}
// Return the required sum
return sum;
}
// Driver code
public static void main(String[] args)
{
int n = 25;
sieve();
System.out.println(sumTruncatablePrimes(n));
}
}
// This code contributed by Rajput-Ji
Python3
# Python3 implementation of the # above approach N = 1000005 # To check if a number is prime or not prime = [True for i in range(N)] # Sieve of Eratosthenes # function to find all prime numbers def sieve(): prime[1] = False prime[0] = False for i in range(2, N): if (prime[i]==True): for j in range(i * 2, N, i): prime[j] = False # Function to return the sum of # all truncatable primes below n def sumTruncatablePrimes(n): # To store the required sum sum = 0 # Check every number below n for i in range(2, n): num = i flag = True # Check from right to left while (num): # If number is not prime at any stage if (prime[num] == False): flag = False break num //= 10 num = i power = 10 # Check from left to right while (num // power): # If number is not prime at any stage if (prime[num % power] == False): flag = False break power *= 10 # If flag is still true if (flag==True): sum += i # Return the required sum return sum # Driver code n = 25 sieve() print(sumTruncatablePrimes(n)) # This code is contributed by mohit kumar
C#
// C# implementation of the above approach.
using System;
using System.Collections.Generic;
class GFG
{
static int N = 1000005;
// To check if a number is prime or not
static Boolean []prime = new Boolean[N];
// Sieve of Eratosthenes
// function to find all prime numbers
static void sieve()
{
Array.Fill(prime, true);
prime[1] = false;
prime[0] = false;
for (int i = 2; i < N; i++)
{
if (prime[i])
{
for (int j = i * 2; j < N; j += i)
{
prime[j] = false;
}
}
}
}
// Function to return the sum of
// all truncatable primes below n
static int sumTruncatablePrimes(int n)
{
// To store the required sum
int sum = 0;
// Check every number below n
for (int i = 2; i < n; i++)
{
int num = i;
Boolean flag = true;
// Check from right to left
while (num > 0)
{
// If number is not prime at any stage
if (!prime[num])
{
flag = false;
break;
}
num /= 10;
}
num = i;
int power = 10;
// Check from left to right
while (num / power > 0)
{
// If number is not prime at any stage
if (!prime[num % power])
{
flag = false;
break;
}
power *= 10;
}
// If flag is still true
if (flag)
{
sum += i;
}
}
// Return the required sum
return sum;
}
// Driver code
public static void Main(String []args)
{
int n = 25;
sieve();
Console.WriteLine(sumTruncatablePrimes(n));
}
}
// This code has been contributed by Arnab Kundu
PHP
<?php
// PHP implementation of the approach
$N = 10005;
// To check if a number is prime or not
$prime = array_fill(0, $N, true);
// Sieve of Eratosthenes
// function to find all prime numbers
function sieve()
{
global $prime, $N;
$prime[1] = false;
$prime[0] = false;
for ($i = 2; $i < $N; $i++)
if ($prime[$i])
for ($j = $i * 2; $j < $N; $j += $i)
$prime[$j] = false;
}
// Function to return the sum of
// all truncatable primes below n
function sumTruncatablePrimes($n)
{
global $prime, $N;
// To store the required sum
$sum = 0;
// Check every number below n
for ($i = 2; $i < $n; $i++)
{
$num = $i;
$flag = true;
// Check from right to left
while ($num)
{
// If number is not prime at any stage
if (!$prime[$num])
{
$flag = false;
break;
}
$num = (int)($num / 10);
}
$num = $i;
$power = 10;
// Check from left to right
while ((int)($num / $power))
{
// If number is not prime at any stage
if (!$prime[$num % $power])
{
$flag = false;
break;
}
$power *= 10;
}
// If flag is still true
if ($flag)
$sum += $i;
}
// Return the required sum
return $sum;
}
// Driver code
$n = 25;
sieve();
echo sumTruncatablePrimes($n);
// This code is contributed by mits
?>
Javascript
<script>
// Javascript implementation of the approach
let N = 1000005;
// To check if a number is prime or not
let prime = new Array(N);
// Sieve of Eratosthenes
// function to find all prime numbers
function sieve()
{
for(let i = 0; i < prime.length; i++)
{
prime[i] = true;
}
prime[1] = false;
prime[0] = false;
for(let i = 2; i < N; i++)
{
if (prime[i])
{
for(let j = i * 2; j < N; j += i)
{
prime[j] = false;
}
}
}
}
// Function to return the sum of
// all truncatable primes below n
function sumTruncatablePrimes(n)
{
// To store the required sum
let sum = 0;
// Check every number below n
for(let i = 2; i < n; i++)
{
let num = i;
let flag = true;
// Check from right to left
while (num > 0)
{
// If number is not prime at any stage
if (!prime[num])
{
flag = false;
break;
}
num = Math.floor(num / 10);
}
num = i;
let power = 10;
// Check from left to right
while (num / power > 0)
{
// If number is not prime at any stage
if (!prime[num % power])
{
flag = false;
break;
}
power *= 10;
}
// If flag is still true
if (flag)
{
sum += i;
}
}
// Return the required sum
return sum;
}
// Driver code
let n = 25;
sieve();
document.write(sumTruncatablePrimes(n));
// This code is contributed by unknown2108
</script>
Producción:
40
Complejidad de tiempo: O(n*log(log(n))), tiempo utilizado para ejecutar la función tamiz
Espacio auxiliar: O(N), espacio adicional de tamaño n utilizado para crear una array principal
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA