kratos99's blog

Need Help
By kratos99, history, 5 years ago, In English

I need help to solve this problem.

Thanks in advance.

Happy Coding :)

  • Vote: I like it
  • +13
  • Vote: I do not like it

»
5 years ago, # |
← Rev. 5   Vote: I like it +6 Vote: I do not like it

1.Use Linear Sieve to take primes no more than $$$n$$$ out, store them.

Linear Sieve

2.Use upper_bound() to find the position of the smallest prime strictly greater than $$$n$$$. Then we can calculate $$$\pi(n)$$$ easily.

3.$$$\forall i: i\ge 0 $$$ and $$$ p_{A\times i+B} \le n$$$, store $$$p_{A\times i+B}$$$ for answer.

4.Output what you stored for answer.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did this and got AC but I think purpose of problem setter is behind this question is not this so I asked.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      There's a time constraint of $$$10$$$ seconds, with $$$1024$$$ MB memory avaliable.

      I think the purpose of the author could be that ( enumerate primes )

      → Reply