//#include <stdio.h>
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
#define PI 3.14159265359;

class Hoge{
  public:
					int i0;
					int i1,N0;
	int imax,imin,N1,iratio;
					int *iarray0,*iarray1;
					Hoge(int);
					void func0();
	bool* barray0;
	~Hoge();
  private:
	
	void inputarray(int*,int);
	void inputarray2(int*,int*,int);
	void printarray(int*,int);
	void printarrayb(bool*,int);
	void count0();
	void makelist0();
	void makelist1();
	void checkdouble();	//no dupicate
	void checkdouble1();	
	void count1();
	


};


Hoge::Hoge(int itemp){
	
	i0=itemp;
	//cout<<"i0="<<i0<<endl;
	
									}

void Hoge::func0(){
	//cout<<"N0?"<<endl;
	cin>>N0;
	iarray0=new int[N0];
	iarray1=new int[N0];


	inputarray(iarray0,N0);

	sort(iarray0,iarray0+N0,greater<int>());		//sort
	sort(iarray1,iarray1+N0,greater<int>());
	makelist0();
	//printarray(iarray0,N0);
	checkdouble();//no duplicate , iarray1
	//printarray(iarray1,N0);
	//cout<<"nownow"<<endl;
	//checkdouble1();	//??

	makelist1();
	
	count0();
	
	count1();
	//printarrayb(barray0,N1+1);
	
	//checkdouble1();
	//count0();
	
	//count00();
	
}

void Hoge::makelist0(){
	
	imax=iarray0[0];
	imin=iarray0[N0-1];
	//cout<<"imin"<<imin<<endl;
	iratio=imax/imin+1;
	//N1=imax-imin+1;
	N1=imax;
	//printarray(iarray0,N0);
	
	
	//cout<<"N1="<<N1<<endl;
	barray0=new bool[imax+1];
	
	
	for(int ic0=0;ic0<imax+1;ic0++){ //for 1
		
		barray0[ic0]=0;
		//cout<<"barray0["<<ic0<<"]="<<barray0[ic0]<<endl;
		
	}//end for1
	/*
	for(int ic0=0;ic0<imin;ic0++){ //for 2
		cout<<"hoge"<<endl;
		cout<<ic0<<endl;
		barray0[ic0]=0;
	}//end for 2
	*/
	
}//end func

void Hoge::makelist1(){
	//int icount00=0;
	barray0[0]=0;
	//cout<<"makelist1now"<<endl;
	
	for(int i0=0;i0<N0;i0++){
		//	cout<<"i0="<<i0<<endl;
		if(iarray1[i0]==0){}//do nothing
		else {barray0[iarray1[i0]]=1;}
		
	}
	//cout<<barray0[0]<<endl;
	//printarrayb(barray0,N1+1);
}

void Hoge::checkdouble1(){
	for(int i0=0;i0<N0-1;i0++){
		if(iarray0[i0]==iarray0[i0+1])
		{
			iarray0[i0]=0;
		}
		
	}
	//printarray(iarray0,N0);
}

void Hoge::checkdouble(){
	//int i0=0;
	int itemp=iarray1[0];
	for(int i0=0;i0<N0-1;i0++){
		
	if(iarray1[i0+1]==itemp)
	{
		//cout<<"i0="<<i0<<endl;
			iarray1[i0]=0;
			iarray1[i0+1]=0;
		}
		else {	itemp=iarray1[i0+1];}
		
	}//end for
	//printarray(iarray1,N0);
}
void Hoge::count0(){
	//printarray(iarray0,N0);
	int ihalf=N0/2-1;
	//cout<<"ihalf="<<ihalf<<endl;
	//cout<<"imax="<<imax<<endl;
	for(int i0=N0-1;i0>-1;i0--){
		//cout<<"i0="<<i0<<endl;
		if(iarray0[i0]*2>imax){
			//cout<<"break"<<endl;
		break;}//end if(iarray1[i0]*2>imax)
		
		else if(iarray0[i0]==0){cout<<"0!!"<<endl;
			cout<<"iarray["<<i0<<"]="<<iarray0[i0]<<endl;
			
		}
		
		else {
			
			//cout<<"ihalf="<<ihalf<<endl;
			//cout<<iratio<<endl;
			for(int j0=2;j0<iratio;j0++){
				//cout<<"loopnow"<<endl;
				
		//	cout<<"iarray1[i0]*j0="<<iarray1[i0]*j0<<endl;
				if(iarray0[i0]*j0>imax){break;}
				
				else{
				barray0[iarray0[i0]*j0]=0;
						
						}//else 2
									
			}//end for 2
								
		}//else 
	//	printarrayb(barray0,N1+1);
	}	//for 1
	
	//cout<<"icount"<<icount<<endl;
	//printarray(iarray0,N0);

}// end of func

void Hoge::count1(){
	int icount=0;
	for(int i0=0;i0<N1+1;i0++){
		
		//cout<<(barray0[i0]==1)<<endl;
		icount+=(barray0[i0]==1);
		
	}
	cout<<icount<<endl;
	//cout<<"icount="<<icount<<endl;
}
void Hoge::inputarray(int* itemp,int itempn){
	
	int* iarray=itemp;
	int n0=itempn;
	for (int i0=0;i0<n0;i0++){
		//cout<<"i0="<<i0<<endl;
		cin>>iarray[i0];
		iarray1[i0]=iarray[i0];
	}
}

void Hoge::printarray(int* itemp,int itempn){
	
	int* iarray=itemp;
	int n0=itempn;
	for (int i0=0;i0<n0;i0++){
		cout<<"iarray["<<i0<<"]="<<iarray[i0]<<endl;
		
	}
	cout<<"--------------"<<endl;
}

void Hoge::printarrayb(bool* btemp,int itempn){
	
	bool* barray=btemp;
	int n0=itempn;
	for (int i0=0;i0<n0;i0++){
		cout<<"barray["<<i0<<"]="<<barray[i0]<<endl;
		
	}
	cout<<"--------------"<<endl;
}

	
Hoge::~Hoge(){
	
	delete [] iarray0;
	delete [] iarray1;
	delete [] barray0;
	
							}
int main(){
				int N=0;
				//cin>>N;
	Hoge* hoge=new Hoge(N);
	hoge->func0();
	
	
	return 0;
	delete hoge;
}//end of main

Measured memory_bytes: 6132