[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分

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
}

百度未收录

Last modification：August 31st, 2019 at 07:32 pm