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
kejriwal:
20160201 17:05:54
AC in one go :) !!!


GAURAV CHANDEL:
20160120 16:51:34
Nice problem... 

darkhire21:
20150906 18:38:32
TLE in 25th test case


Kriti Joshi:
20150203 20:30:13
Last edit: 20150207 09:44:05 

Dhawal Harkawat:
20150107 08:07:46
Last edit: 20150107 10:54:59 

Dhawal Harkawat:
20150107 07:59:22
Last edit: 20150107 10:55:10 

sancha:
20150107 06:46:18
g++ 4.3.2 gives this error "Language available only on Cube Cluster" 

ayushi agarwal:
20141118 12:17:26
got the problem i was using int instead of long long 

ayushi agarwal:
20141118 11:58:18
wrong answer on run 25. can anyone tell why? 

Praneeth Reddy:
20140905 13:19:32
getting WA at 25....what is happening??? 
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 PERL 6 VB.net 
Resource:   