一般筛法 O(nlnn)

import java.util.Scanner;

public class Main { 
    static int N=(int)(1.6e7);
    static int K=(int)(1e6+10);
    static int[] cnt=new int[N];
    static int[] num=new int[K];
    static int count=0;
    public static void main(String[] args) {
        Scanner cin=new Scanner(System.in);
        int n=cin.nextInt();
        int k=cin.nextInt();
        if(n>=N) {
            System.out.println(2);
            return;
        }else {
            for(int i=2;i<=n;i++) {
                cnt[i]+=2;
                for(int j=2*i;j<=n;j+=i) {
                    cnt[j]++;
                }
            }
            for(int i=2;i<=n;i++) {
                num[cnt[i]]++;
            }
            for(int i=2;i<K;i++) {
                while(num[i]-->0) {
                    count++;
                }
                if(count>=k) { 
                    System.out.println(i);
                    return ;
                }
            }
        }
    }
}

线性筛法 O(n)

public class Main {
    static int N = (int) (1.6e7 + 10);
    static int K = (int) 1e5;
    static int[] primes = new int[N];
    static boolean[] st = new boolean[N];
    static int[] cnt;// 记录约数个数
    static int[] times;// 记录最小质因子个数
    static int[] nums = new int[K];;
    static int num1;
    static int idx = 0;

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        int k = cin.nextInt();
        if (n > N) {
            System.out.println(2);
            return;
        } else {
            cnt = new int[N];
            times = new int[N];
            for (int i = 2; i <= n; i++) {
                if (!st[i]) {
                    primes[idx++] = i;
                    cnt[i] = 2;
                    times[i] = 1;
                }
                for (int j = 0; primes[j] <= n / i; j++) {
                    st[primes[j] * i] = true;
                    if (i % primes[j] == 0) {
                        times[primes[j] * i] = times[i] + 1;
                        cnt[i * primes[j]] = cnt[i] / (times[i] + 1) * (times[i * primes[j]] + 1);
                        break;
                    }
                    times[primes[j] * i] = 1;
                    cnt[i * primes[j]] = cnt[i] * 2;// cnt[i*primes[j]]=cnt[i]*(times[primes[j]*i]+1);
                }
            }
            /*
             * Arrays.sort(cnt,2,n+1); System.out.println(cnt[k+1]);
             */
            for (int i = 2; i <= n; i++) {
                nums[cnt[i]]++;
            }
            for (int i = 2; i <= n; i++) {
                while (nums[i]-- > 0) {
                    num1++;
                }
                if (num1 >= k) {
                    System.out.println(i);
                    break;
                }
            }
        }
    }
}