static int getNumberOfPrimes(int N) {
		if (N<2) return 0;
		List<Integer> p=new ArrayList<>(); p.add(2);
		for (int i=3;i<=N;i+=2) {
			boolean f=true;
			for (int j=0;j<p.size()&&f&&p.get(j)<=Math.sqrt(i);++j)
				f=i%p.get(j)!=0;
			if (f) p.add(i);
		}		
		return p.size();
	}