/*
 * To input a number n and print all left truncatable numbers till n
 * To be compiled using: gcc -lm
 * For example,if your filename is left_truncatable.c,compile it using: gcc -lm left_truncatable.c 
 * @author-Karan Narain(karan@iitk.ac.in)
 *
*/

#include <stdio.h>
#include <math.h>

int isprime(int n)
{
	int i,count=0;
	for(i=2;i<n;i++)
	{
		if((n%i)==0)
		count++;
	}
	if(count==0 && n!=1)
	return 1;
	else
	return 0;
}

int truncate(int n)
{
	int num_digits=0,m,trunc_n,p;
	m=n;
	//Count the number of digits in m
	while(m>0)
	{
		m=m/10;
		num_digits++;
	}
	p=pow(10,num_digits-1);
	trunc_n=n%p;
	return trunc_n;
}

int left_truncatable(int n)
{
	int x;
	x=n;
	//Return not left truncatable if n is not prime
	if(isprime(x)==0)
	return 0;
	else
	{
		while(x>0)
		{
			x=truncate(x);
			//return not left truncatable as soon as the first non-prime left truncated number is found 
			if(isprime(x)==0)
			return 0;
		}
	}
	//If the control reaches here,it means n is left truncatable
	return 1;

}

int main()
{
	int n,i;
	printf("Enter the value of n\n");
	scanf("%d",&n);
	for(i=1;i<n;i++)
	{
		if(left_truncatable(i)==1)
		printf("%d is left_truncatable\n",i);
	}

return 0;
}