Friday 31 May 2013

CIRCULAR PRIMES



Circular primes are prime numbers which upon cyclic rotation also give prime numbers. For example: 197 is  prime number and its cyclic rotations 719 and 917 are also prime . Therefore 197 is a circular prime. It is to be noted that cyclic rotations and permutations are different concepts. Cyclic rotations are a subset of permutations of a given number.                                                                                                                                                                                                                                    
                                                              
There are 13 circular primes below 100:2 ,3 ,5 ,7 ,11 ,13 ,17 ,31 ,37 ,71 ,73 ,79 ,97.
Here is an interesting program to find the circular prime numbers between a given range of numbers input by the user. First of all, we’ll check whether the number is prime or not. If the number is prime then its cyclic rotations are further checked.
The circular primes with at least 2 digits can consist of combinations of only 1,3,7 or 9 as the numbers consisting of digits 2,4,6,8,0 or 5 will be either divisible by 2 or 5 and hence are not prime. Therefore the code can be shortened by checking that if any digit of the number is a multiple of 2 or 5 then the number can be skipped. Since 2 and 5 are prime ,if they are included in the range, they can be separately checked.  

Source code # 1 (in C++)
/*****************************************************************************/

#include<iostream.h>
#include<conio.h>
#include<math.h>

void main()
{
                clrscr();
                int c=0,r,flag,d;
                unsigned long num,num1,num2,div,i,j,n1,n2,nn;
                cout<<"\n Enter the starting number of the range:";
                cin>>n1;
                cout<<"\n Enter the ending number of the range:";
                cin>>n2;
                for(i=n1;i<=n2;i++)
                {
                                if(i==1)
                                goto a;
                                if(i==2 || i==5)
                                goto b;
                                num2=i;
                                while(num2)  //if number consists of a digit that is multiple of 2 or 5 
                                                                              //then no need to check it.
                                {
                                                d=num2%10;
                                                if(d==5 || d%2==0)
                                                goto a;
                                                num2=num2/10;
                                }
                                num=i;
                                for(j=2;j<=sqrt(num);j++) //to check whether number is prime or not.
                                {
                                                if(num%j==0)
                                                goto a;
                                }
                                flag=0;
                                while(num>9)      //to count the number of digits in the number.
                                {
                                                num=num/10;
                                                flag++;
                                }
                                div=pow(10,flag);
                                num1=i;
                                while(flag) //here cyclic rotations of the number are formed and
                                                 //checked whether  they are prime or not.
                                {
                                                r=num1%10;
                                                nn=div*r+(num1/10);
                                                for(j=2;j<=sqrt(nn);j++)
                                                {
                                                                if(nn%j==0)
                                                                goto a;
                                                }
                                                num1=nn;
                                                flag=flag-1;
                                }
                                b:
                                c=c+1; // to count the number of circular primes.
                                cout<<"\t"<<i;
                                a:
                }
                cout<<"\n the number of circular primes between "
                <<n1<<" and "<<n2<<" are:"<<c;
                getch();
}
/*****************************************************************************/

Source code # 2 (in C) 

/*******************************************************************************/
#include<stdio.h>
#include<math.h>
#include<conio.h>

int isprime(long);
int main()
{
long int upper_limit,lower_limit,i,j,copy_i,new_num;
int ccounter=0,counter=0;
/*counter is used for counting the
total number of digits of any number

ccounter is used for counting
that how many numbers
that are circular permutations of
original number are primes
*/
clrscr();
printf("ENTER THE LOWER LIMIT : ");
scanf("%ld",&upper_limit);
printf("ENTER THE UPPERLIMIT : ");
scanf("%ld",&lower_limit);

for(i=upper_limit;i<=lower_limit;i++)
{
counter=0;ccounter=0;

copy_i=i;
while(copy_i)
{
counter++;
copy_i/=10;
}

copy_i=i;
if(isprime(i))
{
for(j=0;j<counter;j++)
{
new_num=copy_i%10;
copy_i/=10;
new_num*=(long)pow(10,(counter-1));
new_num+=copy_i;


if(isprime(new_num))
ccounter++;

copy_i=new_num;
}
if(ccounter==counter)
{
printf("%ld\t",i);
}
}
}
printf("\n\nDONE!!!");
getch();
return 1;
}

int isprime(long num)
{
long j;

for(j=2;j<=(num/2);j++)
{
if(num%j==0)
{
return 0;
}
}
return 1;
}
/******************************************************************************/
Output :-

No comments:

Post a Comment