fork download 
  1. import java.util.*;
  2.  
  3. class A {
  4. 	static final boolean[] composite = new boolean[123457 * 2];
  5. 	static final int[] cnt = new int[123457 * 2];
  6.  
  7. 	static {
  8. 		for (int i = 2; i * i < composite.length; i++)
  9. 			if (!composite[i]) {
  10. 				for (int j = i * i; j < composite.length; j += i)
  11. 					composite[j] = true;
  12. 			}
  13. 		for (int i = 2; i < cnt.length; i++)
  14. 			if (composite[i])
  15. 				cnt[i] = cnt[i - 1];
  16. 			else
  17. 				cnt[i] = cnt[i - 1] + 1;
  18. 	}
  19.  
  20. 	public void run() {
  21. 		Scanner sc = new Scanner(System.in);
  22. 		for (int n = sc.nextInt(); n > 0; n = sc.nextInt()) {
  23. 			System.out.println(cnt[2 * n] - cnt[n]);
  24. 		}
  25. 	}
  26.  
  27. 	public static void main(String[] args) throws Exception {
  28. 		new A().run();
  29. 	}
  30. }
Success #stdin #stdout 0.11s 213888KB
comments (?)
stdin 
1
10
13
100
1000
10000
100000
0
stdout 
1
4
3
21
135
1033
8392
https://ideone.com/KzLVK
language:
Java (HotSpot 12)
created:
13 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!