0
\$\begingroup\$

I have the following code to get the prime numbers between a range of numbers. Is this the best and fastest method?

int[] numberCollection = Enumerable.Range(startNum,Count).ToArray<int>();
string primeNumbers = string.Join(",", from number in numberCollection 
                                       where (IsPrime(number)==true)
                                       select number);

Where :

  • startNum is the starting number
  • Count is the number of numbers in the collection
  • IsPrime is a method defined as follows:

      private static bool IsPrime(int number)
      {
          for (int i = 2; i < number/2; i++)
              if (number % i == 0) return false;
          return true;
      }
    
\$\endgroup\$
1
  • \$\begingroup\$ This is a very poor way of generating prime numbers within a range in case the range is large. You should try and do more research about the Sieve of Eratosthenes GeeksForGeeks article \$\endgroup\$ Oct 14, 2015 at 6:05

1 Answer 1

1
\$\begingroup\$

If you are only executing this once, it should work fine as is. If you are going to execute it more than once per century, you should use the Sieve of Eratosthenes, as suggested by Somnath Rakshit.

Using the algorithm as described on wikipedia:

static class MathExtensions
{
    static public List<int> GetPrimes(int start, int end)
    {
        List<int> res = new List<int>();

        // 1. Create a list of consecutive integers from 2 through n: (2, 3, 4, ..., n).
        int[] numbers = Enumerable.Range(0, end).ToArray();

        // 2. Initially, let p equal 2, the first prime number.
        int idx = 2;
        do
        {
            // If the number is in range, add it to the result
            if (numbers[idx] >= start)
            {
                res.Add(numbers[idx]);
            }

            // 3. Starting from p, enumerate its multiples by counting to n in increments of p, and mark them in the list (these will be 2p, 3p, 4p, ... ; the p itself should not be marked).
            for (var i = idx; i < end; i += idx)
            {
                numbers[i] = 0;
            }

            // 4. Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this new number (which is the next prime), and repeat from step 3.
            while (idx < end && numbers[idx] == 0)
            {
                idx++;
            }
        }
        while (idx < end);

        return res;
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.