c# optimizing cycle working with big numbers 工作大数

Question

我有这段代码可以在给定范围内查找仅包含 3 和 5 并且是多项式(对称，例如 3553)的数字。问题是数字在 1 到 10^18 之间，所以在某些情况下我必须处理大数字，而使用 BigInteger 会使程序速度太慢，那么有没有办法解决这个问题？这是我的代码:

namespace Lucky_numbers
{
    class Program
    {
        static void Main(string[] args)
        {

            string startString = Console.ReadLine();
            string finishString = Console.ReadLine();
            BigInteger start = BigInteger.Parse(startString);
            BigInteger finish = BigInteger.Parse(finishString);

            int numbersFound = 0;

            for (BigInteger i = start; i <= finish; i++)
            {
                if (Lucky(i.ToString()))
                {
                    if (Polyndrome(i.ToString()))
                    {
                        numbersFound++;
                    }
                }

            }
        }

        static bool Lucky(string number)
        {
            if (number.Contains("1") || number.Contains("2") || number.Contains("4") || number.Contains("6") || number.Contains("7") || number.Contains("8") || number.Contains("9") || number.Contains("0"))
            {
                return false;
            }
            else
            {
                return true;
            }
        }

        static bool Polyndrome(string number)
        {
            bool symetrical = true;

            int middle = number.Length / 2;
            int rightIndex = number.Length - 1;

            for (int leftIndex = 0; leftIndex <= middle; leftIndex++)
            {
                if (number[leftIndex] != number[rightIndex])
                {
                    symetrical = false;
                    break;
                }
                rightIndex--;
            }
            return symetrical;
        }
    }
}

编辑:事实证明它不是 BigInteger，这是我糟糕的实现。

Answer 1

你可以使用 ulong :

Size: Unsigned 64-bit integer

Range: 0 to 18,446,744,073,709,551,615

但我猜 BigInteger 在这里不是问题。我认为您应该创建用于回文创建的算法而不是蛮力 increment+check 解决方案。

奖金

这是我用 5 分钟编写的回文生成器。我认为它会比你的方法快得多。你能测试一下并告诉它速度有多快吗？我对此很好奇。

public class PalyndromeGenerator
{
    private List<string> _results;
    private bool _isGenerated;
    private int _length;
    private char[] _characters;

    private int _middle;
    private char[] _currentItem;

    public PalyndromeGenerator(int length, params char[] characters)
    {
        if (length <= 0)
            throw new ArgumentException("length");
        if (characters == null)
            throw new ArgumentNullException("characters");
        if (characters.Length == 0)
            throw new ArgumentException("characters");

        _length = length;
        _characters = characters;
    }

    public List<string> Results
    {
        get
        {
            if (!_isGenerated)
                throw new InvalidOperationException();

            return _results.ToList();
        }
    }

    public void Generate()
    {
        _middle = (int)Math.Ceiling(_length / 2.0) - 1;
        _results = new List<string>((int)Math.Pow(_characters.Length, _middle + 1));
        _currentItem = new char[_length];

        GeneratePosition(0);

        _isGenerated = true;
    }

    private void GeneratePosition(int position)
    {
        if(position == _middle)
        {
            for (int i = 0; i < _characters.Length; i++)
            {
                _currentItem[position] = _characters[i];
                _currentItem[_length - position - 1] = _characters[i];
                _results.Add(new string(_currentItem));
            }
        }
        else
        {
            for(int i = 0; i < _characters.Length; i++)
            {
                _currentItem[position] = _characters[i];
                _currentItem[_length - position - 1] = _characters[i];
                GeneratePosition(position + 1);
            }
        }
    }
}

用法:

var generator = new PalyndromeGenerator(6, '3', '5');
generator.Generate();
var items = generator.Results.Select(x => ulong.Parse(x)).ToList();