You are not logged in. Please login at www.codechef.com to post your questions!

×

Prime Numbers Problem-2

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

asked 08 Nov '17, 18:35

harrypotter0's gravatar image

4★harrypotter0
318110
accept rate: 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.

link

answered 08 Nov '17, 18:54

vijju123's gravatar image

4★vijju123 ♦♦
15.4k12065
accept rate: 18%

edited 08 Nov '17, 18:58

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

link

answered 08 Nov '17, 18:42

ramini's gravatar image

2★ramini
615
accept rate: 8%

Already invested 3-4 hours on the problem ....

(08 Nov '17, 19:06) harrypotter04★
link

answered 08 Nov '17, 18:42

siddharthp538's gravatar image

4★siddharthp538
2555
accept rate: 11%

Watched that but still stuck

(08 Nov '17, 19:07) harrypotter04★

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.

link

answered 08 Nov '17, 18:57

ramini's gravatar image

2★ramini
615
accept rate: 8%

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

(08 Nov '17, 19:08) harrypotter04★

Testing my solution? :/

(08 Nov '17, 19:49) vijju123 ♦♦4★

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) harrypotter04★

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

(08 Nov '17, 20:08) vijju123 ♦♦4★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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,344
×199

question asked: 08 Nov '17, 18:35

question was seen: 267 times

last updated: 08 Nov '17, 20:08