Prime Numbers Problem-2

How to solve this Problem ? Any solution in C++ will be more helpful . Thanks in advance

Take time and try to solve it on your own, if you don’t get it have a look at the editorial. The problems you are asking are from medium level, so it’ll take some time to solve them. Don’t just ask questions without trying them.

First have a look at the editorial:- Click Here

This should help.

Its another typical segmented sieve problem, with a bit of greedy.

Given the value for A and B, you first segment out prime and not prime numbers. For every number i , instead of marking/storing 1 for non-prime, you store the factor of that number at that position. Its preferable to use a vector, such that vec[i] is storing all the factors of that number \le {10}^{6} In case there is nothing stored in the factor list, or the multiplication of factors does not yield the original number, then you can claim that the leftover number is prime.

Eg, take case of 38.

We store only {2} in vector. After diving by 2, 19 is left. My claim is, since we stored all factors \le \sqrt{N}, and there is no more factor except 2 in vector, and that since ProductOfFactors!=38, \implies 19 is leftover-and this leftover is prime itself.

Now whats left is just finding a way to maximize result from the factors- the editorial has given 2 beautiful proofs that how greedy works here and how to apply it. I hope this addressed the issue here.

Well, I would have recommended tester’s code, but idk that link suddenly broke. I will get it fixed asap though.

1 Like

Question:- PRIME1

Solution-1 by @vijju123

Solution-2 by @harrypotter0

Both are exactly same!!! @harrypotter0 You asked this question in the morning and you just copied it from @vijju123 and submitted it. Don’t post questions if you’re going to copy anyway from other users. If you don’t get it, try it after few days then you have a chance of getting it. This is not good bro. Please don’t repeat it again.

Already invested 3-4 hours on the problem …

Watched that but still stuck

Actually I didn’t copied . Please check I got it accepted before testing his solution :0

Testing my solution? :confused:

Testing :: By removing else condition , it fails for larger inputs so I came to know that without modification one can’t pass all test cases .

Oh XDXD. Experimenting is always good :slight_smile: . But you need a legible code for that :stuck_out_tongue: