kratos99's blog

By kratos99, history, 4 weeks 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

»
4 weeks 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.

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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 )