Find the all left truncatable primes in n natural numbers
Here given code implementation process.
// C program for
// Find the all left truncatable primes in n natural numbers
#include <stdio.h>
// Find all prime numbers which have smaller and equal to given number n
void sieveOfEratosthenes(int prime[], int n)
{
// Loop controlling variables
int i;
int j;
// 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 (i = 2; i <= n; ++i)
{
prime[i] = 1;
}
// Initial 0 and 1 are not prime
// We start to 2
for (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 (j = i *i; j <= n; j += i)
{
prime[j] = 0;
}
}
}
}
void leftTruncatablePrime(int n)
{
if (n <= 1)
{
return;
}
int prime[n + 1];
sieveOfEratosthenes(prime, n);
printf("\n Given n : %d", n);
printf("\n");
for (int i = 2; i <= n; ++i)
{
if (prime[i] == 1)
{
int temp = i;
int count = 1;
int zero = 0;
// Count number of digits
while (zero == 0 && temp > 9)
{
if (temp % 10 == 0)
{
zero++;
}
temp = temp / 10;
count = count *10;
}
int k = count;
temp = i;
while (zero == 0 && temp > 0 && prime[temp] == 1)
{
// Remove last digit
temp = temp - ((temp / count) *count);
count = count / 10;
}
if (temp == 0)
{
printf("\n %d : ", i);
count = k;
temp = i;
while (temp > 0 && prime[temp] == 1)
{
printf(" %d ", temp);
// Remove last digit
temp = temp - ((temp / count) *count);
count = count / 10;
}
}
}
}
}
int main(int argc, char
const *argv[])
{
// Test A
// n = 30
/*
2 : 2
3 : 3
5 : 5
7 : 7
13 : 13 3
17 : 17 7
23 : 23 3
----------
*/
leftTruncatablePrime(30);
// Test B
// n = 1000
/*
2 : 2
3 : 3
5 : 5
7 : 7
13 : 13 3
17 : 17 7
23 : 23 3
37 : 37 7
43 : 43 3
47 : 47 7
53 : 53 3
67 : 67 7
73 : 73 3
83 : 83 3
97 : 97 7
113 : 113 13 3
137 : 137 37 7
167 : 167 67 7
173 : 173 73 3
197 : 197 97 7
223 : 223 23 3
283 : 283 83 3
313 : 313 13 3
317 : 317 17 7
337 : 337 37 7
347 : 347 47 7
353 : 353 53 3
367 : 367 67 7
373 : 373 73 3
383 : 383 83 3
397 : 397 97 7
443 : 443 43 3
467 : 467 67 7
523 : 523 23 3
547 : 547 47 7
613 : 613 13 3
617 : 617 17 7
643 : 643 43 3
647 : 647 47 7
653 : 653 53 3
673 : 673 73 3
683 : 683 83 3
743 : 743 43 3
773 : 773 73 3
797 : 797 97 7
823 : 823 23 3
853 : 853 53 3
883 : 883 83 3
937 : 937 37 7
947 : 947 47 7
953 : 953 53 3
967 : 967 67 7
983 : 983 83 3
997 : 997 97 7
----------------
[Remove left digit]
Example prime = 823
823
23
3
----------------------
All is prime so 823
left truncatable prime
*/
leftTruncatablePrime(1000);
return 0;
}
Output
Given n : 30
2 : 2
3 : 3
5 : 5
7 : 7
13 : 13 3
17 : 17 7
23 : 23 3
Given n : 1000
2 : 2
3 : 3
5 : 5
7 : 7
13 : 13 3
17 : 17 7
23 : 23 3
37 : 37 7
43 : 43 3
47 : 47 7
53 : 53 3
67 : 67 7
73 : 73 3
83 : 83 3
97 : 97 7
113 : 113 13 3
137 : 137 37 7
167 : 167 67 7
173 : 173 73 3
197 : 197 97 7
223 : 223 23 3
283 : 283 83 3
313 : 313 13 3
317 : 317 17 7
337 : 337 37 7
347 : 347 47 7
353 : 353 53 3
367 : 367 67 7
373 : 373 73 3
383 : 383 83 3
397 : 397 97 7
443 : 443 43 3
467 : 467 67 7
523 : 523 23 3
547 : 547 47 7
613 : 613 13 3
617 : 617 17 7
643 : 643 43 3
647 : 647 47 7
653 : 653 53 3
673 : 673 73 3
683 : 683 83 3
743 : 743 43 3
773 : 773 73 3
797 : 797 97 7
823 : 823 23 3
853 : 853 53 3
883 : 883 83 3
937 : 937 37 7
947 : 947 47 7
953 : 953 53 3
967 : 967 67 7
983 : 983 83 3
997 : 997 97 7
/*
Java Program for
Find the all left 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 leftTruncatablePrime(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;
int count = 1;
int zero = 0;
// Count number of digits
while (zero == 0 && temp > 9)
{
if (temp % 10 == 0)
{
zero++;
}
temp = temp / 10;
count = count * 10;
}
int k = count;
temp = i;
while (zero == 0 && temp > 0 && prime[temp] == true)
{
// Remove last digit
temp = temp - ((temp / count) * count);
count = count / 10;
}
if (temp == 0)
{
System.out.print("\n " + i + " : ");
count = k;
temp = i;
while (temp > 0 && prime[temp] == true)
{
System.out.print(" " + temp);
// Remove last digit
temp = temp - ((temp / count) * count);
count = count / 10;
}
}
}
}
}
public static void main(String[] args)
{
TruncatablePrimes task = new TruncatablePrimes();
// Test A
// n = 30
/*
2 : 2
3 : 3
5 : 5
7 : 7
13 : 13 3
17 : 17 7
23 : 23 3
----------
*/
task.leftTruncatablePrime(30);
// Test B
// n = 1000
/*
2 : 2
3 : 3
5 : 5
7 : 7
13 : 13 3
17 : 17 7
23 : 23 3
37 : 37 7
43 : 43 3
47 : 47 7
53 : 53 3
67 : 67 7
73 : 73 3
83 : 83 3
97 : 97 7
113 : 113 13 3
137 : 137 37 7
167 : 167 67 7
173 : 173 73 3
197 : 197 97 7
223 : 223 23 3
283 : 283 83 3
313 : 313 13 3
317 : 317 17 7
337 : 337 37 7
347 : 347 47 7
353 : 353 53 3
367 : 367 67 7
373 : 373 73 3
383 : 383 83 3
397 : 397 97 7
443 : 443 43 3
467 : 467 67 7
523 : 523 23 3
547 : 547 47 7
613 : 613 13 3
617 : 617 17 7
643 : 643 43 3
647 : 647 47 7
653 : 653 53 3
673 : 673 73 3
683 : 683 83 3
743 : 743 43 3
773 : 773 73 3
797 : 797 97 7
823 : 823 23 3
853 : 853 53 3
883 : 883 83 3
937 : 937 37 7
947 : 947 47 7
953 : 953 53 3
967 : 967 67 7
983 : 983 83 3
997 : 997 97 7
----------------
[Remove left digit]
Example prime = 823
823
23
3
----------------------
All is prime so 823
left truncatable prime
*/
task.leftTruncatablePrime(1000);
}
}
Output
Given n : 30
2 : 2
3 : 3
5 : 5
7 : 7
13 : 13 3
17 : 17 7
23 : 23 3
Given n : 1000
2 : 2
3 : 3
5 : 5
7 : 7
13 : 13 3
17 : 17 7
23 : 23 3
37 : 37 7
43 : 43 3
47 : 47 7
53 : 53 3
67 : 67 7
73 : 73 3
83 : 83 3
97 : 97 7
113 : 113 13 3
137 : 137 37 7
167 : 167 67 7
173 : 173 73 3
197 : 197 97 7
223 : 223 23 3
283 : 283 83 3
313 : 313 13 3
317 : 317 17 7
337 : 337 37 7
347 : 347 47 7
353 : 353 53 3
367 : 367 67 7
373 : 373 73 3
383 : 383 83 3
397 : 397 97 7
443 : 443 43 3
467 : 467 67 7
523 : 523 23 3
547 : 547 47 7
613 : 613 13 3
617 : 617 17 7
643 : 643 43 3
647 : 647 47 7
653 : 653 53 3
673 : 673 73 3
683 : 683 83 3
743 : 743 43 3
773 : 773 73 3
797 : 797 97 7
823 : 823 23 3
853 : 853 53 3
883 : 883 83 3
937 : 937 37 7
947 : 947 47 7
953 : 953 53 3
967 : 967 67 7
983 : 983 83 3
997 : 997 97 7
// Include header file
#include <iostream>
using namespace std;
/*
C++ Program for
Find the all left 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 leftTruncatablePrime(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;
int count = 1;
int zero = 0;
// Count number of digits
while (zero == 0 && temp > 9)
{
if (temp % 10 == 0)
{
zero++;
}
temp = temp / 10;
count = count *10;
}
int k = count;
temp = i;
while (zero == 0 && temp > 0 && prime[temp] == true)
{
// Remove last digit
temp = temp - ((temp / count) *count);
count = count / 10;
}
if (temp == 0)
{
cout << "\n " << i << " : ";
count = k;
temp = i;
while (temp > 0 && prime[temp] == true)
{
cout << " " << temp;
// Remove last digit
temp = temp - ((temp / count) *count);
count = count / 10;
}
}
}
}
}
};
int main()
{
TruncatablePrimes *task = new TruncatablePrimes();
// Test A
// n = 30
/*
2 : 2
3 : 3
5 : 5
7 : 7
13 : 13 3
17 : 17 7
23 : 23 3
----------
*/
task->leftTruncatablePrime(30);
// Test B
// n = 1000
/*
2 : 2
3 : 3
5 : 5
7 : 7
13 : 13 3
17 : 17 7
23 : 23 3
37 : 37 7
43 : 43 3
47 : 47 7
53 : 53 3
67 : 67 7
73 : 73 3
83 : 83 3
97 : 97 7
113 : 113 13 3
137 : 137 37 7
167 : 167 67 7
173 : 173 73 3
197 : 197 97 7
223 : 223 23 3
283 : 283 83 3
313 : 313 13 3
317 : 317 17 7
337 : 337 37 7
347 : 347 47 7
353 : 353 53 3
367 : 367 67 7
373 : 373 73 3
383 : 383 83 3
397 : 397 97 7
443 : 443 43 3
467 : 467 67 7
523 : 523 23 3
547 : 547 47 7
613 : 613 13 3
617 : 617 17 7
643 : 643 43 3
647 : 647 47 7
653 : 653 53 3
673 : 673 73 3
683 : 683 83 3
743 : 743 43 3
773 : 773 73 3
797 : 797 97 7
823 : 823 23 3
853 : 853 53 3
883 : 883 83 3
937 : 937 37 7
947 : 947 47 7
953 : 953 53 3
967 : 967 67 7
983 : 983 83 3
997 : 997 97 7
----------------
[Remove left digit]
Example prime = 823
823
23
3
----------------------
All is prime so 823
left truncatable prime
*/
task->leftTruncatablePrime(1000);
return 0;
}
Output
Given n : 30
2 : 2
3 : 3
5 : 5
7 : 7
13 : 13 3
17 : 17 7
23 : 23 3
Given n : 1000
2 : 2
3 : 3
5 : 5
7 : 7
13 : 13 3
17 : 17 7
23 : 23 3
37 : 37 7
43 : 43 3
47 : 47 7
53 : 53 3
67 : 67 7
73 : 73 3
83 : 83 3
97 : 97 7
113 : 113 13 3
137 : 137 37 7
167 : 167 67 7
173 : 173 73 3
197 : 197 97 7
223 : 223 23 3
283 : 283 83 3
313 : 313 13 3
317 : 317 17 7
337 : 337 37 7
347 : 347 47 7
353 : 353 53 3
367 : 367 67 7
373 : 373 73 3
383 : 383 83 3
397 : 397 97 7
443 : 443 43 3
467 : 467 67 7
523 : 523 23 3
547 : 547 47 7
613 : 613 13 3
617 : 617 17 7
643 : 643 43 3
647 : 647 47 7
653 : 653 53 3
673 : 673 73 3
683 : 683 83 3
743 : 743 43 3
773 : 773 73 3
797 : 797 97 7
823 : 823 23 3
853 : 853 53 3
883 : 883 83 3
937 : 937 37 7
947 : 947 47 7
953 : 953 53 3
967 : 967 67 7
983 : 983 83 3
997 : 997 97 7
// Include namespace system
using System;
/*
Csharp Program for
Find the all left 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 leftTruncatablePrime(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;
int count = 1;
int zero = 0;
// Count number of digits
while (zero == 0 && temp > 9)
{
if (temp % 10 == 0)
{
zero++;
}
temp = temp / 10;
count = count * 10;
}
int k = count;
temp = i;
while (zero == 0 && temp > 0 && prime[temp] == true)
{
// Remove last digit
temp = temp - ((temp / count) * count);
count = count / 10;
}
if (temp == 0)
{
Console.Write("\n " + i + " : ");
count = k;
temp = i;
while (temp > 0 && prime[temp] == true)
{
Console.Write(" " + temp);
// Remove last digit
temp = temp - ((temp / count) * count);
count = count / 10;
}
}
}
}
}
public static void Main(String[] args)
{
TruncatablePrimes task = new TruncatablePrimes();
// Test A
// n = 30
/*
2 : 2
3 : 3
5 : 5
7 : 7
13 : 13 3
17 : 17 7
23 : 23 3
----------
*/
task.leftTruncatablePrime(30);
// Test B
// n = 1000
/*
2 : 2
3 : 3
5 : 5
7 : 7
13 : 13 3
17 : 17 7
23 : 23 3
37 : 37 7
43 : 43 3
47 : 47 7
53 : 53 3
67 : 67 7
73 : 73 3
83 : 83 3
97 : 97 7
113 : 113 13 3
137 : 137 37 7
167 : 167 67 7
173 : 173 73 3
197 : 197 97 7
223 : 223 23 3
283 : 283 83 3
313 : 313 13 3
317 : 317 17 7
337 : 337 37 7
347 : 347 47 7
353 : 353 53 3
367 : 367 67 7
373 : 373 73 3
383 : 383 83 3
397 : 397 97 7
443 : 443 43 3
467 : 467 67 7
523 : 523 23 3
547 : 547 47 7
613 : 613 13 3
617 : 617 17 7
643 : 643 43 3
647 : 647 47 7
653 : 653 53 3
673 : 673 73 3
683 : 683 83 3
743 : 743 43 3
773 : 773 73 3
797 : 797 97 7
823 : 823 23 3
853 : 853 53 3
883 : 883 83 3
937 : 937 37 7
947 : 947 47 7
953 : 953 53 3
967 : 967 67 7
983 : 983 83 3
997 : 997 97 7
----------------
[Remove left digit]
Example prime = 823
823
23
3
----------------------
All is prime so 823
left truncatable prime
*/
task.leftTruncatablePrime(1000);
}
}
Output
Given n : 30
2 : 2
3 : 3
5 : 5
7 : 7
13 : 13 3
17 : 17 7
23 : 23 3
Given n : 1000
2 : 2
3 : 3
5 : 5
7 : 7
13 : 13 3
17 : 17 7
23 : 23 3
37 : 37 7
43 : 43 3
47 : 47 7
53 : 53 3
67 : 67 7
73 : 73 3
83 : 83 3
97 : 97 7
113 : 113 13 3
137 : 137 37 7
167 : 167 67 7
173 : 173 73 3
197 : 197 97 7
223 : 223 23 3
283 : 283 83 3
313 : 313 13 3
317 : 317 17 7
337 : 337 37 7
347 : 347 47 7
353 : 353 53 3
367 : 367 67 7
373 : 373 73 3
383 : 383 83 3
397 : 397 97 7
443 : 443 43 3
467 : 467 67 7
523 : 523 23 3
547 : 547 47 7
613 : 613 13 3
617 : 617 17 7
643 : 643 43 3
647 : 647 47 7
653 : 653 53 3
673 : 673 73 3
683 : 683 83 3
743 : 743 43 3
773 : 773 73 3
797 : 797 97 7
823 : 823 23 3
853 : 853 53 3
883 : 883 83 3
937 : 937 37 7
947 : 947 47 7
953 : 953 53 3
967 : 967 67 7
983 : 983 83 3
997 : 997 97 7
package main
import "fmt"
/*
Go Program for
Find the all left 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
// Set the initial (2 to n element is prime)
for i := 2 ; i <= n ; i++ {
prime[i] = true
}
// 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) leftTruncatablePrime(n int) {
if n <= 1 {
return
}
var prime = make([] bool, n + 1)
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
var count int = 1
var zero int = 0
// Count number of digits
for (zero == 0 && temp > 9) {
if temp % 10 == 0 {
zero++
}
temp = temp / 10
count = count * 10
}
var k int = count
temp = i
for (zero == 0 && temp > 0 && prime[temp] == true) {
// Remove last digit
temp = temp - ((temp / count) * count)
count = count / 10
}
if temp == 0 {
fmt.Print("\n ", i, " : ")
count = k
temp = i
for (temp > 0 && prime[temp] == true) {
fmt.Print(" ", temp)
// Remove last digit
temp = temp - ((temp / count) * count)
count = count / 10
}
}
}
}
}
func main() {
var task * TruncatablePrimes = getTruncatablePrimes()
// Test A
// n = 30
/*
2 : 2
3 : 3
5 : 5
7 : 7
13 : 13 3
17 : 17 7
23 : 23 3
----------
*/
task.leftTruncatablePrime(30)
// Test B
// n = 1000
/*
2 : 2
3 : 3
5 : 5
7 : 7
13 : 13 3
17 : 17 7
23 : 23 3
37 : 37 7
43 : 43 3
47 : 47 7
53 : 53 3
67 : 67 7
73 : 73 3
83 : 83 3
97 : 97 7
113 : 113 13 3
137 : 137 37 7
167 : 167 67 7
173 : 173 73 3
197 : 197 97 7
223 : 223 23 3
283 : 283 83 3
313 : 313 13 3
317 : 317 17 7
337 : 337 37 7
347 : 347 47 7
353 : 353 53 3
367 : 367 67 7
373 : 373 73 3
383 : 383 83 3
397 : 397 97 7
443 : 443 43 3
467 : 467 67 7
523 : 523 23 3
547 : 547 47 7
613 : 613 13 3
617 : 617 17 7
643 : 643 43 3
647 : 647 47 7
653 : 653 53 3
673 : 673 73 3
683 : 683 83 3
743 : 743 43 3
773 : 773 73 3
797 : 797 97 7
823 : 823 23 3
853 : 853 53 3
883 : 883 83 3
937 : 937 37 7
947 : 947 47 7
953 : 953 53 3
967 : 967 67 7
983 : 983 83 3
997 : 997 97 7
----------------
[Remove left digit]
Example prime = 823
823
23
3
----------------------
All is prime so 823
left truncatable prime
*/
task.leftTruncatablePrime(1000)
}
Output
Given n : 30
2 : 2
3 : 3
5 : 5
7 : 7
13 : 13 3
17 : 17 7
23 : 23 3
Given n : 1000
2 : 2
3 : 3
5 : 5
7 : 7
13 : 13 3
17 : 17 7
23 : 23 3
37 : 37 7
43 : 43 3
47 : 47 7
53 : 53 3
67 : 67 7
73 : 73 3
83 : 83 3
97 : 97 7
113 : 113 13 3
137 : 137 37 7
167 : 167 67 7
173 : 173 73 3
197 : 197 97 7
223 : 223 23 3
283 : 283 83 3
313 : 313 13 3
317 : 317 17 7
337 : 337 37 7
347 : 347 47 7
353 : 353 53 3
367 : 367 67 7
373 : 373 73 3
383 : 383 83 3
397 : 397 97 7
443 : 443 43 3
467 : 467 67 7
523 : 523 23 3
547 : 547 47 7
613 : 613 13 3
617 : 617 17 7
643 : 643 43 3
647 : 647 47 7
653 : 653 53 3
673 : 673 73 3
683 : 683 83 3
743 : 743 43 3
773 : 773 73 3
797 : 797 97 7
823 : 823 23 3
853 : 853 53 3
883 : 883 83 3
937 : 937 37 7
947 : 947 47 7
953 : 953 53 3
967 : 967 67 7
983 : 983 83 3
997 : 997 97 7
<?php
/*
Php Program for
Find the all left 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 leftTruncatablePrime($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;
$count = 1;
$zero = 0;
// Count number of digits
while ($zero == 0 && $temp > 9)
{
if ($temp % 10 == 0)
{
$zero++;
}
$temp = (int)($temp / 10);
$count = $count * 10;
}
$k = $count;
$temp = $i;
while ($zero == 0 && $temp > 0 && $prime[$temp] == true)
{
// Remove last digit
$temp = $temp - (((int)($temp / $count)) * $count);
$count = (int)($count / 10);
}
if ($temp == 0)
{
echo("\n ".$i.
" : ");
$count = $k;
$temp = $i;
while ($temp > 0 && $prime[$temp] == true)
{
echo(" ".$temp);
// Remove last digit
$temp = $temp - (((int)($temp / $count)) * $count);
$count = (int)($count / 10);
}
}
}
}
}
}
function main()
{
$task = new TruncatablePrimes();
// Test A
// n = 30
/*
2 : 2
3 : 3
5 : 5
7 : 7
13 : 13 3
17 : 17 7
23 : 23 3
----------
*/
$task->leftTruncatablePrime(30);
// Test B
// n = 1000
/*
2 : 2
3 : 3
5 : 5
7 : 7
13 : 13 3
17 : 17 7
23 : 23 3
37 : 37 7
43 : 43 3
47 : 47 7
53 : 53 3
67 : 67 7
73 : 73 3
83 : 83 3
97 : 97 7
113 : 113 13 3
137 : 137 37 7
167 : 167 67 7
173 : 173 73 3
197 : 197 97 7
223 : 223 23 3
283 : 283 83 3
313 : 313 13 3
317 : 317 17 7
337 : 337 37 7
347 : 347 47 7
353 : 353 53 3
367 : 367 67 7
373 : 373 73 3
383 : 383 83 3
397 : 397 97 7
443 : 443 43 3
467 : 467 67 7
523 : 523 23 3
547 : 547 47 7
613 : 613 13 3
617 : 617 17 7
643 : 643 43 3
647 : 647 47 7
653 : 653 53 3
673 : 673 73 3
683 : 683 83 3
743 : 743 43 3
773 : 773 73 3
797 : 797 97 7
823 : 823 23 3
853 : 853 53 3
883 : 883 83 3
937 : 937 37 7
947 : 947 47 7
953 : 953 53 3
967 : 967 67 7
983 : 983 83 3
997 : 997 97 7
----------------
[Remove left digit]
Example prime = 823
823
23
3
----------------------
All is prime so 823
left truncatable prime
*/
$task->leftTruncatablePrime(1000);
}
main();
Output
Given n : 30
2 : 2
3 : 3
5 : 5
7 : 7
13 : 13 3
17 : 17 7
23 : 23 3
Given n : 1000
2 : 2
3 : 3
5 : 5
7 : 7
13 : 13 3
17 : 17 7
23 : 23 3
37 : 37 7
43 : 43 3
47 : 47 7
53 : 53 3
67 : 67 7
73 : 73 3
83 : 83 3
97 : 97 7
113 : 113 13 3
137 : 137 37 7
167 : 167 67 7
173 : 173 73 3
197 : 197 97 7
223 : 223 23 3
283 : 283 83 3
313 : 313 13 3
317 : 317 17 7
337 : 337 37 7
347 : 347 47 7
353 : 353 53 3
367 : 367 67 7
373 : 373 73 3
383 : 383 83 3
397 : 397 97 7
443 : 443 43 3
467 : 467 67 7
523 : 523 23 3
547 : 547 47 7
613 : 613 13 3
617 : 617 17 7
643 : 643 43 3
647 : 647 47 7
653 : 653 53 3
673 : 673 73 3
683 : 683 83 3
743 : 743 43 3
773 : 773 73 3
797 : 797 97 7
823 : 823 23 3
853 : 853 53 3
883 : 883 83 3
937 : 937 37 7
947 : 947 47 7
953 : 953 53 3
967 : 967 67 7
983 : 983 83 3
997 : 997 97 7
/*
Node JS Program for
Find the all left 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;
}
}
}
}
leftTruncatablePrime(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;
var count = 1;
var zero = 0;
// Count number of digits
while (zero == 0 && temp > 9)
{
if (temp % 10 == 0)
{
zero++;
}
temp = parseInt(temp / 10);
count = count * 10;
}
var k = count;
temp = i;
while (zero == 0 && temp > 0 && prime[temp] == true)
{
// Remove last digit
temp = temp - ((parseInt(temp / count)) * count);
count = parseInt(count / 10);
}
if (temp == 0)
{
process.stdout.write("\n " + i + " : ");
count = k;
temp = i;
while (temp > 0 && prime[temp] == true)
{
process.stdout.write(" " + temp);
// Remove last digit
temp = temp - ((parseInt(temp / count)) * count);
count = parseInt(count / 10);
}
}
}
}
}
}
function main()
{
var task = new TruncatablePrimes();
// Test A
// n = 30
/*
2 : 2
3 : 3
5 : 5
7 : 7
13 : 13 3
17 : 17 7
23 : 23 3
----------
*/
task.leftTruncatablePrime(30);
// Test B
// n = 1000
/*
2 : 2
3 : 3
5 : 5
7 : 7
13 : 13 3
17 : 17 7
23 : 23 3
37 : 37 7
43 : 43 3
47 : 47 7
53 : 53 3
67 : 67 7
73 : 73 3
83 : 83 3
97 : 97 7
113 : 113 13 3
137 : 137 37 7
167 : 167 67 7
173 : 173 73 3
197 : 197 97 7
223 : 223 23 3
283 : 283 83 3
313 : 313 13 3
317 : 317 17 7
337 : 337 37 7
347 : 347 47 7
353 : 353 53 3
367 : 367 67 7
373 : 373 73 3
383 : 383 83 3
397 : 397 97 7
443 : 443 43 3
467 : 467 67 7
523 : 523 23 3
547 : 547 47 7
613 : 613 13 3
617 : 617 17 7
643 : 643 43 3
647 : 647 47 7
653 : 653 53 3
673 : 673 73 3
683 : 683 83 3
743 : 743 43 3
773 : 773 73 3
797 : 797 97 7
823 : 823 23 3
853 : 853 53 3
883 : 883 83 3
937 : 937 37 7
947 : 947 47 7
953 : 953 53 3
967 : 967 67 7
983 : 983 83 3
997 : 997 97 7
----------------
[Remove left digit]
Example prime = 823
823
23
3
----------------------
All is prime so 823
left truncatable prime
*/
task.leftTruncatablePrime(1000);
}
main();
Output
Given n : 30
2 : 2
3 : 3
5 : 5
7 : 7
13 : 13 3
17 : 17 7
23 : 23 3
Given n : 1000
2 : 2
3 : 3
5 : 5
7 : 7
13 : 13 3
17 : 17 7
23 : 23 3
37 : 37 7
43 : 43 3
47 : 47 7
53 : 53 3
67 : 67 7
73 : 73 3
83 : 83 3
97 : 97 7
113 : 113 13 3
137 : 137 37 7
167 : 167 67 7
173 : 173 73 3
197 : 197 97 7
223 : 223 23 3
283 : 283 83 3
313 : 313 13 3
317 : 317 17 7
337 : 337 37 7
347 : 347 47 7
353 : 353 53 3
367 : 367 67 7
373 : 373 73 3
383 : 383 83 3
397 : 397 97 7
443 : 443 43 3
467 : 467 67 7
523 : 523 23 3
547 : 547 47 7
613 : 613 13 3
617 : 617 17 7
643 : 643 43 3
647 : 647 47 7
653 : 653 53 3
673 : 673 73 3
683 : 683 83 3
743 : 743 43 3
773 : 773 73 3
797 : 797 97 7
823 : 823 23 3
853 : 853 53 3
883 : 883 83 3
937 : 937 37 7
947 : 947 47 7
953 : 953 53 3
967 : 967 67 7
983 : 983 83 3
997 : 997 97 7
# Python 3 Program for
# Find the all left 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 leftTruncatablePrime(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
count = 1
zero = 0
# Count number of digits
while (zero == 0 and temp > 9) :
if (temp % 10 == 0) :
zero += 1
temp = int(temp / 10)
count = count * 10
k = count
temp = i
while (zero == 0 and temp > 0 and prime[temp] == True) :
# Remove last digit
temp = temp - ((int(temp / count)) * count)
count = int(count / 10)
if (temp == 0) :
print("\n ", i ," : ", end = "")
count = k
temp = i
while (temp > 0 and prime[temp] == True) :
print(" ", temp, end = "")
# Remove last digit
temp = temp - ((int(temp / count)) * count)
count = int(count / 10)
i += 1
def main() :
task = TruncatablePrimes()
# Test A
# n = 30
# 2 : 2
# 3 : 3
# 5 : 5
# 7 : 7
# 13 : 13 3
# 17 : 17 7
# 23 : 23 3
# ----------
task.leftTruncatablePrime(30)
# Test B
# n = 1000
# 2 : 2
# 3 : 3
# 5 : 5
# 7 : 7
# 13 : 13 3
# 17 : 17 7
# 23 : 23 3
# 37 : 37 7
# 43 : 43 3
# 47 : 47 7
# 53 : 53 3
# 67 : 67 7
# 73 : 73 3
# 83 : 83 3
# 97 : 97 7
# 113 : 113 13 3
# 137 : 137 37 7
# 167 : 167 67 7
# 173 : 173 73 3
# 197 : 197 97 7
# 223 : 223 23 3
# 283 : 283 83 3
# 313 : 313 13 3
# 317 : 317 17 7
# 337 : 337 37 7
# 347 : 347 47 7
# 353 : 353 53 3
# 367 : 367 67 7
# 373 : 373 73 3
# 383 : 383 83 3
# 397 : 397 97 7
# 443 : 443 43 3
# 467 : 467 67 7
# 523 : 523 23 3
# 547 : 547 47 7
# 613 : 613 13 3
# 617 : 617 17 7
# 643 : 643 43 3
# 647 : 647 47 7
# 653 : 653 53 3
# 673 : 673 73 3
# 683 : 683 83 3
# 743 : 743 43 3
# 773 : 773 73 3
# 797 : 797 97 7
# 823 : 823 23 3
# 853 : 853 53 3
# 883 : 883 83 3
# 937 : 937 37 7
# 947 : 947 47 7
# 953 : 953 53 3
# 967 : 967 67 7
# 983 : 983 83 3
# 997 : 997 97 7
# ----------------
# [Remove left digit]
# Example prime = 823
# 823
# 23
# 3
# ----------------------
# All is prime so 823
# left truncatable prime
task.leftTruncatablePrime(1000)
if __name__ == "__main__": main()
Output
Given n : 30
2 : 2
3 : 3
5 : 5
7 : 7
13 : 13 3
17 : 17 7
23 : 23 3
Given n : 1000
2 : 2
3 : 3
5 : 5
7 : 7
13 : 13 3
17 : 17 7
23 : 23 3
37 : 37 7
43 : 43 3
47 : 47 7
53 : 53 3
67 : 67 7
73 : 73 3
83 : 83 3
97 : 97 7
113 : 113 13 3
137 : 137 37 7
167 : 167 67 7
173 : 173 73 3
197 : 197 97 7
223 : 223 23 3
283 : 283 83 3
313 : 313 13 3
317 : 317 17 7
337 : 337 37 7
347 : 347 47 7
353 : 353 53 3
367 : 367 67 7
373 : 373 73 3
383 : 383 83 3
397 : 397 97 7
443 : 443 43 3
467 : 467 67 7
523 : 523 23 3
547 : 547 47 7
613 : 613 13 3
617 : 617 17 7
643 : 643 43 3
647 : 647 47 7
653 : 653 53 3
673 : 673 73 3
683 : 683 83 3
743 : 743 43 3
773 : 773 73 3
797 : 797 97 7
823 : 823 23 3
853 : 853 53 3
883 : 883 83 3
937 : 937 37 7
947 : 947 47 7
953 : 953 53 3
967 : 967 67 7
983 : 983 83 3
997 : 997 97 7
# Ruby Program for
# Find the all left 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 leftTruncatablePrime(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
count = 1
zero = 0
# Count number of digits
while (zero == 0 && temp > 9)
if (temp % 10 == 0)
zero += 1
end
temp = temp / 10
count = count * 10
end
k = count
temp = i
while (zero == 0 && temp > 0 && prime[temp] == true)
# Remove last digit
temp = temp - ((temp / count) * count)
count = count / 10
end
if (temp == 0)
print("\n ", i ," : ")
count = k
temp = i
while (temp > 0 && prime[temp] == true)
print(" ", temp)
# Remove last digit
temp = temp - ((temp / count) * count)
count = count / 10
end
end
end
i += 1
end
end
end
def main()
task = TruncatablePrimes.new()
# Test A
# n = 30
# 2 : 2
# 3 : 3
# 5 : 5
# 7 : 7
# 13 : 13 3
# 17 : 17 7
# 23 : 23 3
# ----------
task.leftTruncatablePrime(30)
# Test B
# n = 1000
# 2 : 2
# 3 : 3
# 5 : 5
# 7 : 7
# 13 : 13 3
# 17 : 17 7
# 23 : 23 3
# 37 : 37 7
# 43 : 43 3
# 47 : 47 7
# 53 : 53 3
# 67 : 67 7
# 73 : 73 3
# 83 : 83 3
# 97 : 97 7
# 113 : 113 13 3
# 137 : 137 37 7
# 167 : 167 67 7
# 173 : 173 73 3
# 197 : 197 97 7
# 223 : 223 23 3
# 283 : 283 83 3
# 313 : 313 13 3
# 317 : 317 17 7
# 337 : 337 37 7
# 347 : 347 47 7
# 353 : 353 53 3
# 367 : 367 67 7
# 373 : 373 73 3
# 383 : 383 83 3
# 397 : 397 97 7
# 443 : 443 43 3
# 467 : 467 67 7
# 523 : 523 23 3
# 547 : 547 47 7
# 613 : 613 13 3
# 617 : 617 17 7
# 643 : 643 43 3
# 647 : 647 47 7
# 653 : 653 53 3
# 673 : 673 73 3
# 683 : 683 83 3
# 743 : 743 43 3
# 773 : 773 73 3
# 797 : 797 97 7
# 823 : 823 23 3
# 853 : 853 53 3
# 883 : 883 83 3
# 937 : 937 37 7
# 947 : 947 47 7
# 953 : 953 53 3
# 967 : 967 67 7
# 983 : 983 83 3
# 997 : 997 97 7
# ----------------
# [Remove left digit]
# Example prime = 823
# 823
# 23
# 3
# ----------------------
# All is prime so 823
# left truncatable prime
task.leftTruncatablePrime(1000)
end
main()
Output
Given n : 30
2 : 2
3 : 3
5 : 5
7 : 7
13 : 13 3
17 : 17 7
23 : 23 3
Given n : 1000
2 : 2
3 : 3
5 : 5
7 : 7
13 : 13 3
17 : 17 7
23 : 23 3
37 : 37 7
43 : 43 3
47 : 47 7
53 : 53 3
67 : 67 7
73 : 73 3
83 : 83 3
97 : 97 7
113 : 113 13 3
137 : 137 37 7
167 : 167 67 7
173 : 173 73 3
197 : 197 97 7
223 : 223 23 3
283 : 283 83 3
313 : 313 13 3
317 : 317 17 7
337 : 337 37 7
347 : 347 47 7
353 : 353 53 3
367 : 367 67 7
373 : 373 73 3
383 : 383 83 3
397 : 397 97 7
443 : 443 43 3
467 : 467 67 7
523 : 523 23 3
547 : 547 47 7
613 : 613 13 3
617 : 617 17 7
643 : 643 43 3
647 : 647 47 7
653 : 653 53 3
673 : 673 73 3
683 : 683 83 3
743 : 743 43 3
773 : 773 73 3
797 : 797 97 7
823 : 823 23 3
853 : 853 53 3
883 : 883 83 3
937 : 937 37 7
947 : 947 47 7
953 : 953 53 3
967 : 967 67 7
983 : 983 83 3
997 : 997 97 7
/*
Scala Program for
Find the all left 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 leftTruncatablePrime(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;
var count: Int = 1;
var zero: Int = 0;
// Count number of digits
while (zero == 0 && temp > 9)
{
if (temp % 10 == 0)
{
zero += 1;
}
temp = temp / 10;
count = count * 10;
}
var k: Int = count;
temp = i;
while (zero == 0 && temp > 0 && prime(temp) == true)
{
// Remove last digit
temp = temp - ((temp / count) * count);
count = count / 10;
}
if (temp == 0)
{
print("\n " + i + " : ");
count = k;
temp = i;
while (temp > 0 && prime(temp) == true)
{
print(" " + temp);
// Remove last digit
temp = temp - ((temp / count) * count);
count = count / 10;
}
}
}
i += 1;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: TruncatablePrimes = new TruncatablePrimes();
// Test A
// n = 30
/*
2 : 2
3 : 3
5 : 5
7 : 7
13 : 13 3
17 : 17 7
23 : 23 3
----------
*/
task.leftTruncatablePrime(30);
// Test B
// n = 1000
/*
2 : 2
3 : 3
5 : 5
7 : 7
13 : 13 3
17 : 17 7
23 : 23 3
37 : 37 7
43 : 43 3
47 : 47 7
53 : 53 3
67 : 67 7
73 : 73 3
83 : 83 3
97 : 97 7
113 : 113 13 3
137 : 137 37 7
167 : 167 67 7
173 : 173 73 3
197 : 197 97 7
223 : 223 23 3
283 : 283 83 3
313 : 313 13 3
317 : 317 17 7
337 : 337 37 7
347 : 347 47 7
353 : 353 53 3
367 : 367 67 7
373 : 373 73 3
383 : 383 83 3
397 : 397 97 7
443 : 443 43 3
467 : 467 67 7
523 : 523 23 3
547 : 547 47 7
613 : 613 13 3
617 : 617 17 7
643 : 643 43 3
647 : 647 47 7
653 : 653 53 3
673 : 673 73 3
683 : 683 83 3
743 : 743 43 3
773 : 773 73 3
797 : 797 97 7
823 : 823 23 3
853 : 853 53 3
883 : 883 83 3
937 : 937 37 7
947 : 947 47 7
953 : 953 53 3
967 : 967 67 7
983 : 983 83 3
997 : 997 97 7
----------------
[Remove left digit]
Example prime = 823
823
23
3
----------------------
All is prime so 823
left truncatable prime
*/
task.leftTruncatablePrime(1000);
}
}
Output
Given n : 30
2 : 2
3 : 3
5 : 5
7 : 7
13 : 13 3
17 : 17 7
23 : 23 3
Given n : 1000
2 : 2
3 : 3
5 : 5
7 : 7
13 : 13 3
17 : 17 7
23 : 23 3
37 : 37 7
43 : 43 3
47 : 47 7
53 : 53 3
67 : 67 7
73 : 73 3
83 : 83 3
97 : 97 7
113 : 113 13 3
137 : 137 37 7
167 : 167 67 7
173 : 173 73 3
197 : 197 97 7
223 : 223 23 3
283 : 283 83 3
313 : 313 13 3
317 : 317 17 7
337 : 337 37 7
347 : 347 47 7
353 : 353 53 3
367 : 367 67 7
373 : 373 73 3
383 : 383 83 3
397 : 397 97 7
443 : 443 43 3
467 : 467 67 7
523 : 523 23 3
547 : 547 47 7
613 : 613 13 3
617 : 617 17 7
643 : 643 43 3
647 : 647 47 7
653 : 653 53 3
673 : 673 73 3
683 : 683 83 3
743 : 743 43 3
773 : 773 73 3
797 : 797 97 7
823 : 823 23 3
853 : 853 53 3
883 : 883 83 3
937 : 937 37 7
947 : 947 47 7
953 : 953 53 3
967 : 967 67 7
983 : 983 83 3
997 : 997 97 7
/*
Swift 4 Program for
Find the all left 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 leftTruncatablePrime(_ 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;
var count: Int = 1;
var zero: Int = 0;
// Count number of digits
while (zero == 0 && temp > 9)
{
if (temp % 10 == 0)
{
zero += 1;
}
temp = temp / 10;
count = count * 10;
}
let k: Int = count;
temp = i;
while (zero == 0 && temp > 0 && prime[temp] == true)
{
// Remove last digit
temp = temp - ((temp / count) * count);
count = count / 10;
}
if (temp == 0)
{
print("\n ", i ," : ", terminator: "");
count = k;
temp = i;
while (temp > 0 && prime[temp] == true)
{
print(" ", temp, terminator: "");
// Remove last digit
temp = temp - ((temp / count) * count);
count = count / 10;
}
}
}
i += 1;
}
}
}
func main()
{
let task: TruncatablePrimes = TruncatablePrimes();
// Test A
// n = 30
/*
2 : 2
3 : 3
5 : 5
7 : 7
13 : 13 3
17 : 17 7
23 : 23 3
----------
*/
task.leftTruncatablePrime(30);
// Test B
// n = 1000
/*
2 : 2
3 : 3
5 : 5
7 : 7
13 : 13 3
17 : 17 7
23 : 23 3
37 : 37 7
43 : 43 3
47 : 47 7
53 : 53 3
67 : 67 7
73 : 73 3
83 : 83 3
97 : 97 7
113 : 113 13 3
137 : 137 37 7
167 : 167 67 7
173 : 173 73 3
197 : 197 97 7
223 : 223 23 3
283 : 283 83 3
313 : 313 13 3
317 : 317 17 7
337 : 337 37 7
347 : 347 47 7
353 : 353 53 3
367 : 367 67 7
373 : 373 73 3
383 : 383 83 3
397 : 397 97 7
443 : 443 43 3
467 : 467 67 7
523 : 523 23 3
547 : 547 47 7
613 : 613 13 3
617 : 617 17 7
643 : 643 43 3
647 : 647 47 7
653 : 653 53 3
673 : 673 73 3
683 : 683 83 3
743 : 743 43 3
773 : 773 73 3
797 : 797 97 7
823 : 823 23 3
853 : 853 53 3
883 : 883 83 3
937 : 937 37 7
947 : 947 47 7
953 : 953 53 3
967 : 967 67 7
983 : 983 83 3
997 : 997 97 7
----------------
[Remove left digit]
Example prime = 823
823
23
3
----------------------
All is prime so 823
left truncatable prime
*/
task.leftTruncatablePrime(1000);
}
main();
Output
Given n : 30
2 : 2
3 : 3
5 : 5
7 : 7
13 : 13 3
17 : 17 7
23 : 23 3
Given n : 1000
2 : 2
3 : 3
5 : 5
7 : 7
13 : 13 3
17 : 17 7
23 : 23 3
37 : 37 7
43 : 43 3
47 : 47 7
53 : 53 3
67 : 67 7
73 : 73 3
83 : 83 3
97 : 97 7
113 : 113 13 3
137 : 137 37 7
167 : 167 67 7
173 : 173 73 3
197 : 197 97 7
223 : 223 23 3
283 : 283 83 3
313 : 313 13 3
317 : 317 17 7
337 : 337 37 7
347 : 347 47 7
353 : 353 53 3
367 : 367 67 7
373 : 373 73 3
383 : 383 83 3
397 : 397 97 7
443 : 443 43 3
467 : 467 67 7
523 : 523 23 3
547 : 547 47 7
613 : 613 13 3
617 : 617 17 7
643 : 643 43 3
647 : 647 47 7
653 : 653 53 3
673 : 673 73 3
683 : 683 83 3
743 : 743 43 3
773 : 773 73 3
797 : 797 97 7
823 : 823 23 3
853 : 853 53 3
883 : 883 83 3
937 : 937 37 7
947 : 947 47 7
953 : 953 53 3
967 : 967 67 7
983 : 983 83 3
997 : 997 97 7
/*
Kotlin Program for
Find the all left 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 leftTruncatablePrime(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;
var count: Int = 1;
var zero: Int = 0;
// Count number of digits
while (zero == 0 && temp > 9)
{
if (temp % 10 == 0)
{
zero += 1;
}
temp = temp / 10;
count = count * 10;
}
val k: Int = count;
temp = i;
while (zero == 0 && temp > 0 && prime[temp] == true)
{
// Remove last digit
temp = temp - ((temp / count) * count);
count = count / 10;
}
if (temp == 0)
{
print("\n " + i + " : ");
count = k;
temp = i;
while (temp > 0 && prime[temp] == true)
{
print(" " + temp);
// Remove last digit
temp = temp - ((temp / count) * count);
count = count / 10;
}
}
}
i += 1;
}
}
}
fun main(args: Array < String > ): Unit
{
val task: TruncatablePrimes = TruncatablePrimes();
// Test A
// n = 30
/*
2 : 2
3 : 3
5 : 5
7 : 7
13 : 13 3
17 : 17 7
23 : 23 3
----------
*/
task.leftTruncatablePrime(30);
// Test B
// n = 1000
/*
2 : 2
3 : 3
5 : 5
7 : 7
13 : 13 3
17 : 17 7
23 : 23 3
37 : 37 7
43 : 43 3
47 : 47 7
53 : 53 3
67 : 67 7
73 : 73 3
83 : 83 3
97 : 97 7
113 : 113 13 3
137 : 137 37 7
167 : 167 67 7
173 : 173 73 3
197 : 197 97 7
223 : 223 23 3
283 : 283 83 3
313 : 313 13 3
317 : 317 17 7
337 : 337 37 7
347 : 347 47 7
353 : 353 53 3
367 : 367 67 7
373 : 373 73 3
383 : 383 83 3
397 : 397 97 7
443 : 443 43 3
467 : 467 67 7
523 : 523 23 3
547 : 547 47 7
613 : 613 13 3
617 : 617 17 7
643 : 643 43 3
647 : 647 47 7
653 : 653 53 3
673 : 673 73 3
683 : 683 83 3
743 : 743 43 3
773 : 773 73 3
797 : 797 97 7
823 : 823 23 3
853 : 853 53 3
883 : 883 83 3
937 : 937 37 7
947 : 947 47 7
953 : 953 53 3
967 : 967 67 7
983 : 983 83 3
997 : 997 97 7
----------------
[Remove left digit]
Example prime = 823
823
23
3
----------------------
All is prime so 823
left truncatable prime
*/
task.leftTruncatablePrime(1000);
}
Output
Given n : 30
2 : 2
3 : 3
5 : 5
7 : 7
13 : 13 3
17 : 17 7
23 : 23 3
Given n : 1000
2 : 2
3 : 3
5 : 5
7 : 7
13 : 13 3
17 : 17 7
23 : 23 3
37 : 37 7
43 : 43 3
47 : 47 7
53 : 53 3
67 : 67 7
73 : 73 3
83 : 83 3
97 : 97 7
113 : 113 13 3
137 : 137 37 7
167 : 167 67 7
173 : 173 73 3
197 : 197 97 7
223 : 223 23 3
283 : 283 83 3
313 : 313 13 3
317 : 317 17 7
337 : 337 37 7
347 : 347 47 7
353 : 353 53 3
367 : 367 67 7
373 : 373 73 3
383 : 383 83 3
397 : 397 97 7
443 : 443 43 3
467 : 467 67 7
523 : 523 23 3
547 : 547 47 7
613 : 613 13 3
617 : 617 17 7
643 : 643 43 3
647 : 647 47 7
653 : 653 53 3
673 : 673 73 3
683 : 683 83 3
743 : 743 43 3
773 : 773 73 3
797 : 797 97 7
823 : 823 23 3
853 : 853 53 3
883 : 883 83 3
937 : 937 37 7
947 : 947 47 7
953 : 953 53 3
967 : 967 67 7
983 : 983 83 3
997 : 997 97 7
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