C# Find every number divisible by 3, in a string of numbers

This is still vulnerable to overflows, but it would take a very long string indeed to reach that point:

class Program
{
    static void Main(string[] args)
    {
        Console.Write("Enter a string of numbers: ");
        string Nums = Console.ReadLine();          
        Console.WriteLine("The following numbers are divisble by 3: ");

        foreach(var result in DivisibleByThree(Nums))
        {
            Console.WriteLine(result);
        }
        
        Console.ReadKey(true);
    }

    public static IEnumerable<string> DivisibleByThree(string input)
    {
        for (int i = 0; i < input.Length; i++)
        {
            for(int j = input.Length; j > i; j--)
            {
                string segment = input.Substring(i, j-i);                      
                if (SumOfDigits(segment) % 3 == 0)
                {
                    yield return segment;                                                    
                }
            }
        }
    }

    public static int SumOfDigits(string digits)
    {
        return digits.Where(c => char.IsDigit(c)).Select(c => c-'0').Sum();
    }
}

See it work here:

https://dotnetfiddle.net/KacyAD

And since someone suggested recursion, I thought that'd be fun to try. I didn't quite get as far as I wanted (removing both loops and using recursion as the only repetition mechanism), but this does work:

public static IEnumerable<string> DivisibleByThree(string input)
{
    if (input.Length > 1)
    {
       foreach(var item in DivisibleByThree(input.Substring(0, input.Length-1))) 
       {
           yield return item;
       }
    }
    while(input.Length > 0)
    {
        if ( SumOfDigits(input) % 3 == 0) yield return input;
        input = input.Substring(1);
    }
}

But that's the boring recursion. From a pure performance standpoint, it still spends a lot of time summing the same sequences of digits. There's a probably a way to use recursion to preserve prior work on each recursive call, and in that way make this run significantly faster.

That is, rather than start with a big string and check progressively smaller segments, start with the small string and with each check add the sum for the just the additional digit:

public static IEnumerable<string> DivisibleByThree(string input)
{
    for(int i = input.Length - 1; i>=0; i--)
    {
        foreach(var item in DivisibleByThreeR(input.Substring(i, input.Length - i), 0, 0, 0)) yield return item;
    }
}

public static IEnumerable<string> DivisibleByThreeR(string input, int startPos, int nextPos, int sum)
{
    sum += input[nextPos] - '0';
    if (sum % 3 == 0) yield return input.Substring(startPos, nextPos - startPos + 1);
    if (++nextPos < input.Length) 
    {
        foreach (var item in DivisibleByThreeR(input, startPos, nextPos, sum)) yield return item;
    }
}

I'm not sure this is really any faster. I didn't benchmark or test at all beyond getting the right result. In fact, I suspect the iterators will eat up any improvements over the pure-loop version.

There's also probably a way to move the loop in the outer method also into the recursive function thereby optimize even further. But it was a nice exercise.

Here's my final fiddle if anyone else wants to play:

https://dotnetfiddle.net/dGFWNx

Here's a solution close to your code that uses BigInteger (you need .NET5+). This shall eliminate the risk of running into OverflowException. Please note that there can be duplicates in the output (you didn't say if you want to see them).

using System.Numerics;

class Program
{
    static void Main(string[] args)
    {
        #region FindAllNumbersDivisibleBy3
        Console.Write("Enter a string of numbers: ");
        string Nums = Console.ReadLine();
        List<BigInteger> results = new();
    
        for (int i = 0; i < Nums.Length; i++)
        {
            for (int j = Nums.Length; j >= i; j--)
            {
                try
                {
                    string substring = Nums.Substring(i, j - i);
                    if (BigInteger.TryParse(substring, out var bi) && BigInteger.ModPow(bi, 1, 3).IsZero)
                    {
                        results.Add(bi);
                    }
                }
                catch (Exception e)
                {
                    Console.WriteLine(e.Message);
                }
    
            }
        }
        Console.WriteLine("The following numbers are divisible by 3:");
        for (int i = 0; i < results.Count; i++)
        {
            Console.WriteLine(results[i]);
        }
    
        Console.ReadLine();
        #endregion
    }
}

Something that will work even with numbers other than 3 and 9 would be to implement long division and only keep track of the carry remainder (added a Linq version since it seemed like an appropriate problem for it):

static bool IsDivisibleBy(string input, long divBy = 3)
{
    long remainder = 0;
    foreach (char c in input)
    {
        var num = Convert.ToInt64(c);
        remainder = ((remainder * 10) + num) % divBy;
    }
    return remainder == 0;
}

static bool IsDivisibleByLinq(string input, long divBy = 3)
{
    return input.Select(c => Convert.ToInt64(c))
                .Aggregate(0L, (remainder, num) => 
                          ((remainder * 10) + num) % divBy) == 0;
}