fork download
copy 
  1. import java.io.*;
  2. import java.util.*;;
  3.  
  4. class C {
  5. 	int n, m;
  6. 	int MAXN = 10000000;
  7. 	boolean[] isPrime;
  8. 	//ArrayList<Integer> primes;
  9. 	long[] f = new long[MAXN+1];
  10. 	int[] count = new int[MAXN+1];
  11.  
  12. 	void solve(){
  13. 		isPrime = new boolean[MAXN+1];
  14. 		Arrays.fill(isPrime, true);
  15. 		isPrime[0] = isPrime[1] = false;
  16. 		for(int i=2; i<isPrime.length; i++){
  17. 			if(isPrime[i]){
  18. 				f[i] += count[i];
  19. 				for(int j=i+i; j<isPrime.length; j+=i){
  20. 					isPrime[j] = false;
  21. 					if(count[j] > 0) f[i]+=count[j];
  22. 				}
  23. 			}
  24. 		}
  25. 		for (int i = 1; i < n; i++) System.out.println(count[i]);
  26. 		//primes = new ArrayList<Integer>();
  27. 		//for(int i=0; i<isPrime.length; i++) if(isPrime[i]) primes.add(i);
  28. 	}
  29.  
  30.  
  31. 	void run()throws IOException{
  32. 		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
  33. 		int n = Integer.parseInt(bf.readLine());
  34. 		StringTokenizer strtok = new StringTokenizer(bf.readLine(), " ");
  35. 		for(int i=0; i<n; i++){
  36. 			count[Integer.parseInt(strtok.nextToken())]++;
  37. 		}
  38.  
  39. 		solve();
  40. 		for(int i=1; i<f.length; i++) f[i]+=f[i-1];
  41. 		for (int i = 1; i < 25; i++) System.out.println(f[i]);
  42.  
  43. 		int m = Integer.parseInt(bf.readLine());
  44. 		while(m-->0){
  45. 			String[] toks = bf.readLine().trim().split("[ ]+");
  46. 			int l = Integer.parseInt(toks[0]);
  47. 			int r = Integer.parseInt(toks[1]);
  48.  
  49. 			l = Math.min(l, MAXN);
  50. 			r = Math.min(r, MAXN);
  51. 			System.out.println(f[r]-f[l-1]);
  52. 		}
  53.  
  54. 	}
  55.  
  56. 	public static void main(String[] args)throws IOException {
  57. 		new C().run();
  58. 	}
  59.  
  60. }
Success #stdin #stdout 1.21s 380416KB
comments (?)
stdin
copy 
6
5 5 7 10 14 15
3
2 11
3 12
4 4
stdout
copy 
0
2
3
3
7
7
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
7
0
https://ideone.com/z1xOsi
language:
Java (12.0.1)
created:
9 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!