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

Struggling with a number theory problem
Автор flash_7, история, 9 лет назад, По-английски

Given two integers N and M, count the number of integers x between 2 and N! , having the property that all prime factors of x are greater than M. Where 1≤M≤N<10000001 and (N-M)≤100000. Can anyone help me with the logic?

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

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

Use "sieve of eratosthenes" and find prime numbers that is greater than M and smaller than N all the numbers we want is multiplication of these prime number.

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Well but i think it's not possible to find the prime numbers till N!.(N factorial)

    → Ответить
»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

I think you can calculate instead the count of numbers that have prime factors smaller than M in the range 2 to N! and substract it from N! - 1. Now let the primes smaller than M pe p1, ..., pk, then by simple inclusion, exclusion the quantitiy you want is equal to which is similar to euler's toitient function formula and you can write it as .

I hope this is correct.

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

can you post the link of this problem?

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

I think there's no way to solve this problem right now. Since U need to find all the prime numbered from M to N!. Let the count be X, our answer is 2^X -1.

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

Here is the problem link : https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2435

→ Ответить