ECNU 1006 Prime

ECNU 1006 Prime

链接

https://acm.ecnu.edu.cn/problem/1006

题目

单点时限: 2.0 sec

内存限制: 256 MB

A prime is the number which can be only divide exactly by or itself.

输入格式
There several test case. Each test case have two positive integer in one line.

输出格式
For each test case, output one line that contain an integer that is the number of primes from to .

样例
input
5 10
1 3
6 8
output
2
2
1

思路

输入nm，求二者之间的素数，这里要考虑到边界值。
直接素数筛一下，把最大范围内的非素数标记为1，之后统计区间内0的数目。

代码

   public static void prime(int a[], int max) {
    //不是素数标记为1
    a[0] = 1;
    a[1] = 1;
    for (int i = 2; i * i <= max; i++) {
      if (a[i] == 0) {
        for (int j = i * i; j <= max; j += i) {
          a[j] = 1;
        }
      }
    }
  }

  public static void fun() {
    int max = 1000010;
    int[] a = new int[max+1];
    prime(a, max);
    Scanner sc = new Scanner(System.in);
    while (sc.hasNextInt()) {
      int n = sc.nextInt();
      int m = sc.nextInt();
      int count = 0;
      for (int i = n; i <= m; i++) {
        if (a[i] != 1) {
          count++;
        }
      }
      System.out.println(count);
    }
  }