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.

Answer 2

An int[] uses 32-bit per value. If you use byte[] this will use 8-bits per value and if you use BitSet, it will use 1-bit per value (32x smaller)

Answer 3

I'm not sure what you want to do. I think you are trying to factor an integer by trial division by primes. For that, you don't need all the primes less than the integer, only the primes less than the square root of the integer, so all you need is a simple Sieve of Eratosthenes to select the primes:

function sieve(n)
  bits := makeArray(2..n, True)
  ps := []
  for p from 2 to n
    if bits[p]
      ps.append(p)
      for i from p+p to n step p
        bits[i] = False
  return ps

Then you can use those primes to perform the factorization:

function factors(n)
  ps := primes(sqrt(n))
  fs := []
  p := head(ps)
  while p*p <= n
    if n%p == 0
      fs.append(p)
      n := n / p
    else
      ps := tail(ps)
      p := head(ps)
  fs.append(n)
  return fs

I discuss programming with prime numbers in an essay at my blog, which includes implementations of both these algorithms in Java. The essay also includes other more efficient methods of enumerating primes and factoring integers that those given above.