NGM2  Another Game With Numbers
Little Chikoo likes to play with numbers. Often he plays the following game:
 He chooses a number N and a set of positive integers.
 He writes down all the numbers from 1 to N.
 He chooses the first number (say x) from the set and cancels out all the multiples of x from 1 to N, including x.
 He repeats step 3 for all the numbers from the set.
One day Little Chikoo was in a mood to play pranks. So his brother asked him to play the game with a certain challenge. He made the game a little harder and asked him to find out the number of integers which aren't cancelled after he completes step 4. If he does that then Little Chikoo gets to play on his brother's Nintendo for one full day. Now Little Chikoo is in a hurry and wants to finish the job as soon as possible. He has asked for your help.
Input
The first line of the input contains N and K. (N <= 10^9, K <= 15)
Then K numbers follow all in a single line. All numbers are <= 100.
Output
The output file must contain the number of integers thatÂ aren't cancelledÂ after he finishes step 4 of the game.
Example
Input: 10 3 2 4 5 Output: 4
(The numbers 1, 3, 7 and 9 weren't cancelled).
hide comments
anirudnits:
20181225 14:12:40
use long long int to clear the last test case! 

Rahul Jain:
20180719 15:36:29
Nintendo... no wonder question is from 2010 :D


abhi_upadhyay:
20171228 13:25:38
use long long int, otherwise last test case will give wrong answer. 

prodipdatta7:
20170727 09:52:40
WA on test case 25!!!anyone help plz??


holmesherlock:
20170326 16:35:45
tle at test case 25:(


rishab_arora89:
20170221 21:04:57
Very Easy problem !! Just do Inclusionexclusion !! :) 

ganeshjadhav:
20161227 06:55:18
read about bitmasking on codeforces


hacker_sk:
20161002 12:10:58
lol, due to int .. i got 2 wrong ans in 25th(last) test case. finally AC. :) 

karan_batra:
20160913 10:06:17
AC in one go :D 

Bhumit:
20160905 10:53:40
@Paranoid Android

Added by:  Paranoid Android 
Date:  20100309 
Time limit:  0.247s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS OBJC PERL6 VB.NET 
Resource:   