java - 如果它有强大的测试用例,这个问题的解决方案是什么?
问题描述
https://www.codechef.com/problems/PRIME1
如果您不想打开链接,请在此处对以下问题进行简短描述:
这个问题要求我们打印给定范围内的所有素数。有 10 个测试用例,每个测试用例都会为我们提供一个范围的开始值和结束值。此范围的开始和结束可以采用 1 到 10^9 之间的值。开始值和结束值之间的差异为 10^5 或更小。问题的时间限制为 2 秒。(也就是说,对于所有 10 个测试用例一起)
我对此的思考:
一个常见的估计是 Codechef 使用的在线判断可以在 1 秒内执行 ~10^7 次操作。我们有 10 个测试用例,在最坏的情况下,每个测试用例的范围为 10^5(因为这是给定的最大范围)。现在, 10*(10^5)= 10^6 ,这是我们在 1 秒内可以执行的最大操作数,因此对于范围内的每个数字,我们必须确定它是否是 O(1) 中的素数。
Approaches:
1. Simple method for testing primality - Iterate through all numbers from 2 to n-1 and for every number check if it divides n
Ans: Won't work because for the worst case,
= (numbers of the highest size) * (total numbers in max range) * (total test cases)
= (10^9 * 10^5) * 10
= 10^15
2. Square root method to check if prime
Ans: Won't work because, in the worst case,
= (calculating sq. root of numbers of size 10^9) * (total numbers in max range) * (total test cases)
= (~10^4) * (10^5) * 10
= 10^10
3. Using Sieve of Eratosthenes
Precompute primes from 1 to 32000 (this number because it is approx the sq. root of 10^9)
Then to check of a value within the range is primeor not-
if value is between 1 and 32000
directly refer the precomputed value
else
try dividing that value by all precomputed primes, if it divides evenly then its not a prime
Ans: won't work because, in the worst case,
= (number of primes between 1 and 32000) *(total numbers in max range) * (total test cases)
= (3234) * (10^5) * (10)
= 10^9
方法3的代码:
import java.util.*;
import java.io.*;
class Main
{
static ArrayList<Integer> sieve(ArrayList<Integer> primes)
{
int[] prime=new int[32001];
for(int i=2; i<32001; i++)
{
if(prime[i]==0)
{
for(int j=i+i; j<32001; j+=i)
{
prime[j]=1;
}
}
}
for(int i=2; i<32001; i++)
{
if(prime[i]==0)
{
primes.add(i);
}
}
return primes;
}
public static void main(String[] args)
{
int t,m,n,flag;
ArrayList<Integer> primes= new ArrayList<Integer>();
FastReader scanner= new FastReader();
t=scanner.nextInt();
primes= sieve(primes);
while(t-- > 0)
{
m=scanner.nextInt();
n=scanner.nextInt();
for(int i=m; i<=n; i++)
{
if(i < 32001)
{
if(primes.contains(i))
{
System.out.println(i);
}
}
else
{
flag=0;
for(int j=0; j<primes.size(); j++)
{
if(i%primes.get(j) == 0)
{
flag=1;
break;
}
}
if(flag==0)
{
System.out.println(i);
}
}
}
System.out.println();
}
}
}
虽然方法 1 显然不起作用,但方法 2 和 3 却出人意料地通过了!我猜它通过了,因为该问题的测试用例很弱。一个强大的测试用例将类似于:
10
999900000 1000000000
999899999 999999999
999899998 999999998
999899997 999999997
999899996 999999996
999899995 999999995
999899994 999999994
999899993 999999993
999899992 999999992
999899991 999999991
我为这个测试用例运行了方法 3,计算时间总是超过 2 秒。如果这个问题确实有强大的测试用例,那么在给定的约束条件下解决它的正确方法是什么?
解决方案
如果您要尝试找出某个范围内的素数,请使用 Eratosthene 算法的筛法。Sieve 的基本前提是,给定一个数字范围,您可以消除所有与质因数有关的数字(即,一旦我们确定 2 是质数,我们就消除它的所有倍数 ...4、6、8 等)
一个实现如下:
private void printPrimes(int max) {
int [] prime = new int[max + 1];
for (int i = 1; i <= max; i++) {
prime[i] = i; // Assume everything is prime initially
}
// if number is prime, then multiples of that factor are not prime
for (int f = 2; f * f <= max; f++) {
if (prime[f] != 0) {
for (int j = f; f * j <= max; j++) {
prime[f * j] = 0;
}
}
}
int counter = 0;
for (int i = 1; i <= max; i++) {
if (prime[i] != 0) counter++;
}
prime = Arrays.stream(prime).filter(i -> i != 0).toArray();
System.out.println("There are " + counter + " primes between 1 and " + max);
System.out.println(Arrays.toString(prime));
}
推荐阅读
- android - 从辅助进程启动时,夜间模式值并不总是正确地考虑活动
- r - 如何将R中的控制台保存到文件中?
- clingo - 答案集编程初学者
- azure - 在说 Quorum 上部署的私有区块链网络中开采的第一个块的块号是多少?
- php - 如果在mysql表中使用num_rows,面向对象的过程找到空字符串,如何显示消息?
- php - 如何从 json_encode 数组响应中获取元素 - Codeigniter
- html - 如何使用角材料保留选项卡状态?
- docker - Ocelot 找不到重新路由文件
- django - Django Model validation based on a field value of another Model
- yaml - OpenAPI:覆盖引用,引用单个字段