Differentiating between two integers in a string

Question

I have a problem I've been working on where I want to identify all integers within a given string that are prime (numbers that are divisible only by 1 and itself).

The logic I have written for this problem is done and correct, but in debugging and testing the code I came upon an interesting scenario.

Say I have the following string This 15 i2s the45best str7ng 1n th3 w0r17ld

Now when the above string was ran through my program it determined that the prime numbers in the string were 5, 2, 5, 7, 3, 7, which is correct. However, what if I wanted my program to check to see if 15 was prime instead of individually checking if 1 is a prime and then checking to see if 5 is a prime, or if I want to check the primality of 45 instead of 4 and 5 individually?

I'd like to also extend this question to numbers that are, in general, greater than 1 digit long.

Below is the code I have for accomplishing what I've described:

private static void Main(string[] args)
{
    string sentence = "This 15 i2s the45best str7ng 1n th3 w0r17ld";
    string primes = string.Empty;
    foreach(char c in sentence)
    {
        if (char.IsDigit(c))
        {
            if (isPrime(c - 48))
            {
                primes += c;
            }
        }
    }
    Console.WriteLine(primes.Length > 0 ? $"The prime numbers in\n\n\t{sentence}\n\nare {string.Join<char>(", ", primes)}" : $"There exist no primes in\n\n\t{sentence}");
    Console.ReadLine();
}

private static bool isPrime(int number)
{
    if(number == 3 || number == 2)
    {
        return true;
    }
    if(number % 2 == 0)
    {
        return false;
    }
    for(int i = 3; i < (int)Math.Sqrt(number); i++)
    {
        if(number % i == 0)
        {
            return false;
        }
    }
    return true;
}

Obviously, you have to write some code that treats a sequence of digits as a number. — Andrey Nasonov, Nov 12 '17 at 19:05

Dmitry Bychenko · Answer 1 · 2017-11-12T20:02:30.090

Let's split the problem in two smaller ones:

  1. Extract all integers from the string
  2. Check integer value if it is a prime one

First subtask can be solved with help of regular expressions:

  // IEnumerable<int> - we assume that all integers within the string are small enough.
  // If we can face an arbitrary integer sample12345678901234567890123456
  // BigInteger (instead of int) is the solution
  private static IEnumerable<int> ExtractIntValues(string source) {
    return Regex
     .Matches(source, "[0-9]+")
     .OfType<Match>()
     .Select(match => int.Parse(match.Value));
  }

Second subtask can be implemented as (your code slightly optimized)

  private static bool isPrime(int number) {
    if (number <= 1) // 0 and 1 are not primes
      return false;
    if (number % 2 == 0)
      return n == 2;

    int n = (int) (Math.Sqrt(number) + 0.5);

    for (int i = 3; i < n; i += 2) // we have to check odd divisors only
      if (number % i == 0)
        return false;

    return true;   
  }

Finally:

  string sentence = "This 15 i2s the45best str7ng 1n th3 w0r17ld";

  int[] primes = ExtractIntValues(sentence)
    .Where(number => IsPrime(number))
    .ToArray(); 

  Console.WriteLine($"string '{sentence}' contains {primes.Length} prime numbers: {string.Join(", ", primes)}");

oRole · Answer 2 · 2017-11-12T20:07:45.110

You could do it like that:

private static void Main(string[] args)
{
    string sentence = "This 15 i2s the45best str7ng 1n th3 w0r17ld";
    List<int> primes = new List<int>();
    for (int i = 0; i < sentence.Length; i++)
    {  
        // iterate 'sentence' as long as the neighbour of the current character is a valid digit, then add these digits up to a string
        string nStr = string.Empty;
        while (char.IsDigit(sentence[i]))
        {
            nStr += sentence[i];
            i++;
        }

        // if a number was detected and it is a prime number, add it to our list
        if (!string.IsNullOrWhiteSpace(nStr))
        {
            int n = int.Parse(nStr);
            if (IsPrime(n))
                primes.Add(n);
        }
    }

    Console.WriteLine(primes.Count > 0 ? $"The prime numbers in\n\n\t{sentence}\n\nare {string.Join(", ", primes.ToArray())}" : $"There exist no primes in\n\n\t{sentence}");
    Console.ReadLine();
}

public static bool IsPrime(int number)
{
    if (number == 1)
        return false;
    if (number == 2)
        return true;
    if (number % 2 == 0)
        return false;

    var boundary = (int)Math.Floor(Math.Sqrt(number));

    for (int i = 3; i <= boundary; i += 2)
    {
        if (number % i == 0)
            return false;
    }

    return true;
}

Please note:
I took another IsPrime method, because there was something wrong with yours. Check it out here: IsPrime

`(int)Math.Floor(Math.Sqrt(number));` is *dangerous* code: what if `Math.Sqrt` for given `p * p` returns not `p`, but `p - ε`? Say, `Sqrt(25) == 4.9999999999999997` on some platform, FPU etc? — Dmitry Bychenko, Nov 12 '17 at 20:14

Differentiating between two integers in a string

2 Answers2