You are not logged in. Please login at 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

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.


answered 08 Nov '17, 18:54

vijju123's gravatar image

5★vijju123 ♦♦
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


answered 08 Nov '17, 18:42

ramini's gravatar image

accept rate: 8%

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

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

answered 08 Nov '17, 18:42

siddharthp538's gravatar image

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.


answered 08 Nov '17, 18:57

ramini's gravatar image

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 ♦♦5★

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 ♦♦5★
toggle preview

Follow this question

By Email:

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



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "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:


question asked: 08 Nov '17, 18:35

question was seen: 270 times

last updated: 08 Nov '17, 20:08