flash_7's blog

Struggling with a number theory problem
By flash_7, history, 11 years ago, In English

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?

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
11 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
11 years ago, hide # |
← Rev. 2  
Vote: I like it +1 Vote: I do not like it

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.

→ Reply
»
11 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

can you post the link of this problem?

→ Reply
»
11 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
11 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply