3
\$\begingroup\$

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<stdio.h>
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.

\$\endgroup\$
  • 2
    \$\begingroup\$ Welcome to Code Review. This is the right place for your question, but as a courtesy to other users, you should have declared your cross-post. \$\endgroup\$ – 200_success Apr 2 '17 at 15:05
5
\$\begingroup\$

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\$.

\$\endgroup\$
4
\$\begingroup\$

While your code is in C, your question is really more one of algorithms, so I will give a Python prototype of a partial solution of your problem. (Although -- I would be remiss if I didn't point out that int might not be the best datatype for numbers of that scale, even on 64-bit machines. Perhaps use long long int).

1) There are 10^15 numbers <= 10^15, but only 4^15 numbers consisting of the digits 2,3,5,7. Furthermore 10^15 / 4^15 is nearly 1 million, hence it would be better to find a way to directly iterate over the numbers of the right form. One idea is to take an ordinary number, write it in hex, and then find a way to encode 1 hex digits into a 2-digit sequence in 2,3,5,7, (this works because 4^2 = 16). This isn't trivial and there are other ways, but the potential speed-up is orders of magnitude. Furthermore if you find a way of iterating only over valid candidates, it is enough to check if the numbers you are iterating over are primes. Since I am prototyping, I will use Python's itertools module, which makes it trivial.

2) In checking if a number > 2 is prime, it is enough to check that it is neither even nor divisible by an odd number which is <= its square root. You are using the square root optimization, but you are still needlessly iterating over even candidate divisors.

Here is a Python proof-of-concept. It checks for megaprimes in the range 1 to 10^n, the iteration over candidates would need to be tweaked to change the lower bound:

import itertools,math

def candidates(k):
    #finds all candidate megaprimes with k digits
    for p in itertools.product(['2','3','5','7'],repeat = k):
        yield int(''.join(p))

def isPrime(n):
    if n == 1:
        return False
    elif n == 2:
        return True
    elif n%2 == 0:
        return False
    else:
        for k in range(3,1+int(1+math.sqrt(n)),2):
            if n % k == 0:
                return False
        return True

def findMegaPrimes(n):
    #finds all megaprimes < 10**n
    megas = []
    for k in range(1,n+1):
        for c in candidates(k):
            if isPrime(c):
                megas.append(c)
    return megas

On my machine, it takes Python (which compared to C is a "slow" interpreted language) about 15 seconds to evaluate

len(findMegaPrimes(9))

which evaluates to 23169, the number of megaprimes <= 1 billion. I picked 10^9 since that corresponds to the maximum size of the range that you need to iterate over.

\$\endgroup\$
  • \$\begingroup\$ Re "it would be better to find a way to directly iterate over the numbers of the right form": it's possibly worth narrowing the "of the right form" a bit further to require the final digit to be 3 or 7. \$\endgroup\$ – Peter Taylor Apr 11 '17 at 13:55
  • \$\begingroup\$ And re long long int: uint_64t would be greatly preferable. \$\endgroup\$ – Peter Taylor Apr 11 '17 at 13:57
3
\$\begingroup\$

John and Bijan already reviewed your algorithm then let me go with the boring part of reviewing your C code.

In modern C you do not need to declare all variables at the beginning of the function; do it as late as possible, give them a meaningful name and initialize them only if required (not in this case). Assuming C99:

printf("Insert first and last number (separated by space): ");

int firstNumber, lastNumber;
scanf("%d %d", &firstNumber ,&lastNumber);

int megaPrimeCount = 0;
for(int number=firstNumber; number <= lastNumber; ++i) {
    ...
}

I admit that number instead of i is little bit pedantic in this case but it is to give the idea. Also you're not checking your inputs, it may be an issue or not but it's as simple as:

if (firstNumber < 1 || firstNumber > lastNumber) {
    printf("1 <= first <= last <= 10^15\n");

    return 1;
}

You may want also to move inputting into a separate function like readRange().

Inside your loop the code can be simplified because:

  • You do not need to check != 0 for (i % 2) because integer to boolean conversion is automatic. You may also want to introduce a separate function for that.
  • No need to return int from isMegaPrime(), C99 introduced _Bool type and you may include stdbool.h to use a convenient bool macro.
  • There is not any performance penalty to use prefix or postfix increment but I can't stop myself to double-check the reason there is the postfix every time I see it then...

In code:

if (isOdd(number) && isMegaPrime(number))
    ++megaPrimeCount;

However...why do you put the the optimization to skip even numbers inside this function? You shouldn't span knowledge here and there randomly, this function is already doing too much (reading inputs, counting mega prime numbers and outputting that number):

if (isMegaPrime(number))
    ++megaPrimeCount;

isMegaPrime() can be greatly simplified (note that here I keep exactly your original algorithm, I'm review just coding style). Few things to note:

  • Reduce indentation, else condition of a return does not need to be.
  • You do not need flag, just return whenever appropriate.
  • Use bool instead of int where appropriate.
  • Be consistent with spaces and formatting.
  • Use appropriate names, context and variable name will help you to understand the algorithm. For example temp doesn't help me that much to understand what the function is doing, there is no reason to avoid writing if (!isPrime(number % 10)) but introducing an extra variable (that will be optimized away by the compiler!) will help reader to understand the code.

In code:

bool isMegaPrime(int number) {
    if (!isPrime(number))
        return false;

    while (number != 0) {
        int digit = number % 10;
        if (!isPrime(digit))
            return false;

            n /= 10;
        }

    return true;
}

That while loop hurts me little bit and I'm tempted to change it to see how it will look like with a for (also stopping to overwrite parameter value) but let it be...


isPrime() can have the same treatment we reserved to isMegaPrime():

bool isPrime(int number)
{
    if (number == 1 || isEven(number))
        return false;

    int upperLimit = (int)sqrt(number);
    for (int divisor = 2; divisor <= upperLimit; ++divisor) {
        if (number % divisor == 0)
            return false;
    }

    return true;
}

Now I see that we're always using isPrime() return value negated. I dislike negations because sometimes I do not see them (age?) then I'd rewrite it to be isNotPrime() simplifying both functions (of couse if isPrime() isn't used anywhere else).


As exercise you may also want to add some assertions to your code to enforce the constraints you have. Not such useful in this small snippet but good habit for bigger code bases.


It may not be the case for this code but as you can see, for example in Python, generators like range() are pretty handy and nice. You may enjoy to experiment reading Generators in C. Imagine to write your code like this:

FOR(number, range, firstNumber, lastNumber) {
    ...
}

And:

FOR(divisor, range, 2, (int)sqrt(number)) {
    ...
}

You may find it interesting (if not here then in other applications).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.