的高分。算法优化-找合条件的素数

Question

     A prime number is a number that is divisible by only itself and one.
一个质数是只能被自己和1整除的数字 前提定义
 
In this problem we will say that a prime number p is x-isolated at distance (a,b)
我们说质数p 在区间(a,b)上被x分
 if there there are at most x primes (including p) between (p-a) and (p+b), inclusive. 
如果最多有x个质数（包括p）,在 (p-a) , (p+b) 之间 问题You are given the numbers a, b and x.
我们给定三个数字a , b ,x
 Your task is to find the smallest prime p between a+2 and 263-1-b, inclusive,
你的任务是找到最小的质数p,在a +2 和 2**63-1-b , 之间。
such that p is x-isolated at distance (a,b), 
质数p在区间(a,b)上被x分
and return a String which contains its decimal notation.
并且返回一个字符产，包括小数点 For example, for x=2 and a=b=5, the smallest possible value is 23, as the only primes in [18,28] are 19 and 23. 
例如，
X=2,a = b = 5,  最小的p值是23，因为在区间[ p-a,p+b] 之间，也就是[ 23-5,23+5] 之间的质数只有19和23，( 2 个质数) Examples
0)
     x = 2
a = 5
b = 51)
     x = 410
a = 5954
b = 1916
2)
     x = 400
a = 4067
b = 9810
3)
     x = 87
a = 922
b = 630
4)
     x = 76
a = 1127
b = 546
5)
     x = 312
a = 7649
b = 4383  
package topcoder;import java.math.*;
import java.util.Random;
import java.util.Date;public class IsolatedPrimes {

private int m_primeCount = 0;
private boolean m_isMinus1 = true;// c = k*6 -1 (+1)
private int m_count = 0;

public String findPrime(int x, int a, int b) 
{
String ret="";

m_primeCount = x + 2; // add a bottom , and a top

BigInteger primeArray[];

try
{
primeArray = getInitPrimeArray(); 

BigInteger[] p = new BigInteger[1];

BigInteger upperBound = BigInteger.valueOf(2).pow(63).subtract(BigInteger.valueOf(1)).subtract(BigInteger.valueOf(b));
boolean overBound = false;
int j = 0;

while( ( !isPrimeXBin(primeArray,   a, b, p) ) && ( !overBound) && j<5)
{
primeArray  =getNextPrimeArry(primeArray);
if(primeArray[m_primeCount-1].compareTo( upperBound) > 0)
{
overBound = true;
}
j++;
}

if (!overBound)
{
System.out.println("[findPrime.isPrimeX].p=" + p[0].toString());

for(int i = 0 ;i<primeArray.length;i++)
{
System.out.println("[findPrime].primeArry[" + i + "]   =" + primeArray[i].toString() );

}

return p[0].toString();
}

}
catch(Exception e)
{
System.out.println("[findPrime].error=" + e.getMessage()); 
}

System.out.println("[findPrime].end");

return ret;
}

void IsolatedPrimes()
{
 
m_isMinus1 = false ;
}

public BigInteger getNextPrime(BigInteger curPrime  )
{
BigInteger nextPrime = null;


if(curPrime.compareTo(BigInteger.valueOf(5))== 0)
{
nextPrime = BigInteger.valueOf(7);
m_isMinus1=true;
return nextPrime;
}

if(m_isMinus1)
{
nextPrime = curPrime.add(BigInteger.valueOf(4));
}
else
{
nextPrime = curPrime.add(BigInteger.valueOf(2));
}

m_isMinus1 = !m_isMinus1;

if (nextPrime.isProbablePrime(1))
{
return nextPrime;
}
else
{
return getNextPrime(nextPrime);  
}

}

private BigInteger getInitPrimeArray()[]
{
BigInteger primeArray[] = new BigInteger[m_primeCount];

if(m_primeCount<2)
{
throw new RuntimeException("Invalid prime count.");
}

primeArray[0]=BigInteger.valueOf(2);
primeArray[1]=BigInteger.valueOf(3);
m_isMinus1 = false;

if (m_primeCount >2)
{
primeArray[2]=BigInteger.valueOf(5);
m_isMinus1 = false;

for(int i=0;i<m_primeCount -3 ;i++)
{
primeArray[i +3] = getNextPrime(primeArray[i+2]  );  
}
}
return primeArray;
}

private BigInteger getNextPrimeArry(BigInteger curPrimeArry[])[]
{
for(int i = 0;i<m_primeCount-1 ;i++)
{
curPrimeArry[i]=curPrimeArry[i+1];
}

curPrimeArry[m_primeCount -1]= getNextPrime(curPrimeArry[m_primeCount -2]  );

if(m_count%100 == 0)
{
System.out.println("[getNextPrimeArry].m_count=" + m_count + "     curPrimeArry[m_primeCount -1]=" + curPrimeArry[m_primeCount -1]);
}
m_count++;

return curPrimeArry;
}
 
//Use binary search 
private boolean isPrimeXBin(BigInteger primeArray[] ,   int a , int b , BigInteger pArray[])
{
boolean isPrime = false;

int start = 1 ;
int end = primeArray.length-1;
int middle = (start + end)/2;

int count= 0 ;
 
BigInteger p = primeArray[middle];


System.out.println("[isPrimeXBin].p=" + p.toString());
System.out.println("[isPrimeXBin].(p-a,p+b)= (" + p.subtract(BigInteger.valueOf(a)).toString() + "," + p.add(BigInteger.valueOf(b)).toString() + ")");
 
System.out.println("[isPrimeXBin].Inner Bracket= (" + primeArray[1].toString() + "," + primeArray[primeArray.length -2].toString()+ ")");
System.out.println("[isPrimeXBin].Outer Bracket= (" +primeArray[0].toString() + "," +  primeArray[primeArray.length -1].toString() + ")");

boolean overBound = false;

while(
! ( p.subtract(BigInteger.valueOf(a)).compareTo( primeArray [0] ) > 0
&& p.subtract(BigInteger.valueOf(a)).compareTo( primeArray [1] ) <= 0
&& p.add(BigInteger.valueOf(b)).compareTo(primeArray[primeArray.length -2])  >=0
&& p.add(BigInteger.valueOf(b)).compareTo(primeArray[primeArray.length -1])  <0))
 {

//1.if p-a  ,  lbound , p+b , ubound , then move to right +
if( p.subtract(BigInteger.valueOf(a)).compareTo( primeArray [0] ) < 0 
&& p.add(BigInteger.valueOf(b)).compareTo(primeArray[primeArray.length -1])  <0)
{
System.out.println("[isPrimeXBin].1.move right middle=" + middle);
start = middle; 
}
//2.if lbound , p-a ,  ubound , p+a , then move to left  -
if( p.subtract(BigInteger.valueOf(a)).compareTo( primeArray [0] ) > 0 
&& p.add(BigInteger.valueOf(b)).compareTo(primeArray[primeArray.length -1])  >0)
{
System.out.println("[isPrimeXBin].2.move left middle=" + middle);
end = middle; 
}
//3.if p-a  , lbound ,ubound , p+b , over
if( p.subtract(BigInteger.valueOf(a)).compareTo( primeArray [0] ) < 0 
&& p.add(BigInteger.valueOf(b)).compareTo(primeArray[primeArray.length -1])  >0)
{
System.out.println("[isPrimeXBin].3.over bound");
overBound = true;
break;
}
//4.if lbound , p-a , p+b , ubound , over
if( p.subtract(BigInteger.valueOf(a)).compareTo( primeArray [0] ) > 0 
&& p.add(BigInteger.valueOf(b)).compareTo(primeArray[primeArray.length -1])  <0)
{
System.out.println("[isPrimeXBin].4.over bound");
overBound = true;
break;
}
  
          middle=(start+end)/2;
          p = primeArray[middle];
          count++;
          if(count>(primeArray.length-1)/2) 
          {
           overBound = true;
           break;
          }
    } if (!overBound)
{
pArray[0]=p;
isPrime =true;
}

return isPrime;

}

private boolean isPrimeX(BigInteger primeArray[] ,   int a , int b , BigInteger pArray[])
{
boolean isPrimeFlag = false;

System.out.println("[isPrimeX].a=" + a );
System.out.println("[isPrimeX].b=" + b );

for (int i = 1 ;i<primeArray.length -1 ;i++)
{
BigInteger p = primeArray[i];

System.out.println("[isPrimeX].p=" + p.toString());
System.out.println("[isPrimeX].p.subtract(BigInteger.valueOf(a))=" + p.subtract(BigInteger.valueOf(a)).toString());

if(p.subtract(BigInteger.valueOf(a)).compareTo(BigInteger.valueOf(0))>0)
{
System.out.println("[isPrimeX].primeArray[0]=" + primeArray[0].toString());
System.out.println("[isPrimeX].primeArray[1]=" + primeArray[1].toString());
System.out.println("[isPrimeX].p.add(BigInteger.valueOf(b))=" + p.add(BigInteger.valueOf(b)).toString());
System.out.println("[isPrimeX].primeArray[primeArray.length -2]=" + primeArray[primeArray.length -2].toString());
System.out.println("[isPrimeX].primeArray[primeArray.length -1]=" + primeArray[primeArray.length -1].toString());

if(p.subtract(BigInteger.valueOf(a)).compareTo( primeArray [0] ) > 0
&& p.subtract(BigInteger.valueOf(a)).compareTo( primeArray [1] ) <= 0
&& p.add(BigInteger.valueOf(b)).compareTo(primeArray[primeArray.length -2])  >=0
&& p.add(BigInteger.valueOf(b)).compareTo(primeArray[primeArray.length -1])  <0)
{
isPrimeFlag = true;
System.out.println("[isPrimeX].p.****Found***=" + p.toString());
pArray[0] = p;
return isPrimeFlag;
}
}
}
return isPrimeFlag;
}

public static void main(String args[])
{
IsolatedPrimes isp = new IsolatedPrimes();
 
 
int x = 2;
int a = 5;
int b = 5;


//String s = isp.findPrime(x, a, b);

//String s = isp.findPrime(410,5954,1916);
String s = isp.findPrime(400,4067,9810);
System.out.println("[main].findPrime=" + s);
 
 

} 
}、大家给一些思路优化。

Answer 1

public class PrimeTest {
// 判断一个整数num是否是素数
public static boolean checkPrime(int num) {
if (num <= 0)// 负数和0不是素数
{
return false;
}
if (num == 1 || num == 2)// 1和2是素数
{
return true;
}
for (int i = 2; i <= Math.sqrt(num); i++) {
if (num % i == 0) {
return false;
}
}
return true;
} // 获取start——end间素数的个数，并打印出素数
public static int getPrimeNum(int start, int end) {
int sum = 0;
for (int i = start; i <= end; i++) {
if (checkPrime(i) == true)// 是素数
{
System.out.print(i + " ");
sum++;
}
}
return sum;
} public static void main(String args[]) {
int start = 100;
int end = 200;
int sum = getPrimeNum(start, end);
System.out.println("\n" + start + "~" + end + "间共有" + sum + "个素数!");
}
}