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);
}
}、大家给一些思路优化。
一个质数是只能被自己和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);
}
}、大家给一些思路优化。
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 + "个素数!");
}
}