Efficient algorithm to get primes in large numbers.

Question

Hi all , I'm a beginner in C#, I'm trying to write an application to get Primes between two numbers entered by the user .. The Problem is at larg no. like 1 to 10000000 getting the primes takes long time and according to the problem i'm solving, the whole operation must be carried out in a small time interval , this is the problem link for more explanation .. SPOJ-Prime

and here's the part of my code that's responsible of getting primes..

  public void GetPrime()
    {            
        int L1 = int.Parse(Limits[0]);
        int L2 = int.Parse(Limits[1]);

        if (L1 == 1)
        {
            L1++;
        }

        for (int i = L1; i <= L2; i++)
        {
            for (int k = L1; k <= L2; k++)
            {
                if (i == k)
                {
                    continue;
                }
                else if (i % k == 0)
                {
                    flag = false;
                    break;
                }
                else
                {
                    flag = true;
                }
            }

            if (flag)
            {
                Console.WriteLine(i);
            }
        }
    }

Is there any faster algorithm ? Thanks in advance .

Answer 1

You are doing a lot of extra divisions that are not needed - if you know a number is not divisible by 3, there is no point in checking if it is divisible by 9, 27, etc. You should try to divide only by the potential prime factors of the number. Cache the set of primes you are generating and only check division by the previous primes. Note that you do need to generate the initial set of primes below L1.

Remember that no number will have a prime factor that's greater than its own square root, so you can stop your divisions at that point. For instance, you can stop checking potential factors of the number 29 after 5.

You also do can increment by 2 so you can disregard checking if an even number is prime altogether (special casing the number 2, of course.)

I used to ask this question during interviews - as a test I compared an implementation similar to yours with the algorithm I described. With the optimized algorithm, I could generate hundreds of thousands of primes very fast - I never bothered waiting around for the slow, straightforward implementation.

Answer 2

You could try the Sieve of Eratosthenes. The basic difference would be that you start at L1 instead of starting at 2.

Answer 3

There are many algorithms finding prime numbers. Some are faster, others are easier.

You can start by making some easiest optimizations. For example,

• why are you searching if every number is prime? In other words, are you sure that, given a range of 411 to 418, there is a need to search if numbers 412, 414, 416 and 418 are prime? Numbers which divide by 2 and 3 can be skipped with very simple code modifications.

• if the number is not 5, but ends by a digit '5' (1405, 335), it is not prime bad idea: it will make the search slower.

• what about caching the results? You can then divide by primes rather by every number. Moreover, only primes less than square root of the number you search are concerned.

If you need something really fast and optimized, taking an existing algorithm instead of reinventing the wheel can be an alternative. You can also try to find some scientific papers explaining how to do it fast, but it can be difficult to understand and to translate to code.

Answer 4

I remember solving the problem like this:

1. Use the sieve of eratosthenes to generate all primes below sqrt(1000000000) = ~32 000 in an array primes.
2. For each number x between m and n only test if it's prime by testing for divisibility against numbers <= sqrt(x) from the array primes. So for x = 29 you will only test if it's divisibile by 2, 3 and 5.

There's no point in checking for divisibility against non-primes, since if x divisible by non-prime y, then there exists a prime p < y such that x divisible by p, since we can write y as a product of primes. For example, 12 is divisible by 6, but 6 = 2 * 3, which means that 12 is also divisible by 2 or 3. By generating all the needed primes in advance (there are very few in this case), you significantly reduce the time needed for the actual primality testing.

This will get accepted and doesn't require any optimization or modification to the sieve, and it's a pretty clean implementation.

You can do it faster by generalising the sieve to generate primes in an interval [left, right], not [2, right] like it's usually presented in tutorials and textbooks. This can get pretty ugly however, and it's not needed.

Answer 5

Let's change the question a bit: How quickly can you generate the primes between m and n and simply write them to memory? (Or, possibly, to a RAM disk.) On the other hand, remember the range of parameters as described on the problem page: m and n can be as high as a billion, while n-m is at most a million.

IVlad and Brian most of a competitive solution, even if it is true that a slower solution could be good enough. First generate or even precompute the prime numbers less than sqrt(billion); there aren't very many of them. Then do a truncated Sieve of Eratosthenes: Make an array of length n-m+1 to keep track of the status of every number in the range [m,n], with initially every such number marked as prime (1). Then for each precomputed prime p, do a loop that looks like this:

for(k=ceil(m/p)*p; k <= n; k += p) status[k-m] = 0;

This loop marks all of the numbers in the range m <= x <= n as composite (0) if they are multiple of p. If this is what IVlad meant by "pretty ugly", I don't agree; I don't think that it's so bad.

In fact, almost 40% of this work is just for the primes 2, 3, and 5. There is a trick to combine the sieve for a few primes with initialization of the status array. Namely, the pattern of divisibility by 2, 3, and 5 repeats mod 30. Instead of initializing the array to all 1s, you can initialize it to a repeating pattern of 010000010001010001010001000001. If you want to be even more cutting edge, you can advance k by 30*p instead of by p, and only mark off the multiples in the same pattern.

After this, realistic performance gains would involve steps like using a bit vector rather than a char array to keep the sieve data in on-chip cache. And initializing the bit vector word by word rather than bit by bit. This does get messy, and also hypothetical since you can get to the point of generating primes faster than you can use them. The basic sieve is already very fast and not very complicated.

Answer 6

One thing no one's mentioned is that it's rather quick to test a single number for primality. Thus, if the range involved is small but the numbers are large (ex. generate all primes between 1,000,000,000 and 1,000,100,000), it would be faster to just check every number for primality individually.