title: How to calculate the number of coprime subsets of the set {1,2,3,..,n}
body: <p>I am solving <a href="https://docs.google.com/file/d/0B2d37tm1YmE3QmdXazhnN2lRdDQ/edit" rel="noreferrer">this task (problem I)</a>. The statement is:</p>
  
  <p>How many subsets of the set <code>{1, 2, 3, ..., n}</code> are coprime? A set of integers is called coprime if every two of its elements are coprime. Two integers are coprime if their greatest common divisor equals 1.</p>
  
  <p>Input</p>
  
  <p>First line of input contains two integers <code>n</code> and <code>m</code> (<code>1 &lt;= n &lt;= 3000, 1 &lt;= m &lt;= 10^9 + 9</code>)</p>
  
  <p>Output</p>
  
  <p>Output the number of coprime subsets of <code>{1, 2, 3, ..., n}</code> modulo <code>m</code>.</p>
  
  <p>Example</p>
  
  <p>input: 4 7
  output: 5</p>
  
  <p>There are 12 coprime subsets of <code>{1,2,3,4}</code>: <code>{}</code>, <code>{1}</code>, <code>{2}</code>, <code>{3}</code>, <code>{4}</code>, <code>{1,2}</code>, <code>{1,3}</code>, <code>{1,4}</code>, <code>{2,3}</code>, <code>{3,4}</code>, <code>{1,2,3}</code>, <code>{1,3,4}</code>.</p>
  
  <hr>
  
  <p>I think it can be solved by using prime numbers. (keeping track of if we used each prime numbers) ..but I'm not sure.</p>
  
  <p>Can I get some hints to solve this task?</p>
  
  <ul>
  <li>You can found this sequence at here : <a href="http://oeis.org/A084422" rel="noreferrer">http://oeis.org/A084422</a></li>
  </ul>