faster Sieve of Erathostenes and prime number factorization in Java

Question

My input is an Integer. Up to that value, all prime numbers should be found and printed in 5 columns, then I have to "prime factorize" the integer and print the result.

It wokrs fine, but it'ts too slow...

public class Bsp07 {
  public static void main(String[] args) {

     System.out.println("Enter the upper bound for prime number search");
     int n = SavitchIn.readLineInt();
     int[] aZahlen = new int[n - 1];
     for (int el = 0, zahl = 2; el != n - 1; el++, zahl++)
        aZahlen[el] = zahl;

     int p = 2, altesP; // next unmarked number
     boolean aus = false; // when unmarked elements are "aus" (off)

     while (aus == false) {

     // marks Elements; using For loop since for-each loop doesn't work
        for (int i = 0; i < aZahlen.length; i++) {
           if ((aZahlen[i] % p == 0) && (aZahlen[i] != p))
              aZahlen[i] = 0;
        }

        altesP = p; // merkt sich altes p
     // update p, find next unmarked Element
        for (int el : aZahlen) {
           if ((el != 0) && (el > altesP)) {
              p = el;
              break;
           }
        }
     // if p stayed the same unmarked elements are "aus" (off)
        if (altesP == p)
           aus = true;
     }

     int nervVar = 0;
     for (int pr : aZahlen) {
        if(pr==0) 
           continue;
        System.out.print(pr + " ");
        nervVar++;
        if ((nervVar % 5 == 0)) System.out.print("\n");
     }

     /* Factorization */
     System.out.print("\n" + n + " = ");
     for (int i = 0, f = 0; n != 1; i++, f++) {
        while(aZahlen[i]==0) i++;
     /*
      * If the prime divides: divide by it, print the prime,
      * Counter for further continuous decrease with prime number if n = 1,
      * Stop
      */
        if (n % aZahlen[i] == 0) {
           n /= aZahlen[i];
        // So that the first time is not *
           if (f != 0)
              System.out.print(" * " + aZahlen[i]);
           else
              System.out.print(aZahlen[i]);
           i--;
        }
        // So that f remains zero if no division by 2
        else
           f--;
     }
     System.out.println();
  }

}

Where can I save some resources? btw I can only use arrays for now... Sorry for the german comments. Just if some really unnecessary long loop or something similar catches your eye

Thanks!

Answer 1

Instead of searching up to n-1, I would only search up to (int) sqrt(n). Figure out why this is sufficient yourself. ;-)

I do not get why you need altesP at all. Can't you just increment p by two?

I wouldn't filter by striking out. I would build a positive list, and add the prime numbers you have found.

Look into fast primeness tests that can rule out a number without having to go through the whole sieve.

So do the following changes to your code, please:

1. instead of erasing aZahlen, build a list of primes. sqrtN = (int)sqrt(n) as allocation size should be fine, and use a count foundPrimes for how many primes you know.

2. Iterate over p up to <= sqrtN without any fuzz. See if any of the known primes is a divisor, otherwise you found a new prime. Output it, and store it in your foundPrimes list.