×

# Prime Numbers Problem-2

 0 How to solve this Problem ? Any solution in C++ will be more helpful . Thanks in advance asked 08 Nov '17, 18:35 318●1●10 accept rate: 1%

 1 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. answered 08 Nov '17, 18:54 15.4k●1●20●66 accept rate: 18%
 0 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 answered 08 Nov '17, 18:42 2★ramini 61●5 accept rate: 8% Already invested 3-4 hours on the problem .... (08 Nov '17, 19:06)
 0 https://www.youtube.com/watch?v=9kSxipsWu6M This should help. answered 08 Nov '17, 18:42 255●5 accept rate: 11% Watched that but still stuck (08 Nov '17, 19:07)
 0 Question:- PRIME1 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. answered 08 Nov '17, 18:57 2★ramini 61●5 accept rate: 8% Actually I didn't copied . Please check I got it accepted before testing his solution :0 (08 Nov '17, 19:08) Testing my solution? :/ (08 Nov '17, 19:49) 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 . (08 Nov '17, 19:58) Oh XDXD. Experimenting is always good :) . But you need a legible code for that :p (08 Nov '17, 20:08)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,356
×199

question asked: 08 Nov '17, 18:35

question was seen: 270 times

last updated: 08 Nov '17, 20:08