Find the all right truncatable primes in n natural numbers
"Right truncatable primes" are prime numbers that remain prime when their rightmost digits are successively removed. For example, 3797 is a right truncatable prime because 3797, 379, 37, and 3 are all prime numbers.
To find all right truncatable primes in n natural numbers, you would need to generate all prime numbers up to n and then check each prime number to see if it is right truncatable. One way to generate prime numbers is to use the Sieve of Eratosthenes, which is an efficient algorithm for finding all primes up to a given limit.
Program Solution
// C program for
// Find the all right truncatable primes in n natural numbers
#include <stdio.h>
// Find all prime numbers which have smaller and equal to given number n
void sieve_of_eratosthenes(int prime[], int n)
{
// Initial two numbers are not prime (0 and 1)
prime[0] = 0;
prime[1] = 0;
// Set the initial (2 to n element is prime)
for (int i = 2; i <= n; ++i)
{
prime[i] = 1;
}
// Initial 0 and 1 are not prime
// We start to 2
for (int i = 2; i * i <= n; ++i)
{
if (prime[i] == 1)
{
// When i is prime number
// Modify the prime status of all next multiplier of location i
for (int j = i * i; j <= n; j += i)
{
prime[j] = 0;
}
}
}
}
void rightTruncatablePrime(int n)
{
if (n <= 1)
{
return;
}
int prime[n + 1];
sieve_of_eratosthenes(prime, n);
printf("\n Given n : %d", n);
printf("\n");
for (int i = 2; i <= n; ++i)
{
if (prime[i] == 1)
{
int temp = i;
while (temp > 0 && prime[temp] == 1)
{
// Remove last digit
temp = temp / 10;
}
if (temp == 0)
{
printf(" %d", i);
}
}
}
}
int main(int argc, char
const * argv[])
{
// Test A
// n = 30
/*
2
3
5
7
23 2
29 2
----------
*/
rightTruncatablePrime(30);
// Test B
// n = 10000
/*
2
3
5
7
23 2
29 2
31 3
37 3
53 5
59 5
71 7
73 7
79 7
233 23 2
239 23 2
293 29 2
311 31 3
313 31 3
317 31 3
373 37 3
379 37 3
593 59 5
599 59 5
719 71 7
733 73 7
739 73 7
797 79 7
2333 233 23 2
2339 233 23 2
2393 239 23 2
2399 239 23 2
2939 293 29 2
3119 311 31 3
3137 313 31 3
3733 373 37 3
3739 373 37 3
3793 379 37 3
3797 379 37 3
5939 593 59 5
7193 719 71 7
7331 733 73 7
7333 733 73 7
7393 739 73 7
----------------
[Remove right digit]
Example prime = 5939
5939
593
59
5
----------------------
All is prime so 5939
right truncatable prime
*/
rightTruncatablePrime(10000);
return 0;
}Output
Given n : 30
2 3 5 7 23 29
Given n : 10000
2 3 5 7 23 29 31 37 53 59 71 73 79 233 239 293 311 313 317 373 379 593 599 719 733 739 797 2333 2339 2393 2399 2939 3119 3137 3733 3739 3793 3797 5939 7193 7331 7333 7393/*
Java Program for
Find the all right truncatable primes in n natural numbers
*/
public class TruncatablePrimes
{
// Find all prime numbers which have smaller and equal to given number n
public void sieveOfEratosthenes(boolean[] prime, int n)
{
// Initial two numbers are not prime (0 and 1)
prime[0] = false;
prime[1] = false;
// Set the initial (2 to n element is prime)
for (int i = 2; i <= n; ++i)
{
prime[i] = true;
}
// Initial 0 and 1 are not prime
// We start to 2
for (int i = 2; i *i <= n; ++i)
{
if (prime[i] == true)
{
// When i is prime number
// Modify the prime status of all next
// multiplier of location i
for (int j = i *i; j <= n; j += i)
{
prime[j] = false;
}
}
}
}
public void rightTruncatablePrime(int n)
{
if (n <= 1)
{
return;
}
boolean[] prime = new boolean[n + 1];
sieveOfEratosthenes(prime, n);
System.out.print("\n Given n : " + n);
System.out.print("\n");
for (int i = 2; i <= n; ++i)
{
if (prime[i] == true)
{
int temp = i;
while (temp > 0 && prime[temp] == true)
{
// Remove last digit
temp = temp / 10;
}
if (temp == 0)
{
System.out.print(" " + i);
}
}
}
}
public static void main(String[] args)
{
TruncatablePrimes task = new TruncatablePrimes();
// Test A
// n = 30
/*
2
3
5
7
23 2
29 2
----------
*/
task.rightTruncatablePrime(30);
// Test B
// n = 10000
/*
2
3
5
7
23 2
29 2
31 3
37 3
53 5
59 5
71 7
73 7
79 7
233 23 2
239 23 2
293 29 2
311 31 3
313 31 3
317 31 3
373 37 3
379 37 3
593 59 5
599 59 5
719 71 7
733 73 7
739 73 7
797 79 7
2333 233 23 2
2339 233 23 2
2393 239 23 2
2399 239 23 2
2939 293 29 2
3119 311 31 3
3137 313 31 3
3733 373 37 3
3739 373 37 3
3793 379 37 3
3797 379 37 3
5939 593 59 5
7193 719 71 7
7331 733 73 7
7333 733 73 7
7393 739 73 7
----------------
[Remove right digit]
Example prime = 5939
5939
593
59
5
----------------------
All is prime so 5939
right truncatable prime
*/
task.rightTruncatablePrime(10000);
}
}Output
Given n : 30
2 3 5 7 23 29
Given n : 10000
2 3 5 7 23 29 31 37 53 59 71 73 79 233 239 293 311 313 317 373 379 593 599 719 733 739 797 2333 2339 2393 2399 2939 3119 3137 3733 3739 3793 3797 5939 7193 7331 7333 7393// Include header file
#include <iostream>
using namespace std;
/*
C++ Program for
Find the all right truncatable primes in n natural numbers
*/
class TruncatablePrimes
{
public:
// Find all prime numbers which have smaller and equal to
// given number n
void sieveOfEratosthenes(bool prime[], int n)
{
// Initial two numbers are not prime (0 and 1)
prime[0] = false;
prime[1] = false;
// Set the initial (2 to n element is prime)
for (int i = 2; i <= n; ++i)
{
prime[i] = true;
}
// Initial 0 and 1 are not prime
// We start to 2
for (int i = 2; i *i <= n; ++i)
{
if (prime[i] == true)
{
// When i is prime number
// Modify the prime status of all next
// multiplier of location i
for (int j = i *i; j <= n; j += i)
{
prime[j] = false;
}
}
}
}
void rightTruncatablePrime(int n)
{
if (n <= 1)
{
return;
}
bool prime[n + 1];
this->sieveOfEratosthenes(prime, n);
cout << "\n Given n : " << n;
cout << "\n";
for (int i = 2; i <= n; ++i)
{
if (prime[i] == true)
{
int temp = i;
while (temp > 0 && prime[temp] == true)
{
// Remove last digit
temp = temp / 10;
}
if (temp == 0)
{
cout << " " << i;
}
}
}
}
};
int main()
{
TruncatablePrimes *task = new TruncatablePrimes();
// Test A
// n = 30
/*
2
3
5
7
23 2
29 2
----------
*/
task->rightTruncatablePrime(30);
// Test B
// n = 10000
/*
2
3
5
7
23 2
29 2
31 3
37 3
53 5
59 5
71 7
73 7
79 7
233 23 2
239 23 2
293 29 2
311 31 3
313 31 3
317 31 3
373 37 3
379 37 3
593 59 5
599 59 5
719 71 7
733 73 7
739 73 7
797 79 7
2333 233 23 2
2339 233 23 2
2393 239 23 2
2399 239 23 2
2939 293 29 2
3119 311 31 3
3137 313 31 3
3733 373 37 3
3739 373 37 3
3793 379 37 3
3797 379 37 3
5939 593 59 5
7193 719 71 7
7331 733 73 7
7333 733 73 7
7393 739 73 7
----------------
[Remove right digit]
Example prime = 5939
5939
593
59
5
----------------------
All is prime so 5939
right truncatable prime
*/
task->rightTruncatablePrime(10000);
return 0;
}Output
Given n : 30
2 3 5 7 23 29
Given n : 10000
2 3 5 7 23 29 31 37 53 59 71 73 79 233 239 293 311 313 317 373 379 593 599 719 733 739 797 2333 2339 2393 2399 2939 3119 3137 3733 3739 3793 3797 5939 7193 7331 7333 7393// Include namespace system
using System;
/*
Csharp Program for
Find the all right truncatable primes in n natural numbers
*/
public class TruncatablePrimes
{
// Find all prime numbers which have smaller and equal to
// given number n
public void sieveOfEratosthenes(Boolean[] prime, int n)
{
// Initial two numbers are not prime (0 and 1)
prime[0] = false;
prime[1] = false;
// Set the initial (2 to n element is prime)
for (int i = 2; i <= n; ++i)
{
prime[i] = true;
}
// Initial 0 and 1 are not prime
// We start to 2
for (int i = 2; i * i <= n; ++i)
{
if (prime[i] == true)
{
// When i is prime number
// Modify the prime status of all next
// multiplier of location i
for (int j = i * i; j <= n; j += i)
{
prime[j] = false;
}
}
}
}
public void rightTruncatablePrime(int n)
{
if (n <= 1)
{
return;
}
Boolean[] prime = new Boolean[n + 1];
this.sieveOfEratosthenes(prime, n);
Console.Write("\n Given n : " + n);
Console.Write("\n");
for (int i = 2; i <= n; ++i)
{
if (prime[i] == true)
{
int temp = i;
while (temp > 0 && prime[temp] == true)
{
// Remove last digit
temp = temp / 10;
}
if (temp == 0)
{
Console.Write(" " + i);
}
}
}
}
public static void Main(String[] args)
{
TruncatablePrimes task = new TruncatablePrimes();
// Test A
// n = 30
/*
2
3
5
7
23 2
29 2
----------
*/
task.rightTruncatablePrime(30);
// Test B
// n = 10000
/*
2
3
5
7
23 2
29 2
31 3
37 3
53 5
59 5
71 7
73 7
79 7
233 23 2
239 23 2
293 29 2
311 31 3
313 31 3
317 31 3
373 37 3
379 37 3
593 59 5
599 59 5
719 71 7
733 73 7
739 73 7
797 79 7
2333 233 23 2
2339 233 23 2
2393 239 23 2
2399 239 23 2
2939 293 29 2
3119 311 31 3
3137 313 31 3
3733 373 37 3
3739 373 37 3
3793 379 37 3
3797 379 37 3
5939 593 59 5
7193 719 71 7
7331 733 73 7
7333 733 73 7
7393 739 73 7
----------------
[Remove right digit]
Example prime = 5939
5939
593
59
5
----------------------
All is prime so 5939
right truncatable prime
*/
task.rightTruncatablePrime(10000);
}
}Output
Given n : 30
2 3 5 7 23 29
Given n : 10000
2 3 5 7 23 29 31 37 53 59 71 73 79 233 239 293 311 313 317 373 379 593 599 719 733 739 797 2333 2339 2393 2399 2939 3119 3137 3733 3739 3793 3797 5939 7193 7331 7333 7393package main
import "fmt"
/*
Go Program for
Find the all right truncatable primes in n natural numbers
*/
type TruncatablePrimes struct {}
func getTruncatablePrimes() * TruncatablePrimes {
var me *TruncatablePrimes = &TruncatablePrimes {}
return me
}
// Find all prime numbers which have smaller and equal to
// given number n
func(this TruncatablePrimes) sieveOfEratosthenes(prime[] bool, n int) {
// Initial two numbers are not prime (0 and 1)
prime[0] = false
prime[1] = false
// Initial 0 and 1 are not prime
// We start to 2
for i := 2 ; i * i <= n ; i++ {
if prime[i] == true {
// When i is prime number
// Modify the prime status of all next
// multiplier of location i
for j := i * i ; j <= n ; j += i {
prime[j] = false
}
}
}
}
func(this TruncatablePrimes) rightTruncatablePrime(n int) {
if n <= 1 {
return
}
var prime = make([] bool, n + 1)
for i := 0; i <= n; i++ {
prime[i] = true
}
this.sieveOfEratosthenes(prime, n)
fmt.Print("\n Given n : ", n)
fmt.Print("\n")
for i := 2 ; i <= n ; i++ {
if prime[i] == true {
var temp int = i
for (temp > 0 && prime[temp] == true) {
// Remove last digit
temp = temp / 10
}
if temp == 0 {
fmt.Print(" ", i)
}
}
}
}
func main() {
var task * TruncatablePrimes = getTruncatablePrimes()
// Test A
// n = 30
/*
2
3
5
7
23 2
29 2
----------
*/
task.rightTruncatablePrime(30)
// Test B
// n = 10000
/*
2
3
5
7
23 2
29 2
31 3
37 3
53 5
59 5
71 7
73 7
79 7
233 23 2
239 23 2
293 29 2
311 31 3
313 31 3
317 31 3
373 37 3
379 37 3
593 59 5
599 59 5
719 71 7
733 73 7
739 73 7
797 79 7
2333 233 23 2
2339 233 23 2
2393 239 23 2
2399 239 23 2
2939 293 29 2
3119 311 31 3
3137 313 31 3
3733 373 37 3
3739 373 37 3
3793 379 37 3
3797 379 37 3
5939 593 59 5
7193 719 71 7
7331 733 73 7
7333 733 73 7
7393 739 73 7
----------------
[Remove right digit]
Example prime = 5939
5939
593
59
5
----------------------
All is prime so 5939
right truncatable prime
*/
task.rightTruncatablePrime(10000)
}Output
Given n : 30
2 3 5 7 23 29
Given n : 10000
2 3 5 7 23 29 31 37 53 59 71 73 79 233 239 293 311 313 317 373 379 593 599 719 733 739 797 2333 2339 2393 2399 2939 3119 3137 3733 3739 3793 3797 5939 7193 7331 7333 7393<?php
/*
Php Program for
Find the all right truncatable primes in n natural numbers
*/
class TruncatablePrimes
{
// Find all prime numbers which have smaller and equal to
// given number n
public function sieveOfEratosthenes(&$prime, $n)
{
// Initial two numbers are not prime (0 and 1)
$prime[0] = false;
$prime[1] = false;
// Initial 0 and 1 are not prime
// We start to 2
for ($i = 2; $i * $i <= $n; ++$i)
{
if ($prime[$i] == true)
{
// When i is prime number
// Modify the prime status of all next
// multiplier of location i
for ($j = $i * $i; $j <= $n; $j += $i)
{
$prime[$j] = false;
}
}
}
}
public function rightTruncatablePrime($n)
{
if ($n <= 1)
{
return;
}
$prime = array_fill(0, $n + 1, true);
$this->sieveOfEratosthenes($prime, $n);
echo("\n Given n : ".$n);
echo("\n");
for ($i = 2; $i <= $n; ++$i)
{
if ($prime[$i] == true)
{
$temp = $i;
while ($temp > 0 && $prime[$temp] == true)
{
// Remove last digit
$temp = (int)($temp / 10);
}
if ($temp == 0)
{
echo(" ".$i);
}
}
}
}
}
function main()
{
$task = new TruncatablePrimes();
// Test A
// n = 30
/*
2
3
5
7
23 2
29 2
----------
*/
$task->rightTruncatablePrime(30);
// Test B
// n = 10000
/*
2
3
5
7
23 2
29 2
31 3
37 3
53 5
59 5
71 7
73 7
79 7
233 23 2
239 23 2
293 29 2
311 31 3
313 31 3
317 31 3
373 37 3
379 37 3
593 59 5
599 59 5
719 71 7
733 73 7
739 73 7
797 79 7
2333 233 23 2
2339 233 23 2
2393 239 23 2
2399 239 23 2
2939 293 29 2
3119 311 31 3
3137 313 31 3
3733 373 37 3
3739 373 37 3
3793 379 37 3
3797 379 37 3
5939 593 59 5
7193 719 71 7
7331 733 73 7
7333 733 73 7
7393 739 73 7
----------------
[Remove right digit]
Example prime = 5939
5939
593
59
5
----------------------
All is prime so 5939
right truncatable prime
*/
$task->rightTruncatablePrime(10000);
}
main();Output
Given n : 30
2 3 5 7 23 29
Given n : 10000
2 3 5 7 23 29 31 37 53 59 71 73 79 233 239 293 311 313 317 373 379 593 599 719 733 739 797 2333 2339 2393 2399 2939 3119 3137 3733 3739 3793 3797 5939 7193 7331 7333 7393/*
Node JS Program for
Find the all right truncatable primes in n natural numbers
*/
class TruncatablePrimes
{
// Find all prime numbers which have smaller and equal to
// given number n
sieveOfEratosthenes(prime, n)
{
// Initial two numbers are not prime (0 and 1)
prime[0] = false;
prime[1] = false;
// Initial 0 and 1 are not prime
// We start to 2
for (var i = 2; i * i <= n; ++i)
{
if (prime[i] == true)
{
// When i is prime number
// Modify the prime status of all next
// multiplier of location i
for (var j = i * i; j <= n; j += i)
{
prime[j] = false;
}
}
}
}
rightTruncatablePrime(n)
{
if (n <= 1)
{
return;
}
var prime = Array(n + 1).fill(true);
this.sieveOfEratosthenes(prime, n);
process.stdout.write("\n Given n : " + n);
process.stdout.write("\n");
for (var i = 2; i <= n; ++i)
{
if (prime[i] == true)
{
var temp = i;
while (temp > 0 && prime[temp] == true)
{
// Remove last digit
temp = parseInt(temp / 10);
}
if (temp == 0)
{
process.stdout.write(" " + i);
}
}
}
}
}
function main()
{
var task = new TruncatablePrimes();
// Test A
// n = 30
/*
2
3
5
7
23 2
29 2
----------
*/
task.rightTruncatablePrime(30);
// Test B
// n = 10000
/*
2
3
5
7
23 2
29 2
31 3
37 3
53 5
59 5
71 7
73 7
79 7
233 23 2
239 23 2
293 29 2
311 31 3
313 31 3
317 31 3
373 37 3
379 37 3
593 59 5
599 59 5
719 71 7
733 73 7
739 73 7
797 79 7
2333 233 23 2
2339 233 23 2
2393 239 23 2
2399 239 23 2
2939 293 29 2
3119 311 31 3
3137 313 31 3
3733 373 37 3
3739 373 37 3
3793 379 37 3
3797 379 37 3
5939 593 59 5
7193 719 71 7
7331 733 73 7
7333 733 73 7
7393 739 73 7
----------------
[Remove right digit]
Example prime = 5939
5939
593
59
5
----------------------
All is prime so 5939
right truncatable prime
*/
task.rightTruncatablePrime(10000);
}
main();Output
Given n : 30
2 3 5 7 23 29
Given n : 10000
2 3 5 7 23 29 31 37 53 59 71 73 79 233 239 293 311 313 317 373 379 593 599 719 733 739 797 2333 2339 2393 2399 2939 3119 3137 3733 3739 3793 3797 5939 7193 7331 7333 7393# Python 3 Program for
# Find the all right truncatable primes in n natural numbers
class TruncatablePrimes :
# Find all prime numbers which have smaller and equal to
# given number n
def sieveOfEratosthenes(self, prime, n) :
# Initial two numbers are not prime (0 and 1)
prime[0] = False
prime[1] = False
i = 2
# Initial 0 and 1 are not prime
# We start to 2
while (i * i <= n) :
if (prime[i] == True) :
j = i * i
# When i is prime number
# Modify the prime status of all next
# multiplier of location i
while (j <= n) :
prime[j] = False
j += i
i += 1
def rightTruncatablePrime(self, n) :
if (n <= 1) :
return
prime = [True] * (n + 1)
self.sieveOfEratosthenes(prime, n)
print("\n Given n : ", n, end = "")
print(end = "\n")
i = 2
while (i <= n) :
if (prime[i] == True) :
temp = i
while (temp > 0 and prime[temp] == True) :
# Remove last digit
temp = int(temp / 10)
if (temp == 0) :
print(" ", i, end = "")
i += 1
def main() :
task = TruncatablePrimes()
# Test A
# n = 30
# 2
# 3
# 5
# 7
# 23 2
# 29 2
# ----------
task.rightTruncatablePrime(30)
# Test B
# n = 10000
# 2
# 3
# 5
# 7
# 23 2
# 29 2
# 31 3
# 37 3
# 53 5
# 59 5
# 71 7
# 73 7
# 79 7
# 233 23 2
# 239 23 2
# 293 29 2
# 311 31 3
# 313 31 3
# 317 31 3
# 373 37 3
# 379 37 3
# 593 59 5
# 599 59 5
# 719 71 7
# 733 73 7
# 739 73 7
# 797 79 7
# 2333 233 23 2
# 2339 233 23 2
# 2393 239 23 2
# 2399 239 23 2
# 2939 293 29 2
# 3119 311 31 3
# 3137 313 31 3
# 3733 373 37 3
# 3739 373 37 3
# 3793 379 37 3
# 3797 379 37 3
# 5939 593 59 5
# 7193 719 71 7
# 7331 733 73 7
# 7333 733 73 7
# 7393 739 73 7
# ----------------
# [Remove right digit]
# Example prime = 5939
# 5939
# 593
# 59
# 5
# ----------------------
# All is prime so 5939
# right truncatable prime
task.rightTruncatablePrime(10000)
if __name__ == "__main__": main()Output
Given n : 30
2 3 5 7 23 29
Given n : 10000
2 3 5 7 23 29 31 37 53 59 71 73 79 233 239 293 311 313 317 373 379 593 599 719 733 739 797 2333 2339 2393 2399 2939 3119 3137 3733 3739 3793 3797 5939 7193 7331 7333 7393# Ruby Program for
# Find the all right truncatable primes in n natural numbers
class TruncatablePrimes
# Find all prime numbers which have smaller and equal to
# given number n
def sieveOfEratosthenes(prime, n)
# Initial two numbers are not prime (0 and 1)
prime[0] = false
prime[1] = false
i = 2
# Initial 0 and 1 are not prime
# We start to 2
while (i * i <= n)
if (prime[i] == true)
j = i * i
# When i is prime number
# Modify the prime status of all next
# multiplier of location i
while (j <= n)
prime[j] = false
j += i
end
end
i += 1
end
end
def rightTruncatablePrime(n)
if (n <= 1)
return
end
prime = Array.new(n + 1) {true}
self.sieveOfEratosthenes(prime, n)
print("\n Given n : ", n)
print("\n")
i = 2
while (i <= n)
if (prime[i] == true)
temp = i
while (temp > 0 && prime[temp] == true)
# Remove last digit
temp = temp / 10
end
if (temp == 0)
print(" ", i)
end
end
i += 1
end
end
end
def main()
task = TruncatablePrimes.new()
# Test A
# n = 30
# 2
# 3
# 5
# 7
# 23 2
# 29 2
# ----------
task.rightTruncatablePrime(30)
# Test B
# n = 10000
# 2
# 3
# 5
# 7
# 23 2
# 29 2
# 31 3
# 37 3
# 53 5
# 59 5
# 71 7
# 73 7
# 79 7
# 233 23 2
# 239 23 2
# 293 29 2
# 311 31 3
# 313 31 3
# 317 31 3
# 373 37 3
# 379 37 3
# 593 59 5
# 599 59 5
# 719 71 7
# 733 73 7
# 739 73 7
# 797 79 7
# 2333 233 23 2
# 2339 233 23 2
# 2393 239 23 2
# 2399 239 23 2
# 2939 293 29 2
# 3119 311 31 3
# 3137 313 31 3
# 3733 373 37 3
# 3739 373 37 3
# 3793 379 37 3
# 3797 379 37 3
# 5939 593 59 5
# 7193 719 71 7
# 7331 733 73 7
# 7333 733 73 7
# 7393 739 73 7
# ----------------
# [Remove right digit]
# Example prime = 5939
# 5939
# 593
# 59
# 5
# ----------------------
# All is prime so 5939
# right truncatable prime
task.rightTruncatablePrime(10000)
end
main()Output
Given n : 30
2 3 5 7 23 29
Given n : 10000
2 3 5 7 23 29 31 37 53 59 71 73 79 233 239 293 311 313 317 373 379 593 599 719 733 739 797 2333 2339 2393 2399 2939 3119 3137 3733 3739 3793 3797 5939 7193 7331 7333 7393/*
Scala Program for
Find the all right truncatable primes in n natural numbers
*/
class TruncatablePrimes()
{
// Find all prime numbers which have smaller and equal to
// given number n
def sieveOfEratosthenes(prime: Array[Boolean], n: Int): Unit = {
// Initial two numbers are not prime (0 and 1)
prime(0) = false;
prime(1) = false;
var i: Int = 2;
// Initial 0 and 1 are not prime
// We start to 2
while (i * i <= n)
{
if (prime(i) == true)
{
var j: Int = i * i;
// When i is prime number
// Modify the prime status of all next
// multiplier of location i
while (j <= n)
{
prime(j) = false;
j += i;
}
}
i += 1;
}
}
def rightTruncatablePrime(n: Int): Unit = {
if (n <= 1)
{
return;
}
var prime: Array[Boolean] = Array.fill[Boolean](n + 1)(true);
sieveOfEratosthenes(prime, n);
print("\n Given n : " + n);
print("\n");
var i: Int = 2;
while (i <= n)
{
if (prime(i) == true)
{
var temp: Int = i;
while (temp > 0 && prime(temp) == true)
{
// Remove last digit
temp = temp / 10;
}
if (temp == 0)
{
print(" " + i);
}
}
i += 1;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: TruncatablePrimes = new TruncatablePrimes();
// Test A
// n = 30
/*
2
3
5
7
23 2
29 2
----------
*/
task.rightTruncatablePrime(30);
// Test B
// n = 10000
/*
2
3
5
7
23 2
29 2
31 3
37 3
53 5
59 5
71 7
73 7
79 7
233 23 2
239 23 2
293 29 2
311 31 3
313 31 3
317 31 3
373 37 3
379 37 3
593 59 5
599 59 5
719 71 7
733 73 7
739 73 7
797 79 7
2333 233 23 2
2339 233 23 2
2393 239 23 2
2399 239 23 2
2939 293 29 2
3119 311 31 3
3137 313 31 3
3733 373 37 3
3739 373 37 3
3793 379 37 3
3797 379 37 3
5939 593 59 5
7193 719 71 7
7331 733 73 7
7333 733 73 7
7393 739 73 7
----------------
[Remove right digit]
Example prime = 5939
5939
593
59
5
----------------------
All is prime so 5939
right truncatable prime
*/
task.rightTruncatablePrime(10000);
}
}Output
Given n : 30
2 3 5 7 23 29
Given n : 10000
2 3 5 7 23 29 31 37 53 59 71 73 79 233 239 293 311 313 317 373 379 593 599 719 733 739 797 2333 2339 2393 2399 2939 3119 3137 3733 3739 3793 3797 5939 7193 7331 7333 7393/*
Swift 4 Program for
Find the all right truncatable primes in n natural numbers
*/
class TruncatablePrimes
{
// Find all prime numbers which have smaller and equal to
// given number n
func sieveOfEratosthenes(_ prime: inout[Bool], _ n: Int)
{
// Initial two numbers are not prime (0 and 1)
prime[0] = false;
prime[1] = false;
var i: Int = 2;
// Initial 0 and 1 are not prime
// We start to 2
while (i * i <= n)
{
if (prime[i] == true)
{
var j: Int = i * i;
// When i is prime number
// Modify the prime status of all next
// multiplier of location i
while (j <= n)
{
prime[j] = false;
j += i;
}
}
i += 1;
}
}
func rightTruncatablePrime(_ n: Int)
{
if (n <= 1)
{
return;
}
var prime: [Bool] = Array(repeating: true, count: n + 1);
self.sieveOfEratosthenes(&prime, n);
print("\n Given n : ", n, terminator: "");
print(terminator: "\n");
var i: Int = 2;
while (i <= n)
{
if (prime[i] == true)
{
var temp: Int = i;
while (temp > 0 && prime[temp] == true)
{
// Remove last digit
temp = temp / 10;
}
if (temp == 0)
{
print(" ", i, terminator: "");
}
}
i += 1;
}
}
}
func main()
{
let task: TruncatablePrimes = TruncatablePrimes();
// Test A
// n = 30
/*
2
3
5
7
23 2
29 2
----------
*/
task.rightTruncatablePrime(30);
// Test B
// n = 10000
/*
2
3
5
7
23 2
29 2
31 3
37 3
53 5
59 5
71 7
73 7
79 7
233 23 2
239 23 2
293 29 2
311 31 3
313 31 3
317 31 3
373 37 3
379 37 3
593 59 5
599 59 5
719 71 7
733 73 7
739 73 7
797 79 7
2333 233 23 2
2339 233 23 2
2393 239 23 2
2399 239 23 2
2939 293 29 2
3119 311 31 3
3137 313 31 3
3733 373 37 3
3739 373 37 3
3793 379 37 3
3797 379 37 3
5939 593 59 5
7193 719 71 7
7331 733 73 7
7333 733 73 7
7393 739 73 7
----------------
[Remove right digit]
Example prime = 5939
5939
593
59
5
----------------------
All is prime so 5939
right truncatable prime
*/
task.rightTruncatablePrime(10000);
}
main();Output
Given n : 30
2 3 5 7 23 29
Given n : 10000
2 3 5 7 23 29 31 37 53 59 71 73 79 233 239 293 311 313 317 373 379 593 599 719 733 739 797 2333 2339 2393 2399 2939 3119 3137 3733 3739 3793 3797 5939 7193 7331 7333 7393/*
Kotlin Program for
Find the all right truncatable primes in n natural numbers
*/
class TruncatablePrimes
{
// Find all prime numbers which have smaller and equal to
// given number n
fun sieveOfEratosthenes(prime: Array < Boolean > , n: Int): Unit
{
// Initial two numbers are not prime (0 and 1)
prime[0] = false;
prime[1] = false;
var i: Int = 2;
// Initial 0 and 1 are not prime
// We start to 2
while (i * i <= n)
{
if (prime[i] == true)
{
var j: Int = i * i;
// When i is prime number
// Modify the prime status of all next
// multiplier of location i
while (j <= n)
{
prime[j] = false;
j += i;
}
}
i += 1;
}
}
fun rightTruncatablePrime(n: Int): Unit
{
if (n <= 1)
{
return;
}
var prime: Array < Boolean > = Array(n + 1)
{
true
};
this.sieveOfEratosthenes(prime, n);
print("\n Given n : " + n);
print("\n");
var i: Int = 2;
while (i <= n)
{
if (prime[i] == true)
{
var temp: Int = i;
while (temp > 0 && prime[temp] == true)
{
// Remove last digit
temp = temp / 10;
}
if (temp == 0)
{
print(" " + i);
}
}
i += 1;
}
}
}
fun main(args: Array < String > ): Unit
{
val task: TruncatablePrimes = TruncatablePrimes();
// Test A
// n = 30
/*
2
3
5
7
23 2
29 2
----------
*/
task.rightTruncatablePrime(30);
// Test B
// n = 10000
/*
2
3
5
7
23 2
29 2
31 3
37 3
53 5
59 5
71 7
73 7
79 7
233 23 2
239 23 2
293 29 2
311 31 3
313 31 3
317 31 3
373 37 3
379 37 3
593 59 5
599 59 5
719 71 7
733 73 7
739 73 7
797 79 7
2333 233 23 2
2339 233 23 2
2393 239 23 2
2399 239 23 2
2939 293 29 2
3119 311 31 3
3137 313 31 3
3733 373 37 3
3739 373 37 3
3793 379 37 3
3797 379 37 3
5939 593 59 5
7193 719 71 7
7331 733 73 7
7333 733 73 7
7393 739 73 7
----------------
[Remove right digit]
Example prime = 5939
5939
593
59
5
----------------------
All is prime so 5939
right truncatable prime
*/
task.rightTruncatablePrime(10000);
}Output
Given n : 30
2 3 5 7 23 29
Given n : 10000
2 3 5 7 23 29 31 37 53 59 71 73 79 233 239 293 311 313 317 373 379 593 599 719 733 739 797 2333 2339 2393 2399 2939 3119 3137 3733 3739 3793 3797 5939 7193 7331 7333 7393
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment