Counting prime numbers smaller than n.

Funfunfunfun's blog

By Funfunfunfun, history, 5 years ago, In English

The other day I met a problem that needed to count the number of primes less than n with n <= 1e10. But I only know how to use sieve to solve but it can only run with n <= 1e6. Can you help me find a better solution? thanks for help!

Funfunfunfun
5 years ago
16

Comments (10)

Show archived | Write comment?

_namikazE

5 years ago, hide # |

-24

use segmented sieve, you can easily find videos of it on youtube

→ Reply

Funfunfunfun

5 years ago, hide # ^ |

-8

Thank your idea.This is the good sieve but this can run with n<=1e8.I think another better way to solve this problem.

→ Reply

navneet.h

5 years ago, hide # ^ |

there exists approximate prime counting function, which gives very accurate result for small N

→ Reply

Lemur95

5 years ago, hide # |

-8

I had the same curiosity a while ago, so I wrote some code to find pi(n) (which is what you need) and prime(n) (n-th prime number). You can play with N and X constants to see which gives better times. Here is the code. I used Meissel–Lehmer algorithm. You can read here and here about it. If you don't understand, don't be shy and ask me! Happy new year! :D

→ Reply

Funfunfunfun

5 years ago, hide # ^ |

-8

I don’t understand how to calculate Pi(x,a). Can you explain it to me?

→ Reply

Lemur95

5 years ago, hide # ^ |

-8

In my code it's the function P(niv, n, a) which, I think, it's pretty clear how it works

→ Reply

Funfunfunfun

5 years ago, hide # ^ |

-8

I understood. Thanks you so much!

→ Reply

Funfunfunfun

5 years ago, hide # ^ |

-8

But can you explain me X in your code for what?

→ Reply

Lemur95

5 years ago, hide # ^ |

-8

Yes sure. X is max i so that we calculate Pi(n, a). Increasing X, lowers initial a, but it might cause P function to take much more time. After testing, I found that X should be 6 or 7.

→ Reply