Program to find megaPrime numbers between 2 given integers

A number is said to be megaPrime if it is prime, and all its digits are also prime.

Example:

53 is megaPrime, but 35 is not as it is divisible by 5 and 7.
13 is not a megaPrime number as it contains 1, which is non-prime.
INPUT

Two integer numbers, first and last are entered.
OUTPUT

Display the number of megaPrimes in the inteval between first and last, both inclusive.
CONSTRAINTS

1 <= first <= last <= 10^15

last - first <= 10^9

/* PROGRAM TO FIND MEGA PRIME NUMBERS BETWEEN TWO GIVEN INTEGERS */

#include
int isPrime(int);
int isMegaPrime(int);

int main(void)
{
int i=0,st,sp,count=0;
    scanf("%d%d",&st,&sp);
    for(i=st;i<=sp;i++){
        if((i%2)!=0 && isMegaPrime(i)==1)
            count++;
    }

    printf("%d",count);
    return 0;
}

int isPrime(int n)
{
    int i=0,flag=0;
    if(n==1)
        return 0;
    else
    {    
        int t=sqrt(n);
        for(i=2;i<=t;i++){
            if((n%i)==0){
                flag=1;
                break;
            }
        }
    }
    if(flag==1)
        return 0;
    else
        return 1;
}

int isMegaPrime( int n)
{
    int i=0,flag=0,temp=0;
    if(isPrime(n)==0)
        return 0;
    else{
        while (n!=0){
            temp=n%10;
            flag=isPrime(temp);
            if(flag==0)
                return 0;
            n/=10;
            
        }
    }
    if(flag==1)
        return 1;
    else 
        return 0;
}

Please suggest the possible optimizations.

I think John Coleman did a good job explaining speeding up the testing for mega-primality, but you're still using trial division to test for primality. The Miller-Rabin test is much faster, and can be made deterministic given the size of your range.

The algorithm starts by checking if \$n\$ is 1 or even. These cases are trivial, and should return 0 unless \$n = 2\$.

Next we take n-1 and remove the largest power of 2. Put another way we want to find s and d such that \$2^sd = n - 1\$ and d is odd. For example, if \$n = 49\$, \$n - 1 = 2^43\$, so \$s = 4\$ and \$d = 3\$.

Next we pick a random number for \$a\$ such that \$1 \lt a \lt n - 1\$. Now we make a loop on \$r\$ where \$r\$ goes from 0 to \$s - 1\$ inclusively. If for all values of r:

\$a^{2^rd} \% n \ne n - 1\$ and \$a^d\%n\ne1 % n != 1\$, then \$n\$ is composite. Otherwise, \$n\$ has a large probability of being prime. If you test every \$a\$ where \$a = {2, 3, 5, 7, 11, 13, 17, 19, 23}\$ and \$n\$ comes up as a likely prime for every time, it is prime.

If you are unfamiliar with this you may want to do \$a^b \% c\$ one step at a time, but computing \$a^b\$ may take a long time, and will quite likely result in an overflow error.

Use this trick:

• \$a^b \%c =\$

• If \$b = 0\$ then 1

• If \$b\$ is odd then \$(a^{b-1} \% c ) b \% c\$

• If \$b\$ is even then \$(a^{\frac{b}{2}} \% c)^2 \% c\$

This way, the number is constantly being reduced, and as long as recursion is used, the time will scale logarithmically with the size of \$b\$.

StackExchange Code Review Q#159620, answer score: 5