Efficient algorithm to get primes between two large numbers

c# algorithm primes

18,553

Solution 1

I remember solving the problem like this:

Use the sieve of eratosthenes to generate all primes below sqrt(1000000000) = ~32 000 in an array primes.
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. But if anyone is interested, see:

http://pastie.org/9199654 and this linked answer.

Solution 2

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.

Solution 3

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

Solution 4

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.

Solution 5

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.

View more solutions

18,553

Author by

rafael

Updated on June 03, 2022

Comments

rafael almost 2 years
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 large numbers (valid numbers are in the range from 1 to 1000000000) 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.
- György Andrasek almost 14 years
  
  Possible duplicate: stackoverflow.com/questions/453793/…
- IVlad almost 14 years
  
  It's not really the same. That question asks what the fastest is, this question asks what's fast enough to get accepted on SPOJ.
- Dykam almost 14 years
  
  Large is relative. For some reason I would call every prime that fits in a Int32 small.
Michael almost 14 years

One thing I like about this algorithm is you could potentially do it in parallel to leverage multiple cores - alas, I've never gotten around to actually trying it.
BlueRaja - Danny Pflughoeft almost 14 years

Uh, no, you'd still have to start at 2.
BlueRaja - Danny Pflughoeft almost 14 years

Converting the number to base-10 to check if the last digit is 5 is significantly slower than just checking num % 5 == 0...
Greg Kuperberg almost 14 years

I was going to make that point, until I realized that it isn't relevant for the parameters of the problem. Even for the example range that you give, the range is big enough that a sieve is faster. If you wanted all primes, say, between 1,000,000,000 and 1,000,001,000, then a partial sieve combined with Miller-Rabin would be the best approach.
DarthJDG almost 13 years

Any reason for not just returning isprime at the end?
Tranquocbinh333 almost 13 years

Yes it's true just return isprime is enough.
Christian Ammer over 11 years

With generalising the sieve, do you mean the segmented version of the sieve of Eratosthenes?
Niklas B. almost 10 years

"This can get pretty ugly however" Actually it's very easy, you just have two sieves, one for the range 2..sqrt(n) and one for m..n Example in C++: pastie.org/9199654 and you get a nice runtime of O((n-m) log log (n-m) + sqrt(n) * log log n). Segmented sieve is not a lot more complicated if you don't interleave the prime finding and sieving phase
Will Ness almost 10 years

downvote because of the dissing of the sieve of Eratosthenes. yes you do need it to find primes in a range between two big numbers, and no it isn't ugly. More here.
IVlad almost 10 years

@WillNess - I did not diss it at all. The OP did not seem to have a lot of experience implementing algorithms, so I suggested the easiest necessary to solve his problem. You try explaining things like j=(k-(above-i)%k)%k, or even Nikals B's much nicer j = std::max(2, (m + i - 1) / i) * i to a newbie. And no, it's not needed for this problem.
IVlad almost 10 years

I think you can definitely argue that it is not ugly and is worth mentioning in more detail in your opinion, but I don't think I made any factually wrong statements that would definitely deserve a downvote. You downvoted based on opinion, which I do not think is warranted. If you have a different opinion, you can contribute with another answer, a comment, or even edit my post with a link to more details about the method I suggested against (which I have now done).
Will Ness almost 10 years

@IVlad my wording might have been a bit off; you do say the core primes are to be calculated by the SoE... I assumed you do need SoE for wide ranges high up, like the "(1 <= m <= n <= 1000000000, n-m<=100000)" here.
Will Ness almost 10 years

@IVlad in fact there are so few primes below 32K that you probably could find them with a trial division too, without any noticeable slowdown. -- I tried it, you were right: TD C code was AC at 2.65 secs (my old SoE C code there was 0.07 secs).
IVlad almost 10 years

@WillNess - yes, there are very few and the sieve is not needed at all. It's good that you mentioned the segmented sieve for people who stumble upon this and are interested in it, but not needed for this problem. Thanks for removing the downvote.
Will Ness over 9 years

you should use addition, not multiplication, in your inner loop: [i*j]; j++ is the same as [j]; j+=i.
Arthas over 7 years

how about we use sieve two times? 1st one gets us array of primes and we use the second sieve as usual to strike off all the numbers which are divisible by it after determining if its a prime?
Alejandro Montilla over 6 years

Welcome to SO, please add some explanation of your solution, that will give you more chances to get up voted.
Sinaesthetic over 6 years

The execution time between 1M numbers and 10M numbers is pretty significant (like .5 seconds vs. 8 seconds). You could probably half your tested set by incrementing your loop by 2 instead of 1.