Project Euler: optimizing programs for task 7?

Question

Thus, I would call myself a fairly novice programmer, since I mainly focused on the hardware in my school, and not many courses in computer science.

So, I solved the 7 Project Euler task:

Having listed the first six prime numbers: 2, 3, 5, 7, 11, and 13, we will see that the 6th prime number is 13.

What is the 10001st number of primes?

I managed to solve this problem without any problems in Java, but when I launched my solution, it took 8 and the number of seconds to execute changed. I was wondering how this can be optimized from a programming point of view, and not from a mathematical point of view.

Are array loop cycles and while operations the main ones of which are processing time? And how can this be optimized? Again, don't look for a fancy math equation. There are many solutions in the flow of decisions.

SPOILER My solution is given below.

public class PrimeNumberList {

private ArrayList<BigInteger> primesList = new ArrayList<BigInteger>();

public void fillList(int numberOfPrimes) {
    primesList.add(new BigInteger("2"));
    primesList.add(new BigInteger("3"));
    while (primesList.size() < numberOfPrimes){
        getNextPrime();
    }
}

private void getNextPrime() {
    BigInteger lastPrime = primesList.get(primesList.size()-1);
    BigInteger currentTestNumber = lastPrime;
    BigInteger modulusResult;
    boolean prime = false;
    while(!prime){
        prime = true;
        currentTestNumber = currentTestNumber.add(new BigInteger("2"));
        for (BigInteger bi : primesList){
            modulusResult = currentTestNumber.mod(bi);
            if (modulusResult.equals(BigInteger.ZERO)){
                prime = false;
                break;
            }
        }
        if(prime){
            primesList.add(currentTestNumber);
        }
    }
}

public BigInteger get(int primeTerm) {
    return primesList.get(primeTerm - 1);
}

}

Answer 1

Since the 10001st number of primes is not so large, you can start with longinstead BigInteger. An instance BigIntegeris a full-fledged Java object, and there is a lot of overhead in creating and managing it.

Answer 2

, , for (BigInteger bi : primesList) - , . . , , , .

( ) new BigInteger("2") BigInteger while. < - - - , , .

Answer 3

" " , BitSet, , .

Answer 4

ints. primesList, ( , ).

int, .

Answer 5

while(!prime) getNextPrime(), , fillList size() . , , , , 1.

, LinkedList ArrayList. .

Answer 6

int/long , , . , for, Math.sqrt(num).

: http://www.mycoding.net/2012/01/program-to-find-10001st-prime-number-project-euler-problem-7/

Answer 7

, . . , . , 9999.

Answer 8

.NET-... , 10001st prime 132 100 000 4417 .

public static IEnumerable<long> GetPrimes(int numberPrimes)
{
  List<long> primes = new List<long> { 1, 2, 3 };
  long startTest = 3;

  while (primes.Count() < numberPrimes)
  {
    startTest += 2;
    bool prime = true;
    for (int pos = 2; pos < primes.Count() && primes[pos] < Math.Sqrt(startTest); pos++)
    {
      if (startTest % primes[pos] == 0)
      {
        prime = false;
      }
    }
    if (prime)
      primes.Add(startTest);
  }
  return primes;
}

Answer 9

I just translated the Sieve of Eratosthenes into Java. It should be one of the most efficient ways to solve primes algorithmically.

public static void main(String[] args){

    ArrayList<Integer> List = new ArrayList<Integer>();
    ArrayList<Integer> Primes = new ArrayList<Integer>();
    Primes.add(2);
    Integer p=2;
    Integer n=105000; 
    Integer i=1;

    while(p < n) {

        i=1;

        while((p*i)<=n) {
            List.add(p*i);
            i++;
        }

        while (p < n) {
            p++;
            if(List.contains(p)){                     }
            else                {Primes.add(p); break;}
        }

    }

    System.out.println("PRIME 10,001 is.... " + Primes.get(10000));
    // 104743

}