I've got a problem with a time limit.

A full prime number is one for which the digits are all prime, the sum of the digits is prime, and the number is also prime. Time limit per test is 1 sec. with t<=10^5 and 1 ≤ n ≤ 2.10^9.

It exceeded at test 54 :v. What's wrong with my solution?

Also, the requirements don't allow me to use an array. Its purpose is just to use the loop.

#include<stdio.h>
#include<stdbool.h>

bool checkPrime(long long n) {
    
    if (n==2 || n==3)   return 1;
    if (n < 2 || n%2 == 0 || n%3 == 0)
        return 0;
    for (long long i = 5; i <= n/i; i  = 6) {
        if (n%i == 0)
            return 0;
    }
    for (long long i = 7; i <= n/i; i  = 6) {
        if (n%i == 0)
            return 0;
    }
    return 1;
}

bool checkDigits(long long n){ 
    while (n)
    {
        int i=n;
        
        if (i!=2 && i!=3 && i!=5 &&i !=7)   return 0;
        n/=10;
    }
    return 1;
}

int Sum(long long n){
    int sum=0;
    while (n){
        int i=n;
        sum =i;
        n/=10;
    }
    return sum;
}

bool checkSum(long long n)
{
    long long m=Sum(n);
    return (checkPrime(m));
}

bool isFullPrime(long long n){
    if (checkDigits(n)==0)  return 0;
    if (checkSum(n)==0)   return 0;
    if (checkPrime(n)==0)   return 0;
    else    return 1;
}

int main(){
    
    int t;
    scanf("%d", &t);
    while (t--)
    {
        long long n;
        scanf("%lld", &n);
        
        if (isFullPrime(n))
        {
            printf("Yes\n");
        }
        else
            printf("No\n");                        
    }
    printf("\n");
    return 0;
}

CodePudding user response：

[Wrong]For prime detection, you can take a better approach and try the Sieve of Eratosthenes.

I'm sorry that I don't see a limit to not using arrays, and I'll handle the problem in a different way.

CheckDigits() can be combined with Sum() when checking the number in each step, giving the Sum at the end.

int checkDigits(long long n){
    int sum=0;
    while (n)
    {
        int i=n;
        
        if (i!=2 && i!=3 && i!=5 &&i !=7)   return 0;
        sum  = n;
        n/=10;
    }
    return sum;
}

Since n < 2*10^9, and n is a full prime, each of its digits is prime, its largest composition is 777777777.

The sum of the bits of any other values of full prime will be less than 7 7 7 7 7 7 7 7 7 7 7=63.

Primes within 63 include 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61. So, only these values can be detected when and is prime.

bool checkSum(long long n) {
    
    if (n==2 || n==3 || n==5 || n==7 || n==11 || n==13 || n==17 || n==19 || n==23 || n==29 || n==31 || n==37 || n==41 || n==43 || n==47 || n==53 || n==59 || n==61)   return 1;
    return 0;
}

CodePudding user response：

Use unsigned

Given 1 ≤ n ≤ 2.10^9, there is no need for the wide long long. Use unsigned, int or pedantically uint_fast32_t from <stdint.h>.

Potential speed-up: 4x

Simplify prime detection

Avoid checks like n == 2 until needed.

Check small divisors first rather than i = 5; i <= n/i; i = 6 then i = 7; i <= n/i; i = 6.

bool checkPrime(unsigned n) {
  if (n % 2 == 0) {  // or n&1 == 0 if weak compiler.
    return n == 2;
  }
  if (n % 3 == 0) {
    return n == 3;
  }
  for (unsigned i = 5; i <= n / i; i  = 4) {
    if (n % i == 0) {
      return false;
    }
    i  = 2;
    if (i > n / i) break;
    if (n % i == 0) {
      return false;
    }
  }
  return n > 1;
}

I expect the nearby i <= n / i and n % i to compile into efficient code and effectively compute both for the price of one.

Could experiment and profile with i*i <= n versus i <= n / i (given range limitation) and using int with div(). Such micro-optimizations might be worth it. Usually not though.

Potential speed-up: 2x

Sneaky: string literal

Post has "requirements don't allow me to use an array" but apparently allows string literals like "Yes\n" and "%d" (which are technically arrays).

If string literals allowed, we can do a table look up for small tests.

bool checkDigits(unsigned n){ 
  while (n) {
    // if (i!=2 && i!=3 && i!=5 &&i !=7)   return 0;

    if ("\1\1\0\0\1\0\1\0\1\1"[nu]) return false;
    n/=10;
  }
  return true;
}

May a little speed-up - more of a parlor trick.

CodePudding user response：

You can improve checkPrime to perform 1/3 of the number of iterations:

bool checkPrime(long long n) {
    // handle special cases 0 thru 3
    if (n <= 3)
        return n >= 2;

    // eliminate multiples of 2 or 3
    if (n%2 == 0 || n%3 == 0)
        return 0;

    for (long long i = 5; i*i <= n; i  = 6) {
        if (n%i == 0)
            return 0;
    }

    for (long long i = 7; i*i <= n; i  = 6) {
        if (n%i == 0)
            return 0;
    }

    return 1;
}