J
j1mb0jay
I am now trying to improve upon the way in which i calculate if a number
is prime. I understand their a several probabilist prime checks out
their, but i would like one that give a yes or no rather than a very
mathematical maybe.
Firstly i would like to point out that i am going to be working with
numbers smaller than (2^64)-1 (AKA LONG) I have attached a rather large
amount of code to this post, the code is my implementation of the Sieve
of Atkin method.
The first thing i would like to know... is there are fast prime checker.
The second thing i would like to know is how could i improve upon the
execution time of the method.
-------------------A lot of Code------------------------------------------
package math;
public class Prime
{
/**
* Finds the next prime number greater than the "testSubject"
*
* @param testSubject - the number you want to find the next
prime for.
* @return - the next prime after the test subject
*/
public static long nextPrime(long testSubject)
{
//long startTime = System.currentTimeMillis();
while(!isPrime(testSubject))
{
testSubject++;
}
//System.out.println("\n" + ((double)((double)
System.currentTimeMillis() - (double)startTime) / 1000.0) + " seconds");
return testSubject;
}
/**
* Test to see if a number is a prime number. The method uses the
Sieve of Atkin
* mathmatical formula to test if a number is prime. This is one
of the quickest methods
* of our time.
*
*
* @param testSubject - the number you want to test is prime or
not.
* @return - true if "testSubject" is a prime number.
*/
public static boolean isPrime(long testSubject)
{
if(isLowPrime(testSubject))
{
return true;
}
else
{
if(fastFail(testSubject))
return false;
long mod = testSubject % 60;
if(mod == 1 || mod == 13 || mod == 17 || mod ==
29 || mod == 37 || mod == 41 || mod == 49 || mod == 53)
{
return firstStep(testSubject, 4);
}
else if(mod == 7 || mod == 19 || mod == 31 ||
mod == 43)
{
return firstStep(testSubject, 3);
}
else if(mod == 11 || mod == 23 || mod == 47 ||
mod == 59)
{
return secondStep(testSubject);
}
else
{
return false;
}
}
}
/**
* This method is called for the first and second case of the
Sieve of Atkin method.
* Thus meaning the answer to testSubject % 60 was equal to
* 1,13,17,29,37,41,49,53 for the first case or 7,19,31,43 for
the second case.
*
* This only means the number has a chance of being prime, to
find out for sure
* this method will get the sum of solutions to the follow
equation
*
* 4x^2 + y^2 = "testSubject" for the first case or 3x^2 + y^2 =
"testSubject".
*
* If the sum of the soluations is not perfectly divisable by 2
and the "testSubject"
* is a SquareFree number then the "testSubject" is prime.
*
* @param testSubject - the number that is been tested to see if
it prime.
* @param offSet - because the first and second case are so
simaler this number is either a 3 or 4.
* Depending on if the first or second case is been used.
* @return - true if "testSubject" is a prime number.
*/
private static boolean firstStep(long testSubject, int offSet)
{
//Calcualte the end point of the loop.
long endYPoint = (long)Math.sqrt(testSubject);
long endXPoint = (long)Math.sqrt((testSubject / offSet));
//Variable to store the sum of solutions.
long rightAnswers = 0;
//Loops until it has found all of the solutions.
for(int x = 1; x <= endXPoint; x++)
{
for(int y = 1; y <= endYPoint; y++)
{
if(((x*x) * offSet + (y*y)) ==
testSubject)
{
rightAnswers++;
}
}
}
//If the sum of solutions goes into two perfectly then
testSubject is not a prime.
if(rightAnswers % 2 == 0)
{
return false;
}
else
{
//If the testSubejct is SquareFree then it is a
prime number.
if(SquareFree.isSquareFree(testSubject))
{
return true;
}
else
{
return false;
}
}
}
/**
* This method is called for the third case of the Sieve of Atkin
method.
* Thus meaning the answer to testSubject % 60 was equal to
* 11,23,47,59
*
* This only means the number has a chance of being prime, to
find out for sure
* this method will get the sum of solutions to the follow
equation
*
* 3x^2 - y^2 = "testSubject" where x > y.
*
* If the sum of the soluations is not perfectly divisable by 2
and the "testSubject"
* is a SquareFree number then the "testSubject" is prime.
*
* @param testSubject - the number that is been tested to see if
it prime.
* @return - true if "testSubject" is a prime number.
*/
private static boolean secondStep(long testSubject)
{
long endPoint = (long)Math.sqrt((testSubject / 2));
int rightAnswers = 0;
for(int x = 1; x <= endPoint; x++)
{
for(int y = 1; y <= endPoint; y++)
{
if(x > y)
{
if(((x*x) * 3 - (y*y)) ==
testSubject)
{
rightAnswers++;
}
}
}
}
if(rightAnswers % 2 == 0)
{
return false;
}
else
{
if(SquareFree.isSquareFree(testSubject))
{
return true;
}
else
{
return false;
}
}
}
/**
* Sieve of Atkins fuction does not work the first three primes.
*
* @param testSubject - the number that is been tested to see if
it is prime.
* @return - true if "testSubject" is equal to the first three
primes (2,3 or 5).
*/
private static boolean isLowPrime(long testSubject)
{
if(testSubject==2||testSubject==3||testSubject==5)
return true;
return false;
}
/**
* When testing large numbers it can take along time to check if
a
* number is prime. It is a face that even numbers are not prime.
* Numbers than end in a 5 or a 0 are also not prime.
*
* This check can help save a lot of time.
*
* @param testSubject - the number to test is prime.
* @return - true if the number passed the fast fail, true does
not mean the number is prime,
* it just mean it might be.
*/
private static boolean fastFail(long testSubject)
{
if(testSubject % 2 == 0)
return true;
if(testSubject % 5 == 0)
return true;
return false;
}
}
/**
* A number is sqaure free if it is divisible by no perfect
square (except 1).
*
* @param testSubject
* @return - true if the "testSubject" is a square free number.
*/
public static boolean isSquareFree(double testSubject)
{
double answer;
for(int i = 1; i < testSubject; i++)
{
answer = Math.sqrt(testSubject / (double)i);
if(answer < 1)
return false;
if(answer % 1.0 == 0)
return false;
}
return true;
}
Regards j1mb0jay
is prime. I understand their a several probabilist prime checks out
their, but i would like one that give a yes or no rather than a very
mathematical maybe.
Firstly i would like to point out that i am going to be working with
numbers smaller than (2^64)-1 (AKA LONG) I have attached a rather large
amount of code to this post, the code is my implementation of the Sieve
of Atkin method.
The first thing i would like to know... is there are fast prime checker.
The second thing i would like to know is how could i improve upon the
execution time of the method.
-------------------A lot of Code------------------------------------------
package math;
public class Prime
{
/**
* Finds the next prime number greater than the "testSubject"
*
* @param testSubject - the number you want to find the next
prime for.
* @return - the next prime after the test subject
*/
public static long nextPrime(long testSubject)
{
//long startTime = System.currentTimeMillis();
while(!isPrime(testSubject))
{
testSubject++;
}
//System.out.println("\n" + ((double)((double)
System.currentTimeMillis() - (double)startTime) / 1000.0) + " seconds");
return testSubject;
}
/**
* Test to see if a number is a prime number. The method uses the
Sieve of Atkin
* mathmatical formula to test if a number is prime. This is one
of the quickest methods
* of our time.
*
*
* @param testSubject - the number you want to test is prime or
not.
* @return - true if "testSubject" is a prime number.
*/
public static boolean isPrime(long testSubject)
{
if(isLowPrime(testSubject))
{
return true;
}
else
{
if(fastFail(testSubject))
return false;
long mod = testSubject % 60;
if(mod == 1 || mod == 13 || mod == 17 || mod ==
29 || mod == 37 || mod == 41 || mod == 49 || mod == 53)
{
return firstStep(testSubject, 4);
}
else if(mod == 7 || mod == 19 || mod == 31 ||
mod == 43)
{
return firstStep(testSubject, 3);
}
else if(mod == 11 || mod == 23 || mod == 47 ||
mod == 59)
{
return secondStep(testSubject);
}
else
{
return false;
}
}
}
/**
* This method is called for the first and second case of the
Sieve of Atkin method.
* Thus meaning the answer to testSubject % 60 was equal to
* 1,13,17,29,37,41,49,53 for the first case or 7,19,31,43 for
the second case.
*
* This only means the number has a chance of being prime, to
find out for sure
* this method will get the sum of solutions to the follow
equation
*
* 4x^2 + y^2 = "testSubject" for the first case or 3x^2 + y^2 =
"testSubject".
*
* If the sum of the soluations is not perfectly divisable by 2
and the "testSubject"
* is a SquareFree number then the "testSubject" is prime.
*
* @param testSubject - the number that is been tested to see if
it prime.
* @param offSet - because the first and second case are so
simaler this number is either a 3 or 4.
* Depending on if the first or second case is been used.
* @return - true if "testSubject" is a prime number.
*/
private static boolean firstStep(long testSubject, int offSet)
{
//Calcualte the end point of the loop.
long endYPoint = (long)Math.sqrt(testSubject);
long endXPoint = (long)Math.sqrt((testSubject / offSet));
//Variable to store the sum of solutions.
long rightAnswers = 0;
//Loops until it has found all of the solutions.
for(int x = 1; x <= endXPoint; x++)
{
for(int y = 1; y <= endYPoint; y++)
{
if(((x*x) * offSet + (y*y)) ==
testSubject)
{
rightAnswers++;
}
}
}
//If the sum of solutions goes into two perfectly then
testSubject is not a prime.
if(rightAnswers % 2 == 0)
{
return false;
}
else
{
//If the testSubejct is SquareFree then it is a
prime number.
if(SquareFree.isSquareFree(testSubject))
{
return true;
}
else
{
return false;
}
}
}
/**
* This method is called for the third case of the Sieve of Atkin
method.
* Thus meaning the answer to testSubject % 60 was equal to
* 11,23,47,59
*
* This only means the number has a chance of being prime, to
find out for sure
* this method will get the sum of solutions to the follow
equation
*
* 3x^2 - y^2 = "testSubject" where x > y.
*
* If the sum of the soluations is not perfectly divisable by 2
and the "testSubject"
* is a SquareFree number then the "testSubject" is prime.
*
* @param testSubject - the number that is been tested to see if
it prime.
* @return - true if "testSubject" is a prime number.
*/
private static boolean secondStep(long testSubject)
{
long endPoint = (long)Math.sqrt((testSubject / 2));
int rightAnswers = 0;
for(int x = 1; x <= endPoint; x++)
{
for(int y = 1; y <= endPoint; y++)
{
if(x > y)
{
if(((x*x) * 3 - (y*y)) ==
testSubject)
{
rightAnswers++;
}
}
}
}
if(rightAnswers % 2 == 0)
{
return false;
}
else
{
if(SquareFree.isSquareFree(testSubject))
{
return true;
}
else
{
return false;
}
}
}
/**
* Sieve of Atkins fuction does not work the first three primes.
*
* @param testSubject - the number that is been tested to see if
it is prime.
* @return - true if "testSubject" is equal to the first three
primes (2,3 or 5).
*/
private static boolean isLowPrime(long testSubject)
{
if(testSubject==2||testSubject==3||testSubject==5)
return true;
return false;
}
/**
* When testing large numbers it can take along time to check if
a
* number is prime. It is a face that even numbers are not prime.
* Numbers than end in a 5 or a 0 are also not prime.
*
* This check can help save a lot of time.
*
* @param testSubject - the number to test is prime.
* @return - true if the number passed the fast fail, true does
not mean the number is prime,
* it just mean it might be.
*/
private static boolean fastFail(long testSubject)
{
if(testSubject % 2 == 0)
return true;
if(testSubject % 5 == 0)
return true;
return false;
}
}
/**
* A number is sqaure free if it is divisible by no perfect
square (except 1).
*
* @param testSubject
* @return - true if the "testSubject" is a square free number.
*/
public static boolean isSquareFree(double testSubject)
{
double answer;
for(int i = 1; i < testSubject; i++)
{
answer = Math.sqrt(testSubject / (double)i);
if(answer < 1)
return false;
if(answer % 1.0 == 0)
return false;
}
return true;
}
Regards j1mb0jay
