如何实现无数组统计给定数字可组成的质数个数？

任务需求 #

编写程序统计给定数字的各位数字可组成的质数数量，规则：数字不可重复使用（除非原数字本身存在重复数字）。举两个例子：

• 输入123时输出应为5，所有可能组合集合{1,2,3,12,13,21,23,123,132,213,231,312,321}里有5个质数；
• 输入133时，需从集合{1,3,13,31,33,133,313,331}中统计质数。

疑问 #

能否不使用数组实现该程序？搜索后没找到解决方案，求思路。

尝试的代码（存在问题） #

我写了下面的代码，但没法生成预期数字：输入123时，一位数处理接近正确，但三位数处理有问题。

System.Console.WriteLine("Enter the number: ");
int number = Convert.ToInt32(Console.ReadLine());
int enteredNumber = number;
int length = 0;
while (number != 0)
{
    length++;
    number /= 10;
}

System.Console.WriteLine($"{length} length");
number = enteredNumber;
int nDigit = 1;
int count = 0;
int temp = number;

while (nDigit <= length)
{
    int n = nDigit;

    while (number != 0)
    {
        int digit = number % 10;

        if (nDigit == 1 && isPrime(digit))
        {
            System.Console.WriteLine("1-digit prime number : " + digit);
            count++;
        }
        else
        {
            int tempNewNumber = digit * Convert.ToInt32(Math.Pow(10, Convert.ToDouble(nDigit - 1)));
            int newNumber = tempNewNumber;

            while (temp != 0)
            {

                if (nDigit - 2 >= 0)
                {
                    newNumber += (temp % 10) * Convert.ToInt32(Math.Pow(10, Convert.ToDouble(nDigit - 2)));
                    nDigit--;
                }

                if (nDigit == 1)
                {
                    System.Console.WriteLine("in while : " + newNumber);
                    if (isPrime(newNumber))
                    {
                        System.Console.WriteLine("prime number : " + newNumber);
                        count++;
                    }
                    newNumber = tempNewNumber;
                    nDigit = n;
                }
                temp /= 10;
            }
            nDigit = n;
            temp = enteredNumber;

        }
        number /= 10;
    }
    number = enteredNumber;

    nDigit++;
}

System.Console.WriteLine("Count : " + count);


}


static bool isPrime(int num)
{
    if (num <= 1) return false;
    int i = 2;
    while (i <= num / 2)
    {
        if (num % i == 0)
            return false;

        i++;
    }

    return true;
}

无数组实现思路 #

不用数组的核心是用位掩码标记已使用的数字，配合迭代生成所有组合，同时处理重复数字的去重：

1. 位掩码标记已用数字
   把原数字的每一位对应二进制的一个位，比如3位数字用3位二进制数表示使用状态：001代表第一位被用，010代表第二位，100代表第三位。通过位运算判断哪些数字还没被选，避免重复。

2. 迭代生成所有长度的组合
   从1位到原数字的总长度，遍历所有可能的位掩码（掩码中1的个数等于当前组合长度），根据掩码提取对应数字位，组合成新数后判断是否为质数。

3. 重复数字去重
   如果原数字有重复位（比如133），生成组合时会出现重复数。可以通过判断：当遇到重复数字且前面的相同数字未被使用时，跳过当前组合，避免重复生成；同时用一个整数存储已统计过的质数，防止重复计数。

修正后的无数组实现代码 #

using System;

class Program
{
    static void Main()
    {
        Console.WriteLine("Enter the number: ");
        int number = Convert.ToInt32(Console.ReadLine());
        int original = number;
        int digitCount = 0;
        int temp = original;
        
        // 统计数字的总位数
        while (temp != 0)
        {
            digitCount++;
            temp /= 10;
        }

        int primeCount = 0;
        // 用整数存储已统计的质数（每三位存一个，适配数字长度不超过3位的情况）
        int seenNumbers = 0;

        // 遍历所有可能的位掩码，从1到(1<<digitCount)-1
        for (int mask = 1; mask < (1 << digitCount); mask++)
        {
            int currentNum = 0;
            int tempNum = original;
            int currentMask = mask;
            bool duplicateConflict = false;
            int usedDigitCount = 0;

            // 根据掩码生成当前组合的数字
            for (int i = 0; i < digitCount; i++)
            {
                int digit = tempNum % 10;
                tempNum /= 10;

                if ((currentMask & 1) == 1)
                {
                    // 检查是否有重复数字且前面的相同数字未被使用，避免重复生成组合
                    int checkMask = mask;
                    int checkTemp = original;
                    bool duplicateFound = false;
                    for (int j = 0; j < i; j++)
                    {
                        int checkDigit = checkTemp % 10;
                        checkTemp /= 10;
                        if (checkDigit == digit && (checkMask & 1) == 0)
                        {
                            duplicateFound = true;
                            break;
                        }
                        checkMask >>= 1;
                    }
                    if (duplicateFound)
                    {
                        duplicateConflict = true;
                        break;
                    }

                    currentNum += digit * (int)Math.Pow(10, usedDigitCount);
                    usedDigitCount++;
                }
                currentMask >>= 1;
            }

            if (duplicateConflict)
                continue;

            // 检查当前数字是否已经被统计过
            bool alreadyCounted = false;
            int checkSeen = seenNumbers;
            for (int i = 0; i < primeCount; i++)
            {
                int storedNum = checkSeen % 1000;
                checkSeen /= 1000;
                if (storedNum == currentNum)
                {
                    alreadyCounted = true;
                    break;
                }
            }

            if (!alreadyCounted && IsPrime(currentNum))
            {
                Console.WriteLine("质数: " + currentNum);
                primeCount++;
                seenNumbers = seenNumbers * 1000 + currentNum;
            }
        }

        Console.WriteLine("质数总数: " + primeCount);
    }

    // 优化后的质数判断函数
    static bool IsPrime(int num)
    {
        if (num <= 1) return false;
        if (num == 2) return true;
        if (num % 2 == 0) return false;
        // 只遍历奇数到平方根，提升效率
        for (int i = 3; i <= Math.Sqrt(num); i += 2)
        {
            if (num % i == 0)
                return false;
        }
        return true;
    }
}

代码说明 #

• 位掩码mask精准控制哪些数字位被选中生成组合；
• 重复数字处理逻辑避免生成重复的组合；
• 用整数seenNumbers存储已统计的质数，无需数组即可去重；
• 质数判断函数做了优化，提前排除偶数，减少循环次数，提升效率。

内容的提问来源于stack exchange，提问作者Aphar Magaramova