Examination bonus point projects

The project's goal is about:

We start with the first task by implementing the Euler sieve algorithm. We may use a boolean array representing e.g. the first 100 primes:

boolean[] nonPrimes = new boolean[100];

This array will initially be filled with 100 false values. The idea is using the Euler sieve algorithm to turn all non-prime value to true (t) and leaving al prime index values at false (f):

Index | 0| 1| 2| 3| 4| 5| 6| 7| 8| 9| 10| 11| 12| 13| 14 ...
------+--+--+--+--+--+--+--+--+--+--+---+---+---+---+--- ...
value | t| t| f| f| t| f| t| f| t| t|  t|  f|  t|  f|  t ...

Since we intend to deal with a large number Integer.MAX_VALUE of values (rather than just 100 ) we only consider odd values since even numbers are never prime except for the value 2. Thus 0 will represent 1, 1 will represent 3 and n will represent 2 * n + 1:

Index      | 0| 1| 2| 3| 4|  5|  6|  7| ...
-----------+--+--+--+--+--+---+---+---+ ...
represents | 1| 3| 5| 7| 9| 11| 13| 15| ... 
-----------+--+--+--+--+--+---+---+---+ ...
value      | t| f| f| f| t|  f|  f|  t| ...

This requires a boolean array of just Integer.MAX_VALUE / 2. Start from the following skeleton:

public class Sieve {

   final boolean[] nonPrimes;
   final int numPrimesFound;

   /**
    * Creating a prime number Euler variant sieve 
    * 
    * @param limit The last value to be considered. May or may not be prime.
    * 
    */
   public Sieve(final int limit) {
      ...// initialize nonPrimes and numPrimesFound.
   }
  ...

   /**
    * Test if a given value is prime or not
    * 
    * @param candidate The value in question.
    * 
    * @return True if value is prime, false otherwise.
    */
   public boolean isPrime(final int candidate) {
     // Based on nonPrimes array
     ...
   }
}

Once you've finished implementing the sieve continue by implementing the second task of prime decomposition. We recall the initial example:

1050 = 2 * 3 * 5 * 5 * 7

So the primes 2, 3 and 7 appear with frequency 1 whereas 5 appears with frequency 2. For meaningful operations we introduce a new class combining a prime number and its corresponding frequency of appearance to represent prime factor decompositions appropriately:

/**
 * Representing a single prime factor among with its
 * frequency.
 *
 */
public class PrimeFrequency {
   
   /**
    * The prime's immutable value.
    */
   public final int prime;
   
   /**
    * The prime's frequency of appearance. 
    */
   int frequency;
   
   /**
    * @param prime {@link #prime} 
    * @param frequency The prime's frequency of appearance.
    */
   public PrimeFrequency(final int prime, final int frequency) {
      this.prime = prime;
      this.frequency = frequency;
   }

   /**
    * @return The prime factor's frequency of appearance.
    */
   public int getFrequency() {
      return frequency;
   }
   
   /**
    * change the given frequency value.
    * @param frequency change by this value.
    */
   public void addFrequency(@SuppressWarnings("hiding") final int frequency) {
      this.frequency += frequency;
   }

   @Override
   public boolean equals(final Object obj) {
      ...
   }   
}

Now 2 * 3 * 5 * 5 * 7 may be represented by three (not four!) instances of PrimeFrequency. In order to represent the whole product implement a second container:

/**
 * Representing integer values by an ordered set of prime factors among with
 * their frequencies of appearance.
 *
 */
public class PrimeFrequencySet {

   private final static int initialCapacity = 16;
   
   private PrimeFrequency[] store = new PrimeFrequency[initialCapacity]; // May grow due to new factors.

   /**
    * Searching for the existence of a {@link PrimeFrequency} with a matching
    * prime value (frequency may be different!).
    * 
    * Example: If the set contains the prime values {3, 7, 11} (we ignore
    * frequencies) then searching for:
    * <ul>
    *   <li>3 return index 0</li>
    *   <li>11 returns index 2</li>
    *   <li>5 return -2</li>
    *   <li>13 returns -3</li>
    *   <li>2 returns -1</li>
    * </ul>
    * 
    * @param primeFrequency The candidate to be looked up.
    * 
    * @return If a prime value match exists return its index. If no match
    * exists return the negative value of the first index belonging to a set
    * value having a larger prime value than the candidate (the "natural"
    * insertion point) minus 1 (see example).
    */
   public int find(final PrimeFrequency primeFrequency) {
     ...
   }
   
   /**
    * Either add a new prime or just add a prime's frequency to an existing one.
    * 
    * @param primeFrequency If the prime is already in the current set, add its
    * frequency. Otherwise insert the new element preserving the order of prime
    * values.
    */
   public void add(final PrimeFrequency primeFrequency) {
     ...
   }
   
   /**
    * @return The count of all prime factors.
    */
   public int getLength() {
      ...
   }

   /**
    * The prime factor corresponding to a given index.
    * @param index .
    * @return .
    */
   public PrimeFrequency get(int index) {
      ...
   }
   
   /**
    * @return All prime factors among with their respective frequencies.
    */
   public PrimeFrequency[] get() {
     ...
   }
}

This allows for decomposing arbitrary int values into their prime factors. We show a unit test example:

/**
 * Prime factor decomposition.
 */
public class FactorTest {

   final Sieve sieve = new Sieve(100000);

   @Test
   public void test2 () {
      PrimeFrequencySet pfs = sieve.getPrimeFactors(12); ❶
      Assert.assertEquals(2, pfs.getLength()); ❷
      Assert.assertEquals(new PrimeFrequency(2, 2), pfs.get(0)); ❸
      Assert.assertEquals(new PrimeFrequency(3, 1), pfs.get(1)); ❹
   }
}

For better illustration we provide the following example:

public class Driver {

   /**
    * @param args Unused
    */
   public static void main( String[] args ) {
      
      final Sieve sieve = new Sieve(Integer.MAX_VALUE);

      
      int value = Integer.MAX_VALUE;
      System.out.println("Value " + value + " is " + 
        (sieve.isPrime(value)? "" : "not") + " prime.");

      value--; // Even Value
      
      System.out.println("Value " + value + " is " + 
            (sieve.isPrime(value)? "" : "not") + " prime.");

      value --; // Non-prime as well.
      System.out.println("Value " + value + " is " + 
            (sieve.isPrime(value)? "" : "not") + " prime.");


      value = Integer.MAX_VALUE - 1;
      final PrimeFrequencySet pfs = sieve.getPrimeFactors(value);
      
      System.out.print(value + " = ");
      String separator = "";
      for (PrimeFrequency pf : pfs.get()) {
         for (int i = 0; i < pf.getFrequency(); i++) {
            System.out.print(separator + pf.prime);
            separator = " * ";
         }
      }
      System.out.println();
   }
}

This yields the following output:

Value 2147483647 is  prime.
Value 2147483646 is not prime.
Value 2147483645 is not prime.
2147483646 = 2 * 3 * 3 * 7 * 11 * 31 * 151 * 331

Depending on your implementation you may encounter the following heap memory related error:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at de.hdm_stuttgart.mi.prim.sieve.Sieve.initSieve(Sieve.java:75)
	at de.hdm_stuttgart.mi.prim.sieve.Sieve.<init>(Sieve.java:60)
	at de.hdm_stuttgart.mi.prim.Driver.main(Driver.java:19)

The Java™ virtual machine by default may not provide enough heap space. You may enlarge the default allocation by setting the -Xmx. Eclipse provides a convenient way by means of a run time configuration (Menu Run --> Run Configurations):

Clicking the “Arguments” tab allows for setting the respective VM heap setting:

This allows for running your application with a maximum of 4 gigabytes of heap space.

With respect to automated unit testing (mvn test)you may want to set the same value in you pom.xml file

<plugin>
    <groupId>org.apache.maven.plugins</groupId>
    <artifactId>maven-surefire-plugin</artifactId>
    <version>2.19</version>
    <configuration>
      <argLine>-Xmx4G</argLine>
  </configuration>
</plugin>