c - C中子序列的素性检验

Question

我想打印所有子序列不是素数的素数。例如 881 是可接受的数字(8,8,81,81,88,1 不是素数)但 109 是 Not Acceptable (1,0,9,10 ,19..19 是素数)。我使用掩码找到了每个数字的子序列。所以这里的问题是我找不到单独检查每个数字的子序列的方法。我无法存储子序列，因为我不应该使用数组或函数。你能给我一个建议吗？我是 C 初学者。提前致谢!

#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，
即 1 小于 2 的 4 次方。
此掩码选择四位输入值的所有数字。

一般来说，如果输入值的长度是 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 , 并设置该变量，以便循环将
运行正确的次数。