【洛谷】P1835 - 素数密度

// 方法1：超时，超内存
import java.util.Scanner;

// 值正常，但是超时，超内存
public class P1835_SuShuMiDu_M2 {

    static int L ;
    static int R ;
    static int ans ;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        L = sc.nextInt();
        R = sc.nextInt();
        
        ans = 0 ;
        
        if(L == 2) {
            ans += 2;
            L = L+3 ;
        }else if(L == 3) {
            ans += 1;
            L = L+1 ;
        }else if(L%2 == 0) {
            L += 1;
        }
        
        for (int i = L; i <= R; i += 2) {
            boolean ok = false ;
            for (int j = 2; j <= Math.sqrt(i); j++) {
                if (i%j != 0 ) {
                    ok = true; // 说明该数是质数
                }else if (i%j == 0 ) {
                    ok = false;
                    break;
                }
            }
            
            if (ok) {
                ans += 1;
            }
        }
        
        System.out.println(ans);
        
        sc.close();
        
    }
}

// 方法2：
import java.util.Scanner;

public class P1835_SuShuMiDu_M1 {
    
    static int L ;
    static int R ;
    static int ans ;
    static int cnt ;
    static boolean[] arr ;
    static int p[];
    static boolean v[] = new boolean[1000007];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        L = sc.nextInt();
        R = sc.nextInt();
        
        arr = new boolean[50001];
        p = new int[5001];
        v = new boolean[1000007];
        
        ans = 0 ;
        cnt = 0 ;
        
        System.out.println(getSum(L,R));
        sc.close();
    }
    
    public static int getSum(int l, int r) {
        int n = (int) Math.min(50000, Math.sqrt(r));
        for(int i = 2; i <= n; i++) {
            if (!arr[i])p[++cnt] = i;
            
            for(int j = 1; j <= cnt && i * p[j] <= n; j++) {
                arr[i * p[j]] = true;
                if (i % p[j] == 0)
                    break;
            }
        }
        
        for(int i = 1; i <= cnt; i++) {
            int x = r / p[i] * p[i];
            while(x > p[i] && x >= l) {
                v[x - l] = true;
                x -= p[i];
            }
        }
        
        int res = 0;
        for(int i = 0; i <= r - l; i++) {
            if (!v[i])
                ++res;
        }
        return res;
    }
}