HI Guys,
I implemented the BPSW Test and am getting TLE for some submissions and wrong answers for another. Is there a way to check the input used that caused WA? Great help if something wrong can be pointed out in the below code. (Javascript Rhino).
// http://www.spoj.com/problems/TEST/
importPackage(java.io, java.lang);
var stdin = new BufferedReader(new InputStreamReader(System['in']));
var smallPrimes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41];
var getHighestPowerFactor = function (number, base) {
var index = 0, baseExp = base;
while (number % baseExp == 0 && number > 0) {
baseExp = baseExp * base;
index ++;
}
return index;
}
var millerRabin = function(num) {
var s = getHighestPowerFactor(num-1, 2),
d = num / Math.pow(2,s)
a = 2,
x = Math.pow(a,d) % num;
if(x === 1 || x === num - 1)
return true;
s--;
while(s-- > 0) {
x = Math.pow(x,2) % num;
if(x === 1)
return false;
if(x === num-1)
return true;
}
return true;
}
var jacobi = function(a, b) {
if(b<=0 || (b % 2) == 0)
return 0;
var j = 1;
if (a < 0){
a *= -1;
if(b % 4 === 3) j *= -1;
}
while(a!=0) {
while(a % 2 === 0){
a /= 2;
if([3,5].indexOf(b % 8) !== -1){
j *= -1;
}
}
var c = b; b = a; a = c;
if((a % 4 == 3) && (b % 4 == 3)){
j *= -1;
}
a = a % b;
}
if (b ==1)
return j;
return 0;
}
var isPrime = function(num) {
//BPSW test.
if(num <= 1) return false;
//print('Checking:'+num);
if(smallPrimes.indexOf(num) !== -1) return true;
//Step-1: Check against small primes by trial division method.
var smallPrimeIndex = 0;
while((num % smallPrimes[smallPrimeIndex] !== 0) && smallPrimeIndex < smallPrimes.length){
smallPrimeIndex++;
}
if(smallPrimeIndex < smallPrimes.length){
return false;
}
//print('Running Miller Rabin');
//Step-2: Base 2 strong probable prime test (Miller-Rabin)
var mrResult = millerRabin(num);
if(mrResult === false) {
return false;
}
//print('Finding Jacobi');
//Step-3: Find Jacobi symbol
var iterator = 5, jacobiVal;
jacobiVal = jacobi(iterator,num);
while(jacobiVal !== -1){
//print('Iterator:' + iterator + ' Value:'+jacobiVal);
iterator += (iterator > 0)? 2:-2;
iterator *= -1;
jacobiVal = jacobi(iterator,num);
//If iterator not found in 3-5 iterations, number is most likely a square.
if(Math.abs(iterator) > 17) {
var root = Math.sqrt(num);
if(Math.floor(root) === root){
//Found a perfect square.
return false;
}
}
}
//print('Running Lucas probable prime');
//Step-4: Lucas probable prime test
var p = 1, q = (1 - iterator)/4;
var bits = (num + 1).toString(2), currentBit = 1;
var target = parseInt(bits.substring(0,currentBit + 1), 2);
var u1 = 1, v1 = p;
var uPrev = u1, vPrev = v1;
var uCurrent = uPrev, vCurrent = vPrev;
while(currentBit <= bits.length) {
if(target % 2 === 0) {
uCurrent = uPrev*vPrev;
vCurrent = vPrev*vPrev - 2*Math.pow(q,target/2);
} else{
uCurrent = (p*uPrev + vPrev)/2;
vCurrent = (iterator*uPrev + p*vPrev)/2;
}
uPrev = uCurrent;
vPrev = vCurrent;
currentBit++;
target = parseInt(bits.substring(0, currentBit + 1), 2);
}
return !(uCurrent === 0);
}
var noOfCases = parseInt(stdin.readLine());
var output = [];
while(noOfCases-- > 0){
var range = stdin.readLine();
var low = parseInt(range.split(' ')[0]),
high = parseInt(range.split(' ')[1]);
var primes = [];
while(low<=high){
if(isPrime(low++)){
primes.push(low-1);
//print('Found prime:'+ (low-1));
}
}
output.push(primes);
}
for(var i=0; i< output.length; i++){
for(var j=0;j print(output[i][j]);
}
print('');
}
For the range 999900000 1000000000, the number of primes I get is 14507 (may be incorrect). If I try to print all of them, I get Runtime error (Signal:25). if I just print the count, it terminates correctly. Makes me conclude that it is the printing of 14507 numbers that is causing a TLE. Do you guys think there is way to reduce that? (unless it is impossible to have that high a result).
On my local machine, I am able to print all the numbers in < 5s for the same range.