Faster Prime Generation C#

Question

I know there are many questions already asked on SO regarding the same topic but this one might be different. I have studied some algorithms for calculating primes from 2 to N. I have written the following algorithm to calculate primes within a range, say from N to M where M can be as large as 10^10 and difference between N and M can be 10^6.

for (k = 0; k < t; k++)
{
    int[] indexOfPrimes = new int[m[k] - n[k] + 1];

    int index_1=2;
    int index_2=0;
    int counter = 0;

    for (index_1 = 2; index_1 < Math.Sqrt(m[k]);  index_1++)
    {
        counter = 0;
        for (index_2 = index_1*index_1; index_2 <= m[k];)
        {
            if (index_2 >= n[k] && index_2 <= m[k])
                indexOfPrimes[index_2 % (m[k] - n[k] + 1)] = 1;
            index_2 = (index_1 * index_1) + (index_1 * ++counter);
        }
    }

    for (i = n[k]; i <= m[k]; i++)
    {
        if (i == 1)
            continue;
        if (indexOfPrimes[i % (m[k] - n[k] + 1)] != 1)
            Console.WriteLine(i);
    }
    Console.WriteLine("\n");
}

Here the loop with variable k is for processing t test cases. The algorithm takes lot of time to process largest range (i.e. 100000) when the m[k]>10^7.

Is there a way not to calculate from 2, but directly from within the specified range?

Is there a way I can make is faster?

Edit: Could somebody please provide me a random big enough input to test my algorithm. It always gives Time Limit Exceeded, however, it runs just within 2.5 seconds on my laptop.

Edit: I reduced it to 1.5 seconds at maximum inputs. Gives me wrong answer. Don't understand why.

Answer 1

The smallest multiple of prime p greater than the bound lo is floor(lo/p)*p+p. You could use that for your starting point instead of starting from p.