0

I could use Sieve of Eratosthenes to count the number of prime numbers but it would require me to create an array so large that it couldn't be created. I'm just looking forward to find a way or algorithm to achieve the task. A name or reference would serve the purpose. I just need some way to proceed with the task. Having the method, i'll figure out the programming part. Help please.

Pranjal Katlana
  • 3
  • 4
  • Why hold all the primes? There are 3,204,941,750,802 primes less than 10^14 - you'd struggle to hold them all in memory (!) – Wai Ha Lee Feb 14 '15 at 17:00
  • I do not want to hold the primes, i just want to count the number of primes. – Pranjal Katlana Feb 14 '15 at 17:01
  • [This SO question](http://stackoverflow.com/q/28520359/1364007) asks about the [Sieve of Atkin](https://en.m.wikipedia.org/wiki/Sieve_of_Atkin), which is an optimised version of the Sieve of Eratosthenes. The question hasn't got an accepted answer, but it might be worth you taking a look. – Wai Ha Lee Feb 14 '15 at 21:59
  • 1
    @WaiHaLee, the Sieve of Atkin doesn't deserve the positive attention it gets: It would need to be page segmented for the range to 10^14 and it does very poorly and doesn't perform as per its theoretical time complexity for these ranges - even the reference "primegen" implementation by the authors doesn't do well to this range. A better way for the count of prime to 10^14 would be numerical analysis techniques. – GordonBGood May 28 '16 at 02:23
  • The 10^14 range suggested in this question is large enough so that even the best optimized page segmented Sieve of Eratosthenes [Kim Walisch's primesieve](http://primesieve.org/) takes about four hours to do it on a modern desktop CPU using multi-threading. For prime counting, an approach like [this SO algorithm](http://stackoverflow.com/a/19072704/549617) will do it in a few seconds and [Kim Walisch's extremely optimized version](https://github.com/kimwalisch/primecount) will do it even faster at a fraction of a second using an improved algorithm and multi-threading. – GordonBGood May 28 '16 at 02:51
  • You just want the *number* of primes? See https://stackoverflow.com/questions/19070911/feasible-implementation-of-a-prime-counting-function#answer-19072704 – Don Hatch Aug 18 '17 at 14:32

1 Answers1

0

I can't think of anything better than the Sieve of Eratosthenes for what you want, so here is what I'd do.

The Sieve of Eratosthenes only requires checking for prime divisors of a number up to the square root of that number, so you need not create an array for all the primes less than 10^14 - just the primes less than 10^7.

There are 664,579 primes less than 10^7 - even on a computer with a very modest spec, an array of that size should be fine (storing them as 4 byte integers, that'd be ~2MB).

Here's a pseudo-code method to do that:

  • Create storage for the primes less than 10^7 - let's call that the divisor storage.
  • Seed your storage with the first prime, 2.
  • Create a counter for the number of primes found, initialising it to one (for the prime 2).
  • Create a counter for the prime candidate, starting it at 3.
  • Divide the prime candidate by all the primes in the divisor storage. If any leave no remainder, it is prime, so add it to the divisor storage (unless it's larger than 10^7) and increment the primes found counter.
  • Increase the candidate counter by two.
  • Repeat the last two steps into the prime candidate exceeds 10^14.

You need not when keep hold of the divisor primes - you could just naively divide by every number less than the root of the candidate, but this will be about log(n) faster.

This is a very crude way of doing it, but it works.

Wai Ha Lee
  • 8,598
  • 83
  • 57
  • 92
  • If you used the naive method, you would need only a **tiny** amount of memory: chiefly to store (a) the candidate, (b) the divisor, (c) the remainder, (d) the count of primes found so far. – Wai Ha Lee Feb 14 '15 at 20:15
  • 1
    Its a nice method. :) But still i'll have to repeat the process for i=3 to i=10^14 at the steps of two. So in all i'll have to repeat it for 5x10^13 times which is a lot. I solved the problem using Segmented Sieve of Eratosthenes. Have a look http://discuss.codechef.com/questions/61937/help-related-to-primegenerator-problem – Pranjal Katlana Feb 15 '15 at 00:08