Блог пользователя vbansal027

Conceptual Doubt
Автор vbansal027, история, 8 лет назад, По-английски

Can somebody please explain, why in the following question,
http://codeforces.net/problemset/problem/576/A are we checking with all the powers of a prime whether the given number is divisible or not? why don't we stop, for a prime factor, as soon as we find its first power that is either greater than n or doesn't divide it completely ?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

we are printing all prime powers that are less then or equal to N, we dont stop if the prime powers does not divide N completely, but we do stop if the prime powers are greater then N,

for example: if N is 25, and vasya's number is 24

if we stop if a given prime power does not divide n completely, when checking powers of 2, we would stop immedietly (because 2 does not divide 25), and it would be impossible to determine the number

→ Ответить