寒光博客

[PAT]1013 数素数 20分
PAT (Basic Level)Practice 1013 数素数 https://pintia.cn/prob...
扫描右侧二维码阅读全文
23
2019/08

[PAT]1013 数素数 20分

PAT (Basic Level)Practice 1013 数素数
https://pintia.cn/problem-sets/994805260223102976/problems/994805309963354112

分析

求第几个到第几个的素数
我决定使用埃氏筛法
然后卡范围输出就好
这道题的细节问题是 行末不能有空格 要处理好

wa 最后2个测试

package PAT.BasicLevel;

import java.util.Scanner;

import static java.lang.Math.log;

public class _1013素数数 {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int m = cin.nextInt(), n = cin.nextInt();
        int range = 2;
        while (range / log(range) <= n) {//求出最大素数范围 素数定理
            range++;
        }
        int arr[] = new int[range];
        int x = 2;
        while (x < range) {
            if (arr[x] != 0) {
                x++;
                continue;
            }
            int k = 2;
            while (x * k < range) {
                arr[x * k] = -1;
                k++;
            }
            x++;
        }
        int sum = 0;//是总的个数计数
        int cnt = 0;//换行判断
        for (int i = 2; i < arr.length; i++) {
            if (arr[i] == 0) {
                sum++;
                if (sum >= m && sum <= n) {
                    cnt++;
                    if(sum==n){
                        System.out.print(i);
                    }
                    else if (cnt % 10 != 0 )
                        System.out.print(i + " ");
                    else
                        System.out.print(i + "\n");
                }
            }
        }
    }
}

换暴力打表 也是最后两个wa

package PAT.BasicLevel;

import java.util.Scanner;

import static java.lang.Math.log;

public class _1013素数数 {
    static boolean[] prime;

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int m = cin.nextInt(), n = cin.nextInt();
        getPrime(n);
        int i = 2;
        int cnt = 0;
        int sum=0;
        while (true) {
            if (cnt > n) break;
            if (prime[i]) {
                cnt++;
                if (cnt >= m && cnt <= n) {
                    sum++;
                    if (cnt == n) {//是最后一个素数 没有空格
                        System.out.print(i);
                    } else if (sum % 10 == 0) {//每10个 换行
                        System.out.print(i + "\n");
                    } else {
                        System.out.print(i + " ");
                    }
                }
            }
            i++;
        }

    }

    private static void getPrime(int n) {
        int range = 2;
        while (range / log(range) <= n) {//求出最大素数范围 素数定理
            range++;
        }
        prime = new boolean[range];
        for (int i = 2; i < range; i++) {
            boolean flag = true;
            for (int j = 2; j * j <= i; j++) {
                if (i % j == 0) {
                    flag = false;
                    break;
                }
            }
            if (flag)
                prime[i] = true;
        }
    }
}

暴力AC法 20分

到头来还是想不懂wa的两个点

import java.util.Scanner;

public class Main {
    static int cnt = 0;
    static int flag = 0;

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int m = cin.nextInt(), n = cin.nextInt();
        for (int i = 2; cnt <= n; i++) {
            getPrime(i, m, n);
        }
    }

    private static boolean getPrime(int i, int m, int n) {
        for (int j = 2; j * j <= i; j++) {
            if (i % j == 0) {
                return false;
            }
        }
        cnt++;
        if (cnt >= m && cnt <= n) {//在区间内 不加判n 会多输出一个
            flag++;
            if (flag % 10 == 0) {//十个换行
                System.out.print(i + "\n");
            } else if (cnt == n) {//最后一个特判断 盘 cnt
                System.out.print(i);
            } else {//正常情况
                System.out.print(i + " ");
            }

        }
        return true;
    }
    //2 3 4 5 6
}
本文作者:Author:     文章标题:[PAT]1013 数素数 20分
本文地址:https://dxoca.cn/pat/262.html       百度未收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:August 31st, 2019 at 07:32 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment