# Finding prime numbers performance

I am writing an app that finds prime numbers within a specified range. Currently i am updating almost every part of the app and i have also changed the way i find prime numbers. The problem is that the new method seems to be much slower. As a test, the old method takes only 8 seconds to find all the primes from 0 - 100,000. The same task takes the new method between 25 - 30 seconds to complete. I'm not sure why the new method is so much slower. Is there anything i can do to make the new method faster, or at least comparable to the old method, while still keeping the functionality (like the ability to pause it).

Since the code is quite long i have posted links to them as well.

Old Method Full class

public class PrimeFinderThread implements Runnable{
//Flow control booleans
public boolean scanningNumbers = false;
public boolean stoppedScanning = true;

//Current number being scanned
public long currentNumber = 2;

//Scan progress of current number
public double currentNumberProgress = 0;

//List of all found prime numbers
public List<Long> primeNumbers = new ArrayList<>();

//Buffer for numbers per second
public List<Double> numbersPerSecondArray = new ArrayList<>();

//Times for elapsed time calculation
public long scanStartTime = 0;
public long pausedTime = 0;
public long elapsedTime = 0;
public long lastUpdateTime = 0;
public long loopStartTime = 0;
public long loopEndTime = 0;
public long lastOneSecondUpdateTime;

//Maximum number to check when scanning for primes
private double sqrtMax = 0;

//Numbers scanned per second
public int numbersPerSecond = 0;

//Prime numbers found per second
public int primesPerSecond = 0;
public int primesSinceLastSecond = 0;

@Override
public void run(){
scanningNumbersLoop: while (scanningNumbers){
stoppedScanning = false;
loopStartTime = System.nanoTime();
currentNumberProgress = 0;

boolean isPrime = true;
sqrtMax = Math.round(Math.sqrt(currentNumber));
for (int i = 2; i <= sqrtMax; i++){

//Check if number is prime
double actualNumber =  (double) currentNumber / i;
double roundedNumber = Math.round(actualNumber);

//Number is not prime, break out of the loop
if (actualNumber == roundedNumber){
isPrime = false;
break;
}

break scanningNumbersLoop;
}
}

//Number is prime, add it to the list
if (isPrime){
primesSinceLastSecond++;
}

//Stop thread if end value was reached
if (currentNumber == ScanForPrimesFragment.endValue){
scanningNumbers = false;
currentNumberProgress = 100;
sendUpdateMessage("endValueReached");
break;
}

//Increase variables
currentNumber++;
loopEndTime = System.nanoTime();
}
//Thread has stopped scanning for prime numbers
stoppedScanning = true;
}
}

/**
* Called every few milliseconds to update elapsed time and other stats
* @param i Current iteration of the loop
*/
//Update current number progress
currentNumberProgress = (i / sqrtMax) * 100;

//Update the time elapsed
elapsedTime = System.currentTimeMillis() - scanStartTime;

//Update every second
if (System.currentTimeMillis() - lastOneSecondUpdateTime >= 1000){

primesPerSecond = primesSinceLastSecond;
primesSinceLastSecond = 0;

lastOneSecondUpdateTime = System.currentTimeMillis();
}

//Update ui
if (System.currentTimeMillis() - lastUpdateTime >= PrimeNumberFinder.UPDATE_LIMIT_MS){
lastUpdateTime = System.currentTimeMillis();
sendUpdateMessage(null);
}
}

/**
* Send a message to the handler telling the ui to update
*/
private void sendUpdateMessage(String msgData){
Message message = ScanForPrimesFragment.handler.obtainMessage();
Bundle bundle = new Bundle();
bundle.putString("currentNumber", String.valueOf(currentNumber));
bundle.putString("msgData", msgData);
message.setData(bundle);
ScanForPrimesFragment.handler.sendMessage(message);
}
}


New Method Full class

public class FindPrimesTask extends Task{

/**
* Tag used for logging and debugging.
*/
private static final String TAG = "FindPrimesTask";

/**
* List of all prime numbers found.
*/
private final List<Long> primeNumbers = new ArrayList<>();

/**
* Start and end values. The end value can be modified after the task has started if the user
* pauses it first. If the end value is set to {@link #LIMIT_NO_LIMIT}, then the task will run
* forever until stopped by the user or interrupted.
*/
private final long startValue;
private long endValue;

/**
* If the end value is set to this, then the runnable will run forever until stopped by the
* user or interrupted.
*/
public static final int LIMIT_NO_LIMIT = -1;

/**
* The current number we are checking.
*/
private long currentNumber;

/**
* The search progress on the current number as a decimal between 0 and 1.
*/
private float currentProgress = 0;

private long totalCheckTime;
private int numbersChecked;

private final List<EventListener> eventListeners = new ArrayList<>();

private long[] lastUpdateTimes = new long[2];

Map<Long, Long> map;
Map<Long, Long> primesMap;

/**
* Create a new {@link FindPrimesTask} to search for prime numbers within a given range.
*
* @param startValue The beginning of the search range.
* @param endValue The end of the search range.
*/
public FindPrimesTask(final long startValue, final long endValue){
this.startValue = startValue;
this.endValue = endValue;

map = ExpiringMap.builder().expiration(1000, TimeUnit.MILLISECONDS).build();
primesMap = ExpiringMap.builder().expiration(1000, TimeUnit.MILLISECONDS).build();
}

@Override
public void run(){

dispatchStarted();

/**
* Set the current number to the start value. If the start value is less then 2, then set
* it to 2 because that is the lowest prime number.
*/
if (startValue < 3){
if (endValue >= 2){
sendOnPrimeFound(2);
}

currentNumber = 3;
}else{
currentNumber = startValue;
}

int sqrtMax;
boolean isPrime;

boolean running = true;

//Loop forever
while (running){

//Check if the end value has been reached
if (endValue == LIMIT_NO_LIMIT || currentNumber <= endValue){

//Check if the number is divisible by 2
if (currentNumber % 2 != 0){

/**
* Get the square root of the number. We only need to calculate up to the square
* root to determine if the number is prime. The square root of a long will
* always fit inside the value range of an int.
*/
sqrtMax = (int) Math.sqrt(currentNumber);

//Assume the number is prime
isPrime = true;

final long checkStartTime = System.nanoTime();

/**
* Check if the number is divisible by every odd number below it's square root.
*/
for (int i = 3; i <= sqrtMax; i += 2){

//Check if the number divides perfectly
if (currentNumber % i == 0){
isPrime = false;
break;
}

//Calculate current progress
currentProgress = (float) i / sqrtMax;
sendOnProgressChanged(currentProgress);

//Check if we should pause
tryPause();
if (shouldStop()){
running = false;
break;
}
}

numbersChecked++;
totalCheckTime += (System.nanoTime() - checkStartTime);

//Check if the number was prime
if (isPrime){
synchronized (LOCK){
//primesMap.put(currentNumber, currentNumber);
}

sendOnPrimeFound(currentNumber);
}
}

//Increase currentNumber
currentNumber++;
//map.put(currentNumber, currentNumber);

//Calculate total progress
if (endValue != LIMIT_NO_LIMIT){
setProgress((float) (currentNumber - startValue) / (endValue - startValue));
}

}else{
currentNumber = endValue;
currentProgress = 1f;
setProgress(1);
//isRunning = false;
break;
}
}

dispatchStopped();

if (currentNumber == endValue){
dispatchFinished();
}

}

public long getAverageCheckTime(){
return (totalCheckTime - getTotalPauseTime()) / numbersChecked;
}

public void setEndValue(long endValue){
this.endValue = endValue;
}

public float getCurrentProgress(){
return currentProgress;
}

public long getCurrentNumber(){
return currentNumber;
}

public long getEndValue(){
return endValue;
}

public long getStartValue(){
return startValue;
}

public long getNumbersPerSecond(){
return map.size();
}

public long getPrimesPerSecond(){
return primesMap.size();
}

}

public interface EventListener{
void onPrimeFound(final long prime);
}

private void sendOnPrimeFound(final long prime){
for (EventListener eventListener : eventListeners){
eventListener.onPrimeFound(prime);
}
}
}


The new method extends from Task, which is just a simple class extending from Thread

public abstract class Task implements Runnable{

/**
* Tag used for logging and debugging.
*/
private static final String TAG = "Task";

/**
*/

/**
*/
public enum State{
NOT_STARTED,
RUNNING,
PAUSED,
STOPPED,
FINISHED
}

/**
*/
private State state = State.NOT_STARTED;

/**
* Total task progress. If ongoing task, progress will remain at 0.
*/
private float progress = 0f;

/**
* Keep track of when the task was started and paused. These values are also used to calculate
* the elapsed time.
*/
private long startTime;
private long lastPauseTime;
private long totalPauseTime;

/**
* Lock used to pause the current thread when the task is paused.
*/
protected final Object LOCK = new Object();

private boolean requestPause = false;
private boolean requestStop = false;

//Override methods

@Override
public abstract void run();

//Utility methods

protected void tryPause(){
if (requestPause){
synchronized (LOCK){
try{

//Pause
dispatchPaused();
Log.e(TAG, "Time elapsed pause: " + getTimeElapsed());

//Wait until notified to resume
LOCK.wait();

//Resume
dispatchResumed();

}catch (InterruptedException e){
Log.e(TAG, "Task was interrupted while paused!");
}
}
}
}

protected boolean shouldStop(){
return requestStop;
}

//Lifecycle methods

public void start(){
run();
}

protected void dispatchStarted(){
this.startTime = System.currentTimeMillis();
setState(State.RUNNING);
}

public void pause(){
requestPause = true;
}

private void dispatchPaused(){
requestPause = false;
lastPauseTime = System.currentTimeMillis();
setState(State.PAUSED);
}

public void resume(){
synchronized (LOCK){
LOCK.notify();
}
}

private void dispatchResumed(){
totalPauseTime += (System.currentTimeMillis() - lastPauseTime);
setState(State.RUNNING);
}

protected void dispatchStopped(){
setState(State.STOPPED);
}

protected void dispatchFinished(){
setState(State.FINISHED);
}

public void stop(){
requestStop = true;
}

//Getters and setters

}

public long getTimeElapsed(){
if (startTime == 0){
return 0;
}
return System.currentTimeMillis() - startTime - totalPauseTime;
}

public float getProgress(){
return progress;
}

public void setProgress(float progress){
this.progress = progress;
}

public State getState(){
return state;
}

private void setState(State state){
this.state = state;
switch (state){
case PAUSED:
break;

case STOPPED:
break;

case FINISHED:
break;
}
}

protected long getTotalPauseTime(){
}

//Callbacks

}
}

}
}

}
}

}
}

}
}

protected void sendOnProgressChanged(final float percent){
}
}
}

• You have not included sufficent information to compile and run you code. First, show your imports: import java.util.ArrayList;, import java.util.List; etc. Then, make sure all dependencies are included. For example, what is ScanForPrimesFragment? Where is it defined? Mar 12, 2017 at 3:50
• You do not appear to be using the sieve of Eratosthenes. That will run a lot faster than your current method - dividing by odd number. A sieve will allow you to divide only by prime numbers, omitting 9, 15, 21 25 etc. Mar 12, 2017 at 12:29
• Also not an answer to your question, but a "+1" to rossums comment: just to get a feeling for the time needed, I hacked together a sieve of erastosthenes to calculate the prime numbers from 0 to 100000 and came to a runtime of 3 ms (modern hardware, single threaded). Extending this to a million goes up to 13 ms on my system. Thus, whatever you do, your algorithm seems to be so sub-par, that following through with it is probably not worthwile.
– mtj
Mar 14, 2017 at 6:45
• My tests were all run on an android device in a single thread, so i wasn't expecting great performance. However i was able to bring the time down to about 2 seconds (for 100,000). I have also tested this code on my PC (i7-4990 @ 3.6Ghz) and it took 20ms to get to 100,000 and about 280ms to get to 1 mil (again on a single thread). In the code I posted above, i found that sendOnProgressChanged() was taking a relatively long time, considering it is called every iteration. Removing that helped the performance, but I think i might take your suggestion and implement the sieve. Thanks for the help! Mar 14, 2017 at 23:38

I think you are doing good stuff but your code looks so much complex because you have combined 3 things together.

1) Finding prime numbers