检查一个数是不是全质数？

Question

我对时间限制有疑问。

全素数是指各位的数字都是素数，各位的和是素数，而且这个数也是素数。每次测试的时间限制为 1 秒。其中 t<=10^5 且 1 ≤ n ≤ 2.10^9.

它在测试 54 时超出了 :v。我的解决方案有什么问题？

此外，要求不允许我使用数组。它的目的只是为了使用循环。

#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%10;
        
        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%10;
        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;
}

Answer 1

你可以改进checkPrime执行1/3的迭代次数：

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;
}

Answer 2

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

很抱歉，我没有看到不使用数组的限制，我会以不同的方式处理这个问题。

CheckDigits()可以和Sum()组合在一起，每步查数的时候，最后给出Sum。

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

由于n < 2*10^9，而n是a full prime，它的每一位都是质数，它的最大组成是777777777.

full prime任何其他值的位之和将小于7+7+7+7+7+7+7+7+7+7+7=63.

63以内的素数包括2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61.所以,只有这些值当和为质数时可以被检测到。

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;
}

Answer 3

使用unsigned

给定1 ≤ n ≤ 2.10^9，不需要宽long long。使用 unsigned、int 或迂腐地使用 <stdint.h>.

中的 uint_fast32_t

潜在加速：4x

简化素数检测

避免像 n == 2 这样的检查，直到需要为止。

先检查小除数，而不是 i = 5; i <= n/i; i += 6 然后 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 <= n / i 和 n % i 能够编译成高效的代码，并以一个的价格有效地计算两者。

可以使用 i*i <= n 对比 i <= n / i（给定范围限制）并使用 int 和 div() 进行实验和分析。这样的微优化可能是值得的。通常不会。

潜在加速：2x

偷偷摸摸：字符串文字

Post 有“要求不允许我使用数组”但显然允许 字符串文字 像 "Yes\n" 和 "%d" （从技术上讲是数组）。

如果字符串文字允许，我们可以table查找小测试。

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

    if ("[=11=][=11=][=11=][=11=]"[n%10u]) return false;
    n/=10;
  }
  return true;
}

可能会有点加速 - 更多 parlor trick。

检查一个数是不是全质数？

To check a number is a full prime number or not?

c

primes

numbers