[C#] Spoj - Liczby pierwsze. Jak to zoptymalizować?

Witam. Mam wypisać liczby pierwsze na przedziale a...b. Input wygląda tak

Ilość przedziałów
Początek_przedziału1 Koniec_przedziału 1
Początek_przedziału2 Koniec_przedziału 2

np.

2
1 10
60 90

Niestety mój kod działa, lecz zbyt długo się wykonuję.

    using System;
     
    public class Test
    {
    	    static int BeforeSpace(string before) /// konwertuje napis z wejścia 
                                            /// i zwraca liczbę otwierającą przedział
            {
                int length = before.Length;
                string output = "";
     
                for (int i=0; i<length; i++)
                {
                   if (!char.IsWhiteSpace(before[i]))
                   {
                       output += before[i];
                   }
                     else
                   {
                      return Convert.ToInt32(output);
                   }
                }
             return 0;
            }
            static int AfterSpace(string after) /// konwertuje napis z wejścia 
                                              /// i zwraca liczbę zamykającą przedział
            {
                int length = after.Length;
                string output = "";
                bool startreading = false;
                for (int i=0; i<length; i++)
                {
                   if (char.IsWhiteSpace(after[i]))
                   {
                       startreading = true;
                   }
                   if (startreading)
                   {
                       output+=after[i];
                   }
                }
             return Convert.ToInt32(output);
            }
     
            static bool isPrime(int value) /// określa czy dana liczba jest liczbą pierwszą.
            {
                bool isPrime = true;
                int sqrt = Convert.ToInt32(Math.Sqrt(value));
                for (int i = 2; i<=sqrt; i++)
                {
                    if ((value%i)==0)
                    {
                        isPrime = false;
                    }
                }
                return isPrime;
            }
     
            static void returnprime(int a, int b) /// przelatuje po całym przedziale i wywołuje        
                                                    /// sprawdzanie czy liczba jest pierwsza 
                                                   /// na każdym elemencie przedziału                                             
            {
    			if (a==1)
    			{
    				a=2;
    			}
     
    			for (; a<=b; a++)
    			{
    			   if (isPrime(a))
    			   {
    			       Console.WriteLine(a);
    			   }
    			}
        	   Console.WriteLine(Environment.NewLine);
            }
     
    	public static void Main()
    	{
    	    int amount = Convert.ToInt32(Console.ReadLine()); /// ilość przedziałów
     
            for (int i = 0; i<amount; i++)
            {
                string textvalues = Console.ReadLine();   
                int start_range = BeforeSpace(textvalues); /// zapisuje pierwszą liczbę przed spacją
                int end_range = AfterSpace(textvalues); /// zapisuje drugą liczbę po spacji
                returnprime(start_range,end_range); /// wyznaczam liczby pierwsze z tego przedziału
            }
    	}
    }

Wrzucam kod z przykładowym in/outputem http://ideone.com/8Lzlre

Więc, co mógłbym zmienić?

Twój algorytm ma złożoność kwadratową (dla każdej liczby n z przedziału a..b wywołujesz pętlę, która wykonuje się n razy), podczas gdy bez problemu można tu zejść do liniowej.

Oprócz tego możesz zastosować sztuczki w stylu inkrementacji co 2 zamiast co 1 w metodzie isPrime czy też nie wykorzystywać sita Eratostenesa, które samo w sobie nie grzeszy wydajnością.

W pętli lepiej iść od 3 z krokiem 4, i dzielić przez i oraz i+2.

A to AfterSpace i BeforeSpace lepiej zamienić na string.Split i int.Parse. Wynajdowanie koła na nowo to strata czasu.

Lekcja na dziś: sito eratostenesa -> https://github.com/p4-team/crypto-commons/blob/master/crypto_commons/generic.py#L68
Albo chociaż to jakoś tablicuj jeśli sito za trudne. Bo teraz jak ci podam na wejściu milion identycznych przedziałów to ty i tak będziesz wesoło wszystko liczył milion razy...

Nie ma tu raczej innego wyjścia niż Sito Eratostenesa. Dodatkowo sumy prefiksowe o, których nikt tu nie wspomniał, a są przecież niezbędne.
Co do optymalizacji sita eratostenesa - mozna je nieźle tuningować, ale w pewnym momencie zaczyna się to robić trudne.