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 (寒光博客)”原创,转载请保留文章出处。
本文地址:https://dxoca.cn/pat/262.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。