C语言中子序列的素性检验

Question

我想打印所有不是子序列的质数示例881是一个可接受的数字(8，8，81，81，88，1不是质数)，但109是不可接受的(1，0，9，10，19.19是质数).I通过使用mask.So找到每个数字的子序列这里的问题是我找不到一种方法来单独检查每个数字的子序列我不能存储我的子序列，因为我不应该使用数组或functions.Can你给我一个建议吗?我预先是一个C begginer.Thanks！

#include <stdio.h>

#define MAXNUMB 100

int main (void) 
{
    int i,j,x,l,mask,max=1,mult,sub,c;
    for (i = 11 ; i < MAXNUMB; i += 2 ) {
       //
        for (j = 3; j * j <= i; j += 2) {  
           if (i % j == 0) { 
               break; 
           }           
        }
        if (j * j > i) {

            int length = 0;
            int tmp=i;
            while (tmp != 0) {
                tmp /= 10;
                length++;
            }


           for (x=1;x<length*2;x++) {
              mask=x;
              mult=1;
              sub=0;
              int num=i;
              while ( num != 0 ) {
                  if ( mask % 2 == 1 ) {
                      sub += num % 10 * mult;
                      mult *= 10; 
                   }
                   num /= 10;
                   mask /= 2;

                }
           //the problem is here.If we use a printf command for the subsequences printf("%d \n,sub); it runs perfectly


                int k=sub;

                for (l = 2; l * l <= k; l ++) {  
                    if (k % l == 0) { 
                    printf("%d \n",i);
                    break; 
                   }           
                }   


            }


        }


    }
    return 0;
}

Answer 1

当它们使用子例程时，我发现这样的事情更容易理解。例如，对于从11到MAXNUMB的每个整数，您必须决定该整数是否具有任何质数子序列。因此，编写一个函数int hasPrimeSubsequence(int value)。在这个函数中，您需要查看每个子序列，并确定它是否是质数。因此，编写一个函数int isPrime(int value)。

因为计算一个数的子序列是非常重要的，所以我甚至会写一个函数int getSubsequenceOfNumberUsingMask(int value, int mask)。函数int getMaximumMask(int value)也会很方便。

然后，hasPrimeSubsequence的实现如下所示：

/* Returns 1 if the value has a prime subsequence, 0 if it does not. */
int hasPrimeSubsequence(int value)
{
  int has_found_prime = 0;
  int maximum_mask    = getMaximumMask(value);
  for (mask = 1; mask <= maximum_mask; ++mask )
  {
    int subsequence = getSubsequenceOfNumberUsingMask(value, mask);
    if (isPrime(subsequence))
    {
      /* We found a prime subsequence, so the answer is "yes". */
      has_found_prime = 1;
      break;
    }
  }

  return has_found_prime;
}

请注意，当我们通过值将数字传递给子例程时，子例程可以随意修改这些值(比如mask /= 2)，而不会影响调用者中的值，因此我们不必创建这么多不同名称的数字副本。

变量has_found_prime用于跟踪是否有任何子序列是质数。它从0 (false)开始，因为我们还没有找到任何质数子序列(我们甚至还没有找到一个)。但是，如果任何子序列是质数，我们就设置has_found_prime = 1 (true)，并且永远不会将其设置回0。

另一种实现方式是甚至不必费心使用变量has_found_prime；如果找到质数，只需立即返回1，如果到达函数末尾时没有返回1，则没有质数子序列，因此返回0。但有些人不喜欢这种风格。

您可能会注意到，此hasPrimeSubsequence实现在开始尝试掩码之前不会测试输入值是否为质数。这是因为我假设最后一个掩码将选择原始数字的所有数字，也就是说，数字本身是子序列之一。如果您发现这不起作用，那么您所要做的就是在for循环之前插入类似这样的内容(或者更好，在实际调用getMaximumMask之前)：

  if (isPrime(value))
  {
    has_found_prime = 1;
  }

补充说明：这里显然应该使用的“掩码”被视为二进制数，其二进制位数与要从中提取子序列的数字(我称之为“输入值”)中的十进制位数相同。

每个掩码从输入值中选择一个子序列；掩码的每一位确定输入值的相应十进制数是否包括在该子序列中。例如，如果输入值是1237，则仅使用掩码的最低有效四位，并且

掩码0001 (二进制)选择子序列7，

掩码0010 (二进制)选择子序列3，

掩码1000 (二进制)选择子序列1，

掩码1011 (二进制)选择子序列137，依此类推。

使用四位的最高值掩码是二进制1111，它是2的4次方的1减。此掩码选择四位输入值的所有数字。

一般来说，如果输入值的长度是N个十进制数字，那么最大可能的掩码是2的N次方，减1。这也是可能的子序列的数量(不包括空子序列，它根本不包含数字)。

如果你没有尝试从1到(2的N次方，减1)的每个掩码，那么你没有尝试所有的子序列，并且你可能得到一个错误的答案(猜测数字没有质子序列，而实际上它有一个)。

简单地尝试掩码值从1到length (位数)，甚至到2*length，几乎总是错误的。

一条评论建议如下所示

  for (mask = 1; mask < (1 << length); ++mask)

这是可行的，因为(1 << length)是2的length幂，并且使用<时，实际尝试的最后一个掩码比这个值小1。我仍然发现，如果使用合理的自解释名称(如maximum_mask或end_of_masks )创建一个变量，并设置该变量，以便循环运行正确的次数，则代码的可读性会更好。