NGM2 - Another Game With Numbers


Little Chikoo likes to play with numbers. Often he plays the following game:

  1. He chooses a number N and a set of positive integers.
  2. He writes down all the numbers from 1 to N.
  3. He chooses the first number (say x) from the set and cancels out all the multiples of x from 1 to N, including x.
  4. 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
Anastasia: 2014-07-27 21:31:16

@paranoid,please help with tests since 23 number, long arifmetic,and why solve the problem this?(id77834807)

Last edit: 2014-07-27 21:34:10
aayush ojha: 2014-07-13 12:35:54

getting wrong answer on case-25.can someone provide a tricky test case please?

Vishal Gautam: 2013-09-18 05:36:36

can anyone give me tough test case.. i am running all test cases mentioned in forum and they are giving right answer with my logic yet i am getting WA

Last edit: 2013-09-18 05:39:02
abdelkarim: 2013-05-30 01:30:07

@vijay
output for 1 is 0 :-) .

Vijay Jain: 2013-04-28 07:42:04

what will be the output if one of the number in the set is 1 ??

[Lakshman]: 2013-02-01 11:56:32

after running 23 test cases I an Getting Run time error @Paranoid Android Please check my code or Give me the critical test cases..Please..Solution no.8634087
Please check code at...

got AC :) after 15 run time error and WA.
EDIT: [Link Deleted]

Last edit: 2013-02-14 12:43:08
Thomas: 2012-06-12 08:37:45

Does Someone knows the formula??

Gunjit : 2012-05-14 18:42:02

after running 23 test cases the judge says WA ... can any1 help me plz

accept: 2011-12-09 10:26:15

can anybody help me about runtime error (SIGSEGV)

sesume uchiha: 2011-07-31 07:51:36

@paranoid : can u help me with the test case for which my code is failing (id 5453378)

Last edit: 2011-07-31 08:28:10

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